Sort a linked list in O(n log n) time using constant space complexity.
Solution：Merge歸并排序 分治思想
思路：
pre-order部分：將list分為左右兩部分(中間處斷開以便處理)
Divide: 將分開的兩部分 遞歸去處理
Conquer: 將遞歸得到的分別排好序的左右結果 進行 merge排序：直接使用21題mergeTwoLists方法：http://www.reibang.com/p/ddad4576e950
注意遞歸終止條件次兆，以及傳遞關系(input:兩個斷開的序列告丢，return:排好序的頭節(jié)點)
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;
}
}
