Leetcode 148 Sort List

Sort a linked list in O(n log n) time using constant space complexity.
Solution 1: use quick sort partition and top down merge sort can get O(n log n) but need O(log n) space as in system stack. The only solution of O(1) space is bottom up merge sort.

 public class Solution {  
   public ListNode sortList(ListNode head) {  
     int n=0;  
     ListNode p=head;  
     while (p!=null) {n++; p=p.next;}  
     ListNode dummy=new ListNode(0);  
     dummy.next=head;  
     for (int size=1; size<n; size*=2) {  
       ListNode i=dummy;  
       while (true) {  
         ListNode j=i;  
         for (int k=0; k<size && j!=null; k++) j=j.next;  
         if (j==null || j.next==null) break;  
         ListNode t=j;  
         for (int k=0; k<size && t!=null; k++) t=t.next;  
         ListNode p1=i.next, p2=j.next;  
         j.next=null;  
         if (t!=null) {  
           ListNode temp=t.next;  
           t.next=null;  
           t=temp;  
         }  
         while (p1!=null || p2!=null) {  
           if (p1==null) {i.next=p2; i=i.next; p2=p2.next; }  
           else if (p2==null) {i.next=p1; i=i.next; p1=p1.next;}  
           else if (p1.val<p2.val) {i.next=p1; i=i.next; p1=p1.next;}  
           else {i.next=p2; i=i.next; p2=p2.next;}  
         }  
         if (t==null) break;  
         i.next=t;  
       }  
     }  
     return dummy.next;  
   }  
 }