Leetcode 86 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.

Solution 1:  Create 2 dummy list, put <x node to first list and rest to 2nd list. combine them together and then return.

 public class Solution {  
   public ListNode partition(ListNode head, int x) {  
     ListNode d1=new ListNode(0);  
     ListNode d2=new ListNode(0);  
     ListNode i=d1, j=d2, k=head;  
     while (k!=null) {  
       if (k.val<x) {  
         i.next=k;  
         i=i.next;  
         k=k.next;  
       }  
       else {  
         j.next=k;  
         j=j.next;  
         k=k.next;  
       }  
     }  
     i.next=d2.next;  
     j.next=null; //make sure end with null, no loop.  
     return d1.next;  
   }  
 }