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.

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
   typedef ListNode ln;  
   
   ListNode *partition(ListNode *head, int x) {  
     ln *list1 = new ln(0);  
     ln *list2 = new ln(0);  
       
     ln *tmp = head, *newHead = NULL, *list2head = list2;  
     while(tmp)  
     {  
       if (tmp->val < x)  
       {  
         list1->next = tmp;  
         list1 = tmp;  
         if(!newHead) newHead = tmp;  
       }  
       else  
       {  
         list2->next = tmp;  
         list2 = tmp;  
       }  
       tmp = tmp->next;  
     }  
     if(!newHead) newHead = list2head->next;  
     list1->next = list2head->next;  
     list2->next = NULL;  
   
     return newHead;  
   }