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;
    }
    
    
}