# C++实现LeetCode(86.划分链表)

[LeetCode] 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.

## [LeetCode] 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 orderwww.cppcns.com of the nodes in each of the two partitions.

For example,

Given 1->4->3-&CUddhTBgt;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