【LeetCode练习题】Partition List

 1 struct ListNode {
 2       int val;
 3       ListNode *next;
 4       ListNode(int x) : val(x), next(NULL) {}
 5  };
 6 
 7 //用cur和pre指向大于等于x的第一个节点和上一个节点，为了考虑第一个节点就大于x的情况，增加一个dummy的头结点便于处理方便。
 8 class Solution {
 9 public:
10     ListNode *partition(ListNode *head, int x) {
11         if(head == NULL){
12             return head;
13         }
14         ListNode *dummy = new ListNode(0);
15         dummy->next = head;
16         head = dummy;
17         bool hasGreater = false;
18         //找到第一个大于等于x的节点，用cur指向它
19         ListNode *pre = head, *cur = head->next;
20         while(cur!=NULL){
21             if(cur->val < x){
22                 pre = pre->next;
23                 cur = cur->next;
24             }
25             else{
26                 hasGreater = true;
27                 break;
28             }
29         }
30         //将cur节点之后所有的小于x的节点都挪到pre的后面，cur的前面。
31         if(hasGreater){
32             ListNode *pre2 = head, *cur2 = head->next;
33             bool isBehind = false;
34             while(cur2!=NULL){
35                 if(cur2->val == cur->val){
36                     isBehind = true;
37                 }
38                 if(isBehind && cur2->val < x){
39                     pre2->next = cur2->next;
40                     pre->next = cur2;
41                     cur2->next = cur;
42                     cur2 = pre2->next;
43                     pre = pre->next;
44                 }
45                 else{
46                     pre2 = pre2->next;
47                     cur2 = cur2->next;
48                 }
49             }
50         }
51         //去掉dummy节点。
52         head = head->next;
53         delete dummy;
54         return head;    
55     }
56 };