148. 排序链表

题目#

给你链表的头结点 head，请将其按升序排列并返回 排序后的链表 。

进阶：

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

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105

思路#

其实首先我想到的是一些邪道解法，比如用 map/数组或是堆……不过根据题目要求，这些解法显然都是不行的。

所以大概就是类似于 23. 合并 K 个升序链表中的分治法，不过是换成了在一条链表上工作。

同样的，21. 合并两个有序链表中合并两个有序链表的代码也可以直接在这里用。

代码#

递归#

递归法首先利用快慢指针找到链表中点，之后对两边进行递归处理。

func sort(head, tail *ListNode) *ListNode {
    // 空
    if head == nil {
        return head
    }

    // 断链
    if head.Next == tail {
        head.Next = nil
        return head
    }

    // 快慢指针获得中点
    slow, fast := head, head
    for fast != tail {
        slow = slow.Next
        fast = fast.Next
        if fast != tail {
            fast = fast.Next
        }
    }

    mid := slow

    return mergeTwoLists(sort(head, mid), sort(mid, tail))
}

func sortList(head *ListNode) *ListNode {
    return sort(head, nil)
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }

    if l1 == nil {
        cur.Next = l2
    } else {
        cur.Next = l1
    }

    return dummy.Next
}

迭代#

迭代法每次处理两个 1, 2, 4, 8, ... 个已排序节点的合并，直至整条链表有序。

// cut 用于「划分」
func cut(head *ListNode, n int) *ListNode {
    p := head
    for n--; n > 0 && p != nil; n-- {
        p = p.Next
    }
    if p == nil {
        return nil
    }

    next := p.Next
    p.Next = nil
    return next
}

func sortList(head *ListNode) *ListNode {
    dummy := &ListNode{0, head}

    // 确定长度
    length := 0
    for p := head; p != nil; p = p.Next {
        length++
    }

    // 这个 for 用于归并
    for i := 1; i < length; i *= 2 {
        // 这个 for 是一趟归并
        for cur, pre := dummy.Next, dummy; cur != nil; {
            // 左、右两个链表用于双链合并
            left := cur
            right := cut(left, i)

            // 往后面挪
            cur = cut(right, i)

            // 合并好后添加
            pre.Next = mergeTwoLists(left, right)
            for pre.Next != nil {
                pre = pre.Next
            }
        }
    }

    return dummy.Next
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := &ListNode{}
    cur := dummy

    for l1 != nil && l2 != nil {
        if l1.Val <= l2.Val {
            cur.Next = l1
            l1 = l1.Next
        } else {
            cur.Next = l2
            l2 = l2.Next
        }
        cur = cur.Next
    }

    if l1 == nil {
        cur.Next = l2
    } else {
        cur.Next = l1
    }

    return dummy.Next
}