86. Partition List Leetcode Java

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.

Solution:

Another linked list problem. 

Use a pointer to track the tail of the last listnode with value smaller than target and another pointer to track the tail of the last node with value greater or equal than the target value. Any node can be inserted into the right position and then update these two pointers accordingly. 

Tips: if these two pointer point to the same node which means currently there is no node with value>=target yet. So if we want to insert a node with value< target, we have to update both of the pointer together and still pointer to the same node.

 public ListNode partition(ListNode head, int x) {  
     if(head==null || head.next==null) return head;  
     ListNode preDummy=new ListNode(0);  
     preDummy.next=head;  
     ListNode pre=preDummy;  
     ListNode tail=preDummy;  
     while(tail.next!=null){  
       if(tail.next.val<x){  
         ListNode temp=tail.next.next;  
         if(pre.next!=tail.next){  
         tail.next.next=pre.next;  
         pre.next=tail.next;  
         tail.next=temp;  
         }  
         else tail=tail.next;  
         pre=pre.next;  
       }  
       else {  
         tail=tail.next;  
       }      
     }  
     return preDummy.next;  
   }