148. 排序链表

[wengzc]

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

题目链接：https://leetcode-cn.com/problems/sort-list

[wengzc]

需掌握知识：

• merge(l1, l2)，双路归并

• cut(l, n)，断链操作，它表示，将链表 l 切掉前 n 个节点，并返回后半部分的链表头

• dummy 结点，人为制造出来的第一个结点的前驱结点

解法一：迭代归并合并（从底至顶直接合并，空间复杂度O(1)，符合题意要求）

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function (head) {
    if (!head || !head.next) return head
    let len = 0
    let dummy = new ListNode()
    dummy.next = head
    let p = head
    while (p) {
        len++
        p = p.next
    }
    for (let size = 1; size < len; size *= 2) {
        let cur = dummy.next
        let tail = dummy
        while (cur) {
            // left 表示第一个待分割链表的头结点
            let left = cur
            // right 表示第二个待分割链表的头结点
            let right = cut(left, size)
            cur = cut(right, size)
            tail.next = merge(left, right)
            while (tail.next) {
                tail = tail.next
            }
        }
    }
    return dummy.next

    // 切掉链表head前 n 个节点，并返回后半部分的链表头
    function cut(head, n) {
        let p = head
        while (--n && p) {
            p = p.next
        }
        if (!p) return null
        let next = p.next
        // 切割操作
        p.next = null
        return next
    }
    // 双路归并
    function merge(l1, l2) {
        let dummy = new ListNode()
        let cur = dummy
        while (l1 && l2) {
            if (l1.val < l2.val) {
                cur.next = l1
                l1 = l1.next
            } else {
                cur.next = l2
                l2 = l2.next
            }
            cur = cur.next
        }
        cur.next = l1 ? l1 : l2
        return dummy.next
    }
}

解法二：递归归并排序（空间复杂度O(logn)（递归产生的），不符合题意常数级要求）

var sortList = function (head) {
    function mergeSort(node) {
        if (!node || !node.next) {
            return node
        }
        let fast = node, slow = node
        while (fast.next && fast.next.next) {
            fast = fast.next.next
            slow = slow.next
        }
        let mid = slow.next
        slow.next = null
        return merge(mergeSort(node), mergeSort(mid))
    }

    function merge(p, q) {
        let dummy = new ListNode()
        let cur = dummy
        while (p && q) {
            if (p.val < q.val) {
                cur.next = p
                p = p.next
            } else {
                cur.next = q
                q = q.next
            }
            cur = cur.next
        }
        cur.next = p ? p : q
        return dummy.next
    }
    return mergeSort(head)
};