148. 排序链表

题目链接（中等）

题目描述

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

数据范围：

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

进阶：你可以在 $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 = []
输出： []

核心思路

归并排序的核心步骤：

1. 分：把链表从中点拆成两半；
2. 治：递归地对两半排序；
3. 合：把两个有序链表合并成一个有序链表（就是 LC 21 的 merge）21. 合并两个有序链表

两种实现方式：

• 自顶向下：递归拆链表，空间 $O(\log n)$（递归栈）；
• 自底向上：从长度为 1 的子链表开始，两两合并，空间 $O(1)$。

---

方法一：自顶向下归并排序（递归）

思路及解法

找中点：用快慢指针。fast 每次走 2 步，slow 每次走 1 步。当 fast 到达 tail 时，slow 指向链表的中点。

这里传的是 (head, tail) 开区间：排序 [head, tail) 范围内的节点，tail 是哨兵不参与排序。

分：从中点 mid = slow 处断开：

• 左半：[head, mid)；
• 右半：[mid, tail)。

递归终止：当区间只剩 1 个节点（head.next == tail）或为空时，直接返回。

合：用 LC 21 的 merge 函数合并两个有序链表。

merge 技巧：

• 用哑节点 dummy 简化头节点处理；
• 用 cur 指向合并后的尾节点，逐个比较 p1.val 和 p2.val，谁小接谁；
• 一边走完后，把另一边剩下的整体接上。

代码

class Solution:
    def sortList(self, head: ListNode | None) -> ListNode | None:
        def sortFunc(head: ListNode, tail: ListNode) -> ListNode:
            if not head:
                return head
            # 只剩一个节点，直接返回
            if head.next == tail:
                head.next = None
                return head

            # 快慢指针找中点
            slow = fast = head
            while fast != tail:
                slow = slow.next
                fast = fast.next
                if fast != tail:
                    fast = fast.next
            mid = slow

            # 分治 + 合并
            return merge(sortFunc(head, mid), sortFunc(mid, tail))

        def merge(head1: ListNode, head2: ListNode) -> ListNode:
            dummy = ListNode(0)
            cur, p1, p2 = dummy, head1, head2
            while p1 and p2:
                if p1.val <= p2.val:
                    cur.next = p1
                    p1 = p1.next
                else:
                    cur.next = p2
                    p2 = p2.next
                cur = cur.next
            cur.next = p1 if p1 else p2
            return dummy.next

        return sortFunc(head, None)

复杂度分析

• 时间复杂度：$O(n \log n)$，归并排序的层数是 $\log n$，每层合并总代价是 $O(n)$。
• 空间复杂度：$O(\log n)$，主要来自递归栈深度。

---

方法二：自底向上归并排序（迭代）

思路及解法

递归版本有 $O(\log n)$ 的栈空间开销。要达到进阶要求的 $O(1)$ 空间，可以使用自底向上的迭代写法。

核心思路：

• 一开始把每个节点视为长度为 1 的有序子链表；
• 每一轮把相邻两个长度为 step 的有序子链表合并，得到长度为 2 * step 的有序子链表；
• step 翻倍，重复上述过程，直到 step >= n。

流程：

1. 先遍历一遍，求出链表长度 n；
2. step = 1；
3. 当 step < n 时：
   • 用 cur 从左到右扫一遍链表；
   • 每次用 fun 切出两段长度为 step 的子链表，调用 merge 合并；
   • step *= 2；
4. 返回排序后的链表。

两个辅助函数：

• fun(node, k)：从 node 开始切出长度为 k 的一段（内部把第 k 个节点的 next 置 None），返回剩余部分的起点；
• merge(head1, head2, tail)：把两个有序链表接到 tail 后面，返回合并后的尾节点。相比传统 merge 返回头节点，这种写法可以直接用返回的尾节点更新 pre，省去 while pre.next: pre = pre.next 的遍历。

关键点：

• 用 dummy = ListNode(0, head) 作为虚拟头，统一处理「第一段的头」「上一段的尾」等位置关系；
• 每轮合并前，必须把两段各自从后文切断（cur.next = None），否则 merge 会把后面未处理的节点混进来；
• 每轮结束后 step 必须严格翻倍（step *= 2 或 step <<= 1）。

代码

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        # 求链表长度
        n = 0
        cur = head
        while cur:
            n += 1
            cur = cur.next

        def merge(head1, head2, tail):
            """把两个有序链表接到 tail 后面，返回合并后的尾节点"""
            p, p1, p2 = tail, head1, head2
            while p1 and p2:
                if p1.val <= p2.val:
                    p.next = p1
                    p1 = p1.next
                else:
                    p.next = p2
                    p2 = p2.next
                p = p.next
            p.next = p1 or p2
            while p.next:
                p = p.next
            return p

        def fun(node, k):
            """切出从 node 开始长度为 k 的一段，返回剩余部分的起点"""
            if not node:
                return None
            cur = node
            for _ in range(k - 1):
                if cur.next:
                    cur = cur.next
                else:
                    return None
            rest = cur.next
            cur.next = None
            return rest

        dummy = ListNode(0, head)
        step = 1
        while step < n:
            pre = dummy
            cur = dummy.next
            while cur:
                head1 = cur
                cur = fun(head1, step)      # 切出第一段
                head2 = cur
                cur = fun(head2, step)      # 切出第二段
                pre = merge(head1, head2, pre)
            step <<= 1                      # step 翻倍
        return dummy.next

复杂度分析

• 时间复杂度：$O(n \log n)$，外层 step 从 1 倍增到 n，共 $\log n$ 层；每层遍历一遍链表。
• 空间复杂度：$O(1)$，只用常数个指针。