Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Naive Way:时间复杂度的要求决定了只能是merge sort, quick sort 或者用 heap。空间复杂度先排除heap。Quick sort不熟，先试merge sort。merge sort能否只用O(1) space？好像是可以的。

写了N久终于写完了。用一快一慢两个指针引领要被merge的部分，merge函数需要在末尾清零（null），主函数需要用一个指针标记剩下的部分，以便前面部分merge完以后接上。

 /**  
  * Definition for singly-linked list.  
  * class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode sortList(ListNode head) {  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake, fast = fake, slow = fake;  
     fake.next = head;  
     // get the length of list  
     int length = 0;  
     while(cur.next!=null){  
       length++;  
       cur = cur.next;  
     }  
     for(int step = 1;step < length;step*=2){  
       cur = fake;  
       while(cur.next!=null){  
         slow = cur.next;  
         fast = cur.next;  
         int i = 0;  
         // find correct merge starting position  
         while(fast.next!=null && i < step){fast = fast.next; i++;}  
         if(i!=step) break;  
         ListNode temp = fast;  
         i = 0;  
         while(temp!=null && i < step){temp = temp.next; i++;}  
         // merge two lists  
         cur.next = merge(slow, fast, step);  
         // connect with remaining nodes  
         i = 0;  
         while(i < 2*step && cur.next!=null){cur = cur.next;i++;}  
         cur.next = temp;  
       }  
     }  
     return fake.next;  
   }  
   private ListNode merge(ListNode a, ListNode b, int len){  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake;  
     int i = 0,j = 0;  
     while(i < len && j < len && a!=null && b!=null){  
       if(a.val < b.val){  
         cur.next = a;  
         a = a.next;  
         i++;  
       }else{  
         cur.next = b;  
         b = b.next;  
         j++;  
       }  
       cur = cur.next;  
     }  
     while(i < len && a!=null){  
       cur.next = a;  
       a = a.next;  
       i++;  
       cur = cur.next;  
     }  
     while(j < len && b!=null){  
       cur.next = b;  
       b = b.next;  
       j++;  
       cur = cur.next;  
     }  
     cur.next = null;  
     return fake.next;  
   }  
 }  

Improved Way:看到Discuss里很多人都是 大的merge  call 小的merge，那样就会造成一个stack的空间使用，就不是O(1)的了，要实现O(1)，必须从小的往大的写，这样才不会同时进行多个merge。

一些提升的地方：

有一个人用Bit 运算移位来实现step*2，这样挺好的。

有一个人将获取slow, 和fast的位置写成单独的函数，这样主函数就会清晰很多。

最重要的问题：Quick Sort 是否可以写成O(1)的关于链表的。从算法的流程上讲是可以的，先对整个list 进行左右交换，然后对前一半和后一半分别进行左右交换，这样下来应该可以不适用额外空间。