Partition List

Not difficult one. One thing to be noticed is to keep track of the last smaller node, after which new node with smaller should be inserted. Then each time if a smaller node is found, insert it after the last smaller one, and last smaller is now pointed to its next node.

 /**  
  * 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) {  
     if(head == null || head.next == null) return head;  
     ListNode lastSmaller = new ListNode(Integer.MIN_VALUE);  
     ListNode fakeHead = lastSmaller;  
     lastSmaller.next = head;  
     ListNode preNode = lastSmaller;  
     ListNode crntNode = lastSmaller.next;  
     boolean largeFound = false;  
     while(crntNode != null){  
       if(crntNode.val >= x){  
         if(!largeFound) largeFound = true;  
         preNode = preNode.next;  
         crntNode = preNode.next;  
       }  
       else{  
         if(largeFound){  
           preNode.next = crntNode.next;  
           crntNode.next = lastSmaller.next;  
           lastSmaller.next = crntNode;  
           lastSmaller = lastSmaller.next;  
           crntNode = preNode.next;  
         }  
         else{  
           lastSmaller = lastSmaller.next;  
           preNode = preNode.next;  
           crntNode = preNode.next;  
         }  
       }  
     }  
     return fakeHead.next;  
   }  
 }