LeetCode之“链表”：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.

　　该题利用dummy节点能极大方便编程，具体程序如下：

 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 || !head->next)
13             return head;
14         
15         ListNode *dummy = new ListNode(INT_MIN);
16         dummy->next = head;
17         ListNode *parNode = dummy;
18         ListNode *preNode = nullptr, *curNode = nullptr;
19         while(parNode && parNode->val < x)
20         {
21             preNode = parNode;
22             parNode = parNode->next;
23         }
24         
25         parNode = preNode;
26         if(!parNode || !parNode->next)
27         {
28             head = dummy->next;
29             delete dummy;
30             dummy = nullptr;
31             return head;
32         }
33         
34         preNode = parNode->next;
35         curNode = preNode->next;
36         while(curNode)
37         {
38             if(curNode->val < x)
39             {
40                 ListNode *nextPar = parNode->next, *nextCur = curNode->next;
41                 parNode->next = curNode;
42                 curNode->next = nextPar;
43                 parNode = parNode->next;
44                 
45                 curNode = nextCur;
46                 preNode->next = curNode;
47             }
48             else
49             {
50                 preNode = preNode->next;
51                 curNode = curNode->next;
52             }
53         }
54         
55         head = dummy->next;
56         delete dummy;
57         dummy = nullptr;
58         
59         return head;
60     }
61 };