LeetCode OJ

题目：

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.

解题思路：

设立两个指针： pre 和 cur。 pre指向最后一个比x小的节点，cur指向当前节点。每次找到一个比x小的节点时把他链接至pre后面，更新pre指针。

代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *partition(ListNode *head, int x) {
12         if (head == NULL) return NULL;
13 
14         ListNode *ans = new ListNode(0);
15         ans->next = head;
16         ListNode *first_bigger = head;
17         ListNode *pre = ans;
18         while (first_bigger != NULL && first_bigger->val < x) {
19             first_bigger = first_bigger->next;
20             pre = pre->next;
21         }
22         ListNode *cur = first_bigger, *tmp = pre;
23         while (cur != NULL) {
24             while (cur != NULL && cur->val >= x) {
25                 tmp = cur;
26                 cur = cur->next;            
27             }
28             if (cur == NULL) break;
29             tmp->next = cur->next;
30             cur->next = pre->next;
31             pre->next = cur;
32             pre = cur;
33             cur = tmp->next;
34         }
35         return ans->next;
36     }
37 };