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.

Naive Way: A straightforward way is to use two head pointers to carry the list with all nodes less than x and the list with all nodes greater or equal to x. And that's O(1) space. Reset the tail of the second list may be ignored!

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode partition(ListNode head, int x) {  
     ListNode less = new ListNode(0);  
     ListNode noLess = new ListNode(0);  
     ListNode p1 = less;  
     ListNode p2 = noLess;  
     for(ListNode cur = head;cur!=null;cur = cur.next){  
       if(cur.val < x){  
         p1.next = cur;  
         p1 = p1.next;  
       }else{  
         p2.next = cur;  
         p2 = p2.next;  
       }  
     }  
     p2.next = null;  
     p1.next = noLess.next;  
     return less.next;  
   }  
 }