# 86. Partition List

Given a linked list and a value  x , partition it such that all nodes less than  x  come before nodes greater than or equal to  x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given `1->4->3->2->5->2` and  x  = 3,
return `1->2->2->4->3->5`.

``````class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *dummy = new ListNode(-1);
ListNode *pre = dummy, *cur = head;;
while (pre->next && pre->next->val < x) pre = pre->next;
cur = pre;
while (cur->next) {
if (cur->next->val < x) {
ListNode *tmp = cur->next;
cur->next = tmp->next;
tmp->next = pre->next;
pre->next = tmp;
pre = pre->next;
} else {
cur = cur->next;
}
}
return dummy->next;
}
};
``````

1 -> 4 -> 3 -> 2 -> 5 -> 2

1 -> 2 -> 4 -> 3 -> 5 -> 2

1 -> 2 -> 2 -> 4 -> 3 -> 5

``````class Solution {
public:
ListNode *partition(ListNode *head, int x) {
ListNode *dummy = new ListNode(-1);
ListNode *newDummy = new ListNode(-1);
ListNode *cur = dummy, *p = newDummy;
while (cur->next) {
if (cur->next->val < x) {
p->next = cur->next;
p = p->next;
cur->next = cur->next->next;
p->next = NULL;
} else {
cur = cur->next;
}
}
p->next = dummy->next;
return newDummy->next;
}
};
``````

Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2

New:

Original: 4 -> 3 -> 2 -> 5 -> 2

New:　  1

Original: 4 -> 3 -> 5 -> 2

New:　  1 -> 2

Original: 4 -> 3 -> 5

New:　  1 -> 2 -> 2

Original:

New:　  1 -> 2 -> 2 -> 4 -> 3 -> 5

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation