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.

思路：

用两个指针less和greater分别保存小于x和大于x的列表，然后遍历一遍，一边遍历一边更新这两个指针。

代码：

 1     ListNode *partition(ListNode *head, int x) {
 2         // Note: The Solution object is instantiated only once and is reused by each test case.
 3         if(head == NULL)
 4             return NULL;
 5         ListNode *less=NULL, *greater=NULL;
 6         ListNode *newhead = head, *greaterhead = NULL;
 7         while(head){
 8             ListNode *tmp = head->next;
 9             if(head->val < x){
10                 if(less == NULL){
11                     less = head;
12                     newhead = less;
13                 }    
14                 else{
15                     head->next = less->next;
16                     less->next = head;
17                     less = less->next;
18                 }
19             }
20             else{
21                 if(greater == NULL){
22                     greaterhead = head;
23                     greater = head;
24                     greater->next = NULL;
25                 }
26                 else{
27                     greater->next = head;
28                     greater = greater->next;
29                     greater->next = NULL;
30                 }
31             }
32             head = tmp;
33         }
34         if(less)
35             less->next = greaterhead;
36         return newhead;
37     }