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

» Solve this problem

[解题思路]
从左往右扫描，找到第一个大于X的指针，然后再该指针左边，不断插入小于X的元素。这里为了避免处理head是否为空的检测，在头指针位置先插入一个干扰元素，以保证head永不为空，然后在最后返回的时候删除掉。


[Code]

1:    ListNode *partition(ListNode *head, int x) {  
2:      // Start typing your C/C++ solution below  
3:      // DO NOT write int main() function      
4:      ListNode* p = new ListNode(x-1);  
5:      p->next = head;  
6:      head = p;  
7:      ListNode* pre;  
8:      while(p!=NULL && p->val < x)  
9:      {  
10:        pre = p;  
11:        p = p->next;  
12:      }  
13:      if(p!=NULL)  
14:      {      
15:        ListNode* cur = pre;  
16:        while(p!=NULL)      
17:        {  
18:          if(p->val <x)  
19:          {  
20:            ListNode* temp = cur->next;  
21:            pre->next = p->next;  
22:            cur->next = p;  
23:            cur = p;  
24:            p->next = temp;  
25:            p = pre;  
26:          }  
27:          pre=p;  
28:          p= p->next;        
29:        }  
30:      }  
31:      ListNode* temp = head;  
32:      head = head->next;  
33:      delete temp;  
34:      return head;      
35:    }  

[Note]
1. Line 15
cur为插入位置的指针，在双指针遍历过程中是不变的。