LeetCode 148 Sort List
Sort a linked list in O(n log n) time using constant space complexity.
對于linked list而言戚哎，除了insertion sort比較容易實現(xiàn)以外麦锯，剩下o(nlogn)的算法中，merge sort比較容易實現(xiàn)砚嘴。
大致思路：用快慢指針，每次都找到list的中點宇整，然后遞歸對前后兩段分別sort灵奖，再merge排序后的前后兩段list。
也即divide and conquer的方法：Each time divided the given list into two sub list. Merge sub list after bottom case return.
我一開始糾結(jié)在哨颂，通過什么方式divide？相种？威恼？
其實只要分別對前半段和后半段list分別調(diào)用sort函數(shù)，傳入head與slow.next寝并，其實等價于實現(xiàn)了divideｓ锎搿！衬潦！對sort好的前半段后半段再merge即可斤蔓。
而sort每一段list可以分為兩種情況：
list為null或者單節(jié)點時，直接返回镀岛。
list>=2個node時弦牡，將其分成前后半段，各自sort后漂羊，合并驾锰。
所以最基礎(chǔ)的情況，是從2個node開始合并走越，然后再越并越長椭豫。
這里要注意一個trick
操作slow與fast時，到底用slow還是slow.next代表后半段的開始旨指？赏酥！
如果用slow代表后半段的開始，那還需要一個prev node淤毛，每次記錄slow的前一個節(jié)點，這樣才能將前半段的next最后賦值為null算柳，從而cut前半段與后半段低淡。
而用slow.next代表后半段第一個node，則直接slow.next=null，就可以完成cutＵ崽！：渭浴！
代碼：
public class Solution {
public ListNode sortList(ListNode head) {
// If list is null or only has 1 node, then return
if (head == null || head.next == null) return head;
// Use slow & fast pointer to find the middle of list
ListNode slow = head, fast = head.next.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow.next points to the middle!!!
// Break up the list at slow.next by assigning slow.next = null
ListNode h2 = sortList(slow.next);
slow.next = null;
return merge(sortList(head), h2);
}
public ListNode merge(ListNode p1, ListNode p2) {
// How to choose which node as the first node?!
// To deal with the corner case of the first node, we use a dummy node
// So the assign of all nodes can be implemented by using next pointer!!!
ListNode dummy = new ListNode(Integer.MIN_VALUE);
ListNode c = dummy;
while (p1 != null && p2 != null) {
if (p1.val < p2.val) {
c.next = p1;
p1 = p1.next;
} else {
c.next = p2;
p2 = p2.next;
}
c = c.next;
}
if (p1 != null) c.next = p1;
if (p2 != null) c.next = p2;
return dummy.next;
}
}
