LeetCode 148 Sort List
Sort a linked list in O(n log n) time using constant space complexity.
对于linked list而言，除了insertion sort比较容易实现以外，剩下o(nlogn)的算法中，merge sort比较容易实现。
大致思路：用快慢指针，每次都找到list的中点，然后递归对前后两段分别sort，再merge排序后的前后两段list。
也即divide and conquer的方法：Each time divided the given list into two sub list. Merge sub list after bottom case return.
我一开始纠结在，通过什么方式divide？？？
其实只要分别对前半段和后半段list分别调用sort函数，传入head与slow.next，其实等价于实现了divide！！！对sort好的前半段后半段再merge即可。
而sort每一段list可以分为两种情况：
list为null或者单节点时，直接返回。
list>=2个node时，将其分成前后半段，各自sort后，合并。
所以最基础的情况，是从2个node开始合并，然后再越并越长。
这里要注意一个trick
操作slow与fast时，到底用slow还是slow.next代表后半段的开始？！
如果用slow代表后半段的开始，那还需要一个prev node，每次记录slow的前一个节点，这样才能将前半段的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;
}
}
