Leetcode -- Partition List

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
   ListNode *partition(ListNode *head, int x) {  
     ListNode * left = new ListNode(0);  
     ListNode * right = new ListNode(0);  
     ListNode * l = left;  
     ListNode * r = right;  
     ListNode * p = head;  
     while(p != NULL) {  
       if(p->val < x) {  
         l->next = p;  
         p = p->next;  
         l = l->next;  
         l->next = NULL;  
       } else {  
         r->next = p;  
         p = p->next;  
         r = r->next;  
         r->next = NULL;  
       }  
     }  
     l->next = right->next;  
     return left->next;  
   }  
 };