148. Sort List

https://leetcode.com/problems/sort-list/description/

Both Merge Sort and Quick Sort can achieve O(n log n) runtime.

代码：

class Solution {
    class NodePair {
        ListNode start;
        ListNode end;
        public NodePair(ListNode start, ListNode end) {
            this.start = start;
            this.end = end;
        }
    }
    
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        NodePair nodePair = sortListHelper(head);
        return nodePair.start;
    }
    
    private NodePair sortListHelper(ListNode head) {
        if (head == null) {
            return null;
        } else if (head.next == null) {
            return new NodePair(head, head);
        }
        ListNode pivot = head;
        ListNode runner = head.next;
        pivot.next = null;
        ListNode smallHead = new ListNode(0);
        ListNode smallRunner = smallHead;
        ListNode bigHead = new ListNode(0);
        ListNode bigRunner = bigHead;
        while (runner != null) {
            if (runner.val <= pivot.val) {
                smallRunner.next = runner;
                smallRunner = smallRunner.next;
                runner = runner.next;
                smallRunner.next = null;
            } else {
                bigRunner.next = runner;
                bigRunner = bigRunner.next;
                runner = runner.next;
                bigRunner.next = null;
            }
        }
        NodePair smallPartial = sortListHelper(smallHead.next);
        NodePair bigPartial = sortListHelper(bigHead.next);
        ListNode newStart = null;
        ListNode newEnd = null;
        
        if (smallPartial == null) {
            newStart = pivot;
        } else {
            smallPartial.end.next = pivot;
            newStart = smallPartial.start;
        }
        
        if (bigPartial == null) {
            newEnd = pivot;
        } else {
            pivot.next = bigPartial.start;
            newEnd = bigPartial.end;
        }
        
        return new NodePair(newStart, newEnd);
    }
}

采用了 pivot as head 的 quick sort 算法。

实际上，pivot 取中，时间复杂度也是 O(n log n). 只是每一层的递归中，当下 List 需要遍历两遍，第一遍为 pivot 找到 List middle node；第二遍，以 pivot 为界，将 List 分为两段。

为 pivot 取 head，可以在每层递归中，只进行一次遍历。

如此看来，该题目使用 Merge Sort，取中分段，时间复杂度也是 O(n log n)，空间复杂度需要再考虑一下。Array merge sort 是使用了 O(n) 的额外空间来进行Merge。

使用 Merge Sort, 空间复杂度取决于需要合并的次数, 需要 dummyHead 来进行合并。O(n)，推导如下：

需要合并的次数：
1 + 2 + 4 + ... + n
=> 2^0 + 2^1 + 2^2 + ... + 2^(log n)  // 共 (log n) 个项
=> 1 * (2^(log n) - 1) / (2 - 1)   // 等比数列求和公式
=> n