LeetCode LCR 077. 排序链表

2026-03-28 HGNULB 约 7 分钟

文章信息 5 个分类 6 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 077. 排序链表

题意分析

给定单链表的头节点 head，将链表按升序重新排列后返回新的头节点。节点数最多 5 * 10^4，节点值在 [-10^5, 10^5] 内，链表可能为空。

进阶要求是最关键的信号：$O(n \log n)$ 时间加常数级空间。时间下限排除了逐个取节点插入有序部分这类平方级做法；空间要求则堵死了「把值读进数组、排完再写回」的取巧路线——出这道题就是想看你直接在链表结构上排序。

链表与数组的本质差异是不支持按下标随机访问，只能顺序移动指针。这决定了可行的做法必须只依赖两种操作：顺序扫描，以及改接 next 指针。

边界：空链表、单节点、本就有序、所有值相等，都应正确返回。

解法：快慢指针拆分归并排序

核心思路

暴力做法：每轮扫描剩余节点，摘出最小的接到结果尾部，时间 $O(n^2)$；n = 5 * 10^4 时比较次数达十亿量级，也不满足进阶要求。

突破口是链表的一个优势操作：两条各自有序的链表，只靠比较头节点、改接 next 指针，就能在一次线性扫描内合并成一条有序链表，不需要任何辅助数组。有了这个 $O(n)$ 的合并原语，问题就转化为「如何得到两条有序的半长链表」——把链表切成两半，各自递归排序即可。

递归结构：sortList(head) 的语义是「返回这一段排好序后的头节点」。终止条件是空或单节点（天然有序）；否则用快慢指针找中点——slow 每次一步、fast 每次两步且从 head.next 出发，循环结束时 slow 恰好停在前半段尾部：偶数长度切成 n/2 + n/2，奇数长度切成前长后短的两段。必须把 slow.next 置空真正断链，两个子问题才严格小于原问题，递归才能收敛。

递归版的空间开销是 $O(\log n)$ 的调用栈。若要严格做到 $O(1)$ 空间，需改为自底向上：不递归切分，而是按子段长度 1, 2, 4, … 迭代地两两合并，用循环变量取代调用栈，合并原语完全不变。

解题步骤

若 head == null 或 head.next == null，直接返回 head：空链表与单节点天然有序，这也是递归的终止条件。

slow 从 head、fast 从 head.next 出发同步前进找中点：错开一位保证 slow 停在前半段尾节点，偶数长度平均切分，不会出现「前段等于整条链」的切法。

记录 rightHead = slow.next，再置 slow.next = null：先存后断，右半段不丢；断链让左半段递归时看不到右半段。

递归排序左右两段：子问题规模减半且语义与整体一致，各自返回有序段头节点。

用带 dummy 头的双指针合并两条有序链表：每次接上较小的头节点，dummy 免去「结果链第一个节点」的特判；循环结束后把未走完的一段整体接上。

以 4 → 2 → 1 → 3 走一遍：slow 从 4、fast 从 2 出发，一轮后 slow = 2、fast = 3，fast.next 为空停止；rightHead = 1，断链得到 4 → 2 与 1 → 3。左段递归再切成 4 和 2，均为单节点直接返回，合并得 2 → 4；右段同理切成 1 和 3，合并得 1 → 3。最后合并 2 → 4 与 1 → 3：依次取 1、2、3，右段走完后把剩余的 4 整段接上，返回 1 → 2 → 3 → 4。

代码实现

class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // slow 是左半段尾节点，断开后左右两段才能独立递归。
        ListNode rightHead = slow.next;
        slow.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);
        return merge(left, right);
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }
            tail = tail.next;
        }
        if (list1 != null) {
            tail.next = list1;
        } else {
            tail.next = list2;
        }

        return dummy.next;
    }
}

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // 断开左右两段，避免左半段递归时继续连到右半段。
    rightHead := slow.Next
    slow.Next = nil

    left := sortList(head)
    right := sortList(rightHead)
    return mergeSortedLists(left, right)
}

func mergeSortedLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }
    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }

    return dummy.Next
}

复杂度分析

时间复杂度：$O(n \log n)$。每层递归里，快慢指针切分与两两合并各扫描本层全部节点一次，单层共 $O(n)$；链长每层减半，共 $O(\log n)$ 层。

空间复杂度：$O(\log n)$。节点原地复用、只改指针，额外开销只有递归调用栈，深度等于切分层数 $O(\log n)$。

关键点总结

链表排序首选归并：合并阶段只改指针、零辅助数组，而依赖下标随机访问的排序（按下标划分的快排、堆排）在链表上失去优势。

fast = head.next 的错位起点是收敛性的保证：它让前半段永远短于整条链表。

「先存 rightHead、再断 slow.next」的顺序不可颠倒，断链是递归子问题严格变小的前提。

dummy 哨兵节点是链表合并、重构类代码消除头节点特判的通用技巧。

面试视角：高频追问是「递归栈也算空间，如何做到严格 $O(1)$？」——要能口述自底向上按长度 1, 2, 4, … 迭代归并的方案；另一常见考法是先手写合并两个有序链表（21 题），再组装出本题。

易错点总结

错误写法：fast 与 slow 同从 head 出发。反例 [4, 2]：slow 会停在 2，rightHead = null，左段仍是完整的 4 → 2，递归规模没有减小，最终无限递归并栈溢出。

忘记 slow.next = null 断链：[4, 2, 1, 3] → 左段递归时仍连着右半段，子问题不是前一半而是整条链 → 无限递归。

终止条件漏掉 head.next == null：单节点段 [5] → 切分得到 rightHead = null，左段仍是 [5] 自身 → 无限递归栈溢出。

快慢循环条件写成 while (fast.next != null)：[1, 2, 3] → 一轮后 fast = null，下一轮读 fast.next 空指针异常。

合并循环中忘记 tail = tail.next：[2, 1] → tail 一直停在 dummy，dummy.next 被反复覆盖 → 节点丢失，结果只剩最后接上的一个。

合并结束漏接剩余段：合并 1 → 2 与 3 → 4 → 循环因左段走完而退出，3 → 4 没接上 → 返回 1 → 2，丢掉一半节点。

读值进数组排序再写回：[4, 2, 1, 3] → 结果虽对，但 $O(n)$ 额外空间违背进阶要求 → 面试中被当场要求重写。

合并时 new ListNode(val) 新建节点：任意用例 → 结果正确但多出 $O(n)$ 空间分配 → 违背链表题「复用原节点、只改指针」的预期。

相似题目

题目	难度	考察点
21. 合并两个有序链表	简单	本题合并子过程的独立成题
23. 合并 K 个升序链表	困难	两路合并推广到 K 路的分治
147. 对链表进行插入排序	中等	平方级链表排序的对照实现
876. 链表的中间结点	简单	快慢指针找中点的独立成题
912. 排序数组	中等	数组上的手写归并与快排
补充题 5. 手撕归并排序	中等	归并排序模板的白板默写