题目
给你一个链表和一个特定值 x ,请你对链表进行分隔,使得所有小于 x 的节点都出现在大于或等于 x 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
输入:head = 1->4->3->2->5->2, x = 3
输出:1->2->2->4->3->5
思路
- 思路很简单,双指针,两个伪头部节点,把小于x的串起来,大于等于x的穿起来,两个合并即可
- 虽然我也没跑出来。。。之前做过一次也没跑出来,忘了把p2->next设空
代码
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* dummyHead1 = new ListNode(-1);
ListNode* dummyHead2 = new ListNode(-1);
ListNode* p1 = dummyHead1, *p2 = dummyHead2, *curr = head;
while(curr){
if(curr->val < x) {
p1->next = curr;
p1 = p1->next;
}
else {
p2->next = curr;
p2 = p2->next;
}
curr = curr->next;
}
p2->next = nullptr;
p1->next = dummyHead2->next;
return dummyHead1->next;
}
};