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

Solution：Merge歸并排序 分治思想

思路：
pre-order部分：將list分為左右兩部分(中間處斷開以便處理)
Divide: 將分開的兩部分 遞歸去處理
Conquer: 將遞歸得到的分別排好序的左右結(jié)果 進(jìn)行 merge排序：直接使用21題mergeTwoLists方法：http://www.itdecent.cn/p/ddad4576e950
注意遞歸終止條件，以及傳遞關(guān)系(input:兩個斷開的序列，return:排好序的頭節(jié)點(diǎn))
Time Complexity: T(N) = 2T(N / 2) + O(N) => O(NlogN)
Space Complexity: O(logN) 遞歸緩存logN層

Solution Code：

class Solution {
  
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
        return head;
        
        // step 1. cut the list to two halves
        ListNode slow = head;
        ListNode fast = head;
        while(fast.next != null && fast.next.next != null){ 
            slow = slow.next;
            fast = fast.next.next;
        }

        //  1     ->    2    ->    3    ->    4    ->  null
        //             slow   right_start    fast

        ListNode right_start = slow.next;
        slow.next = null; // cut off from middle


        // step 2. sort each half
        ListNode l1 = sortList(head);
        ListNode l2 = sortList(right_start);

        // step 3. merge l1 and l2
        return mergeTwoLists(l1, l2);
    }
    
  
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode cur1 = l1;
        ListNode cur2 = l2;
        
        ListNode dummy = new ListNode(0);
        ListNode cur = dummy;
        while(cur1 != null && cur2 != null) {
            if(cur1.val < cur2.val) {
                cur.next = cur1;
                cur1 = cur1.next;
            }
            else {
                cur.next = cur2;
                cur2 = cur2.next;
            }
            cur = cur.next;
        }        
        // the rest
        cur.next = cur1 == null ? cur2 : cur1;
        return dummy.next;
    }
}