十大网站建设排名,网站更新中,潍坊市城乡建设局网站,网站设计制作 联系1. 题目
编写程序以 x 为基准分割链表#xff0c;使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 x#xff0c;x 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可#xff0c;其不需要被置于左右两部分之间。
示例:
输入…1. 题目
编写程序以 x 为基准分割链表使得所有小于 x 的节点排在大于或等于 x 的节点之前。如果链表中包含 xx 只需出现在小于 x 的元素之后(如下所示)。分割元素 x 只需处于“右半部分”即可其不需要被置于左右两部分之间。
示例:
输入: head 3-5-8-5-10-2-1, x 5
输出: 3-1-2-10-5-5-8来源力扣LeetCode 链接https://leetcode-cn.com/problems/partition-list-lcci 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
题目意思将小于x的节点放在x前部partTail是满足上面要求的部分的尾巴建立空头节点哨兵用head遍历prev记录前置节点
class Solution {
public:ListNode* partition(ListNode* head, int x) {ListNode *emptyHead new ListNode(-1), *prev, *partTail;emptyHead-next head;partTail prev emptyHead;while(head){if(head-val x partTail ! prev)//注意第二个条件{prev-next prev-next-next;//把head断开head-next partTail-next;//head接入小于x的段partTail-next head;//head接上前段尾巴partTail partTail-next;//更新尾巴这句也可以不要//不要的话就是partTail其实是头不变一直往头上插入节点head prev-next;//更新head}else //其他情况直接后移{prev head;head head-next;}}return emptyHead-next;}
};
