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.

Example:

Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

 

题目大意：给定一个链表和值x，将链表划分，使得小于x的结点在大于等于x的结点之前，应该保持两组划分内结点的原始的相对顺序。

思路一：用两个链表，将小于x的结点放到一个链表，将大于等于x的放到另一个链表，最后串起来。

 1 ListNode* partition(ListNode* head, int x) {
 2         ListNode *node1 = new ListNode(0), *node2 = new ListNode(0), *cur1 = node1, *cur2 = node2;
 3         while (head) {
 4             if (head->val < x) {
 5                 cur1->next = head;
 6                 cur1 = cur1->next;
 7             } else {
 8                 cur2->next = head;
 9                 cur2 = cur2->next;
10             }
11             head = head->next;
12         }
13         cur1->next = node2->next;
14         cur2->next = nullptr; //不能少
15         return node1->next;
16     }

思路二：一个链表，但是双指针，慢指针指向小于x的结点组成链表的尾结点，快指针指向大于等于x的结点组成链表的尾结点，注：快指针始终应该不在慢指针的后面。

 1 ListNode* partition(ListNode* head, int x) {
 2         //slow指向第一个链表的尾结点，fast指向第二个链表的尾结点
 3         ListNode *res = new ListNode(0), *slow = res, *fast = res, *cur = head, *next;
 4         while (cur != nullptr) {
 5             next = cur->next;
 6             cur->next = nullptr;
 7             if (cur->val < x) {
 8                 if (slow == fast) { //应该始终保持fast指向的位置>= slow
 9                     slow->next = cur;
10                     slow = cur;
11                     fast = cur;
12                 } else {
13                     cur->next = slow->next;
14                     slow->next = cur;
15                     slow = cur;
16                 }
17             } else {
18                 fast->next = cur;
19                 fast = cur;
20             }
21             cur = next;
22         }
23         return res->next;
24     }