Friday, December 28, 2012

[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

[解题思路]

[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);
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:      }