148. 排序链表

还原成数组结构借助内部排序方法显然不是面试官所期待的解法；

链表结构中模拟快排显然很复杂，因此想能不能用归并；

很容易将问题拆解成：查找中间结点、分治母链表、合并两个链表的子问题；

问题的难点在于如何在merge后保持链表的完整性，因此需要注意以下几个细节：

1. 由于合并之后的链表的头结点可能和原head不一致，因此merge是有ListNode类型的返回值的；
2. merge所返回的是合并后的链表，而在mergeSort中，这相当于左右两个子链表；
3. 为了使merge完全转化为合并两个链表的问题，要确保两个子链表的尾部都指向null，而具体的实现是将中间结点的next指向null；
4. 递归的终止条件在于分治到只有一个结点的子链表，此时mid = head; mid.next = null，再进入下一层递归时要出来，显然终止条件应该是head.next == null，而返回的是head，不是null；
5. 合并链表的时候由于头结点要发生改变，因此最好的方式是建立一个哨兵；

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        ListNode res = mergeSort(head);
        return res;
    }
    private ListNode mergeSort(ListNode head) {
        if (head.next == null) return head; // 注意递归终止条件！
        ListNode mid = midNode(head);
        ListNode p = head, q = mid.next;
        mid.next = null; // 链尾一定要断开！这样可以保证merge的两个链表的表尾都指向null；
        ListNode left = mergeSort(p);
        ListNode right = mergeSort(q);
        return merge(left, right); // 头结点要通过merge来返回！
    }
    // 合并两个有序链表（21. 合并两个有序链表）
    private ListNode merge(ListNode p, ListNode q) {
        ListNode sentry = new ListNode(0); // 一定要建一个哨兵！
        ListNode cur = sentry;
        while (p != null && q != null) {
            if (p.val < q.val) {
                cur.next = p;
                p = p.next;
            } else {
                cur.next = q;
                q = q.next;
            }
            cur = cur.next;
        }
        if (p == null) {
            cur.next = q;
        } else {
            cur.next = p;
        }
        return sentry.next;
    }
    // 找到链表中间节点（876. 链表的中间结点）
    private ListNode midNode(ListNode head) { // 用快慢指针找中间结点！
        ListNode slow = head;
        ListNode fast = head.next; // 注意fast的初始值，这是为了mid能下取整
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}