03 链表排序双题精讲：插入排序与归并排序的链表实现

链表排序双题精讲：插入排序与归并排序的链表实现

摘要

链表排序是面试中链表与排序算法的交叉地带，难点不在排序算法本身，而在于如何在链表上实现排序——链表没有下标，无法随机访问，一些在数组上理所当然的操作（如通过索引访问中间元素）在链表上需要额外思考。本文通过两道经典题（Insertion Sort List 和 Sort List），深入剖析链表上插入排序和归并排序的实现细节，尤其是归并排序的自底向上迭代实现（真正做到 $O(1)$ 额外空间）。

---

第 1 章 链表排序的特殊性

1.1 链表的操作限制

在数组上，我们可以做的事情：

• $O(1)$ 随机访问（nums[i]）
• 原地交换（swap(nums, i, j)）
• 二分中点（mid = (left + right) / 2）

在链表上，这些操作的代价完全不同：

• 随机访问：$O(n)$，必须从头遍历
• 交换节点：复杂，通常通过修改指针而不是交换值来实现
• 找中点：需要快慢指针，$O(n)$

这些限制直接影响排序算法的选型：

• 快速排序：依赖随机访问（随机 pivot）和原地分区（频繁随机访问），在链表上退化为 $O(n)$ 的 pivot 选取 + $O(n)$ 的分区扫描，实现复杂且性能差
• 堆排序：完全依赖下标（父/子节点的下标计算），无法在链表上实现
• 插入排序：只需顺序扫描，可以在链表上实现，但最坏 $O(n^2)$
• 归并排序：找中点 + 合并，这两个操作在链表上都能高效实现，且合并不需要额外空间（修改指针即可）

结论：链表排序首选归并排序。 插入排序（LeetCode 147）是作为对比和练习存在的，理解它的实现有助于加深对链表操作的理解。

1.2 两道题的定位

题目	期望算法	时间复杂度	空间复杂度
LeetCode 147：Insertion Sort List	插入排序	$O(n^2)$	$O(1)$
LeetCode 148：Sort List	归并排序	$O(n\log n)$	$O(\log n)$（递归）/ $O(1)$（迭代）

---

第 2 章 LeetCode 147：链表插入排序

2.1 题目

LeetCode 147 - Insertion Sort List（中等）

给定单个链表的头节点 head，使用插入排序对链表进行排序，并返回排序后链表的头节点。

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

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

2.2 插入排序的链表版本

回忆数组版插入排序：维护一个”已排序前缀”，每次从未排序部分取一个元素，在已排序前缀中找到合适位置插入。

链表版插入排序的思路完全相同，但指针操作更复杂：

关键操作：

1. 从未排序链表中”摘取”当前节点
2. 在已排序链表中找到插入位置（找到第一个比当前节点值大的节点，插到它前面）
3. 将当前节点插入

难点：链表插入需要找到插入位置的前驱节点（因为需要修改前驱的 next 指针），而不是插入位置本身。这正是引入哑节点的动机——让已排序链表也有一个虚拟前驱。

public ListNode insertionSortList(ListNode head) {
    ListNode dummy = new ListNode(Integer.MIN_VALUE);
    // dummy 是已排序链表的虚拟头节点
    // dummy.next 指向已排序链表的真实头节点
 
    ListNode curr = head;  // curr 是当前要插入的节点
 
    while (curr != null) {
        ListNode next = curr.next;  // 先保存下一个待处理节点
 
        // 在已排序链表中找插入位置：找到第一个大于 curr.val 的节点的前驱
        ListNode prev = dummy;
        while (prev.next != null && prev.next.val < curr.val) {
            prev = prev.next;
        }
        // 此时 prev.next 是第一个 >= curr.val 的节点（或 null）
        // 把 curr 插入 prev 和 prev.next 之间
        curr.next = prev.next;
        prev.next = curr;
 
        curr = next;  // 处理下一个节点
    }
 
    return dummy.next;
}

2.3 详细走一遍示例

以 [4, 2, 1, 3] 为例：

初始：dummy -> null，curr = 4

处理 4：

• 已排序链表：dummy -> null
• 找插入位置：prev = dummy，prev.next = null，循环不执行
• 插入：4.next = null，dummy.next = 4
• 已排序链表：dummy -> 4 -> null

处理 2：

• curr = 2，next = 1
• 找插入位置：prev = dummy，prev.next.val = 4 >= 2，循环不执行
• 插入：2.next = 4，dummy.next = 2
• 已排序链表：dummy -> 2 -> 4 -> null

处理 1：

• curr = 1，next = 3
• 找插入位置：prev = dummy，prev.next.val = 2 >= 1，循环不执行
• 插入：1.next = 2，dummy.next = 1
• 已排序链表：dummy -> 1 -> 2 -> 4 -> null

处理 3：

• curr = 3，next = null
• 找插入位置：prev = dummy，prev.next.val = 1 < 3，prev = 1；prev.next.val = 2 < 3，prev = 2；prev.next.val = 4 >= 3，停止
• 插入：3.next = 4，2.next = 3
• 已排序链表：dummy -> 1 -> 2 -> 3 -> 4 -> null

最终返回 dummy.next = 1。

2.4 一个小优化

观察到：如果当前节点 curr.val 大于等于已排序链表的最后一个节点，说明 curr 应该接在链表末尾，不需要从头扫描。这在输入数据已经基本有序时，可以把大量 $O(n)$ 的扫描降为 $O(1)$。

public ListNode insertionSortList(ListNode head) {
    ListNode dummy = new ListNode(Integer.MIN_VALUE);
    ListNode lastSorted = dummy;  // 追踪已排序链表的末尾节点
    ListNode curr = head;
 
    while (curr != null) {
        ListNode next = curr.next;
        if (curr.val >= lastSorted.val) {
            // 当前节点比已排序末尾还大，直接接在末尾
            lastSorted.next = curr;
            lastSorted = lastSorted.next;
        } else {
            // 需要找插入位置
            ListNode prev = dummy;
            while (prev.next.val < curr.val) prev = prev.next;
            curr.next = prev.next;
            prev.next = curr;
        }
        curr = next;
    }
    lastSorted.next = null;  // 末尾节点的 next 可能指向旧链表的某个节点，需要断开
    return dummy.next;
}

---

第 3 章 LeetCode 148：链表归并排序

3.1 题目

LeetCode 148 - Sort List（中等）

给你链表的头节点 head，请你将链表升序排列后返回排序后的链表。

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

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

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

3.2 自顶向下递归归并排序（O(log n) 空间）

算法步骤：

1. 找到链表中点，将链表从中点切断，分成左右两半
2. 递归对左右两半分别排序
3. 合并两个有序链表

关键子程序一：快慢指针找中点

private ListNode findMid(ListNode head) {
    ListNode slow = head, fast = head.next;
    // fast.next != null 确保 fast 不会越界
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    // slow 停在链表的前半段末尾（偶数长度取左中点）
    return slow;
}

为什么 fast = head.next 而不是 fast = head？这是为了处理”两节点链表”的情况：如果 fast = head，那么 fast.next.next = null，循环不执行，slow 停在 head，找到的”中点”是第一个节点，切割后左半部分是 [head]，右半部分是 [head.next]。这没问题，但如果 fast = head.next，更自然地处理了 $n=2$ 的基础情况。

关键子程序二：在 mid 处切断链表

ListNode mid = findMid(head);
ListNode rightHead = mid.next;
mid.next = null;  // 切断！

mid.next = null 是关键的一步。不切断的话，左半部分的末尾仍然指向右半部分的第一个节点，递归就无法正确处理独立的子链表。

完整代码：

public ListNode sortList(ListNode head) {
    // 基础情况：空链表或只有一个节点，已有序
    if (head == null || head.next == null) return head;
 
    // 第一步：找中点，切断
    ListNode mid = findMid(head);
    ListNode rightHead = mid.next;
    mid.next = null;
 
    // 第二步：递归排序左右两半
    ListNode left = sortList(head);
    ListNode right = sortList(rightHead);
 
    // 第三步：合并两个有序链表
    return merge(left, right);
}
 
private ListNode findMid(ListNode head) {
    ListNode slow = head, fast = head.next;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}
 
private ListNode merge(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
        else { curr.next = l2; l2 = l2.next; }
        curr = curr.next;
    }
    curr.next = (l1 != null) ? l1 : l2;
    return dummy.next;
}

复杂度分析：

• 时间：$O(n\log n)$，递归树共 $\log n$ 层，每层处理 $O(n)$ 的数据
• 空间：$O(\log n)$，递归调用栈的深度

这个方案已经很好，但还没有达到题目进阶要求的 $O(1)$ 额外空间（递归栈占 $O(\log n)$ 空间）。

3.3 自底向上迭代归并排序（O(1) 空间）

递归版本的空间来自调用栈。要消除递归，需要改用迭代版本，也就是**自底向上（Bottom-Up）**的归并排序。

自底向上的思路：

递归版是从整个链表分成两半，再分四份，以此类推，直到每份只有一个节点，然后回溯合并。自底向上则反过来：

• 第 1 轮：把链表每 1 个节点当作一个有序段，相邻的两个段合并 → 得到若干长度 2 的有序段
• 第 2 轮：每 2 个节点一段，相邻的两段合并 → 得到若干长度 4 的有序段
• 第 3 轮：每 4 个节点一段 → 得到若干长度 8 的有序段
• …
• 第 $\log n$ 轮：每 $n/2$ 个节点一段，合并两段 → 得到完整有序链表

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
 
    // 先求链表总长度
    int length = 0;
    ListNode node = head;
    while (node != null) { length++; node = node.next; }
 
    ListNode dummy = new ListNode(0);
    dummy.next = head;
 
    // subLen: 当前轮次每个子链表的长度，从 1 开始，每轮翻倍
    for (int subLen = 1; subLen < length; subLen <<= 1) {
        ListNode prev = dummy;  // 上一段合并结果的末尾（用于接下一段）
        ListNode curr = dummy.next;  // 当前处理位置
 
        while (curr != null) {
            // 切出第一段（长度 subLen）
            ListNode head1 = curr;
            ListNode head2 = split(head1, subLen);  // head2 是第二段的起点
            curr = split(head2, subLen);             // curr 是下一组的起点
 
            // 合并 head1 和 head2
            ListNode merged = merge(head1, head2);
 
            // 把合并结果接到已处理的末尾
            prev.next = merged;
            while (prev.next != null) prev = prev.next;  // prev 移到新的末尾
        }
    }
 
    return dummy.next;
}
 
// 从 head 开始切出 n 个节点，返回第 n+1 个节点（后继链表头）
// 同时将第 n 个节点的 next 设为 null（切断）
private ListNode split(ListNode head, int n) {
    for (int i = 1; i < n && head != null; i++) {
        head = head.next;
    }
    if (head == null) return null;
    ListNode rest = head.next;
    head.next = null;  // 切断
    return rest;
}

复杂度分析：

• 时间：$O(n\log n)$，共 $\log n$ 轮，每轮处理 $O(n)$ 的数据
• 空间：$O(1)$，只使用常数个额外指针，没有递归调用栈

3.4 两种方案的详细对比

维度	自顶向下（递归）	自底向上（迭代）
时间复杂度	$O(n\log n)$	$O(n\log n)$
空间复杂度	$O(\log n)$	$O(1)$ ✅
实现难度	⭐⭐（中等，逻辑清晰）	⭐⭐⭐（较难，指针操作多）
面试推荐度	✅ 大多数情况足够	✅ 追求 $O(1)$ 空间时
代码可读性	好（递归结构直观）	一般（迭代步骤较多）

面试建议：先写递归版本，然后主动告知面试官”如果需要 $O(1)$ 空间，可以用自底向上的迭代实现”，并能说清楚迭代版本的核心思路。这样既展示了解题能力，也展示了工程素养。

设计哲学：自顶向下 vs 自底向上

递归（自顶向下）天然符合人类的思维方式：把大问题分解成小问题，递归解决，然后合并结果。它的代价是调用栈空间。 迭代（自底向上）则像工厂流水线：从最小单元开始，逐步合并成更大的单元，直到处理完整个数据集。它没有调用栈的开销，但需要显式管理”当前处理到哪里”的状态，逻辑更复杂。 这种权衡在很多算法问题上都会出现：递归版本易写难优化空间，迭代版本代码复杂但空间最优。

---

第 4 章 链表排序的综合对比与面试策略

4.1 插入排序 vs 归并排序

维度	插入排序（LeetCode 147）	归并排序（LeetCode 148）
时间复杂度	$O(n^2)$	$O(n\log n)$
空间复杂度	$O(1)$	$O(\log n)$ / $O(1)$（迭代）
适用场景	链表近似有序时，接近 $O(n)$	通用，性能稳定
实现难度	⭐⭐	⭐⭐（递归）/ ⭐⭐⭐（迭代）

何时用链表插入排序？ 当链表”基本有序”时，插入排序的最好情况接近 $O(n)$，且常数因子小，可能比归并排序更快。但在不知道输入特征的通用场景下，归并排序总是更优的选择。

4.2 LeetCode 147 的常见错误

错误 1：忘记 lastSorted.next = null

在带优化的插入排序版本中，当某个节点被接在末尾后，其 next 可能仍然指向原始链表的下一个节点（那个节点可能已经被插入到已排序链表的中间）。如果不在最后设置 lastSorted.next = null，已排序链表末尾会形成一个环或指向错误节点。

错误 2：找插入位置时条件写错

// 错误：应该是严格小于，而不是小于等于
while (prev.next.val <= curr.val) prev = prev.next;
 
// 正确：找到第一个 >= curr.val 的节点的前驱
while (prev.next != null && prev.next.val < curr.val) prev = prev.next;

如果用 <=，相等元素会被插到所有相同值的后面，虽然最终结果仍然有序，但改变了相等元素的相对顺序（破坏了稳定性）。

4.3 LeetCode 148 的常见错误

错误 1：忘记切断链表

// 必须在递归前切断！
mid.next = null;  // 绝对不能漏
ListNode left = sortList(head);
ListNode right = sortList(rightHead);

如果不切断，左半部分链表的末尾仍然连着右半部分，sortList(head) 会递归处理整个链表，无限循环（或者结果不正确）。

错误 2：快慢指针找中点后，slow 的位置不对

不同的写法，slow 的停止位置不同：

// 写法 A：fast = head（slow 停在右中点，偶数长度取右中点）
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }
 
// 写法 B：fast = head.next（slow 停在左中点，偶数长度取左中点）
ListNode slow = head, fast = head.next;
while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; }

两种写法都能工作，但需要和后续的切断逻辑对应。推荐写法 B，因为它对两节点链表的处理更自然。

---

小结

本文深入讲解了链表排序的两种实现：

1. 链表插入排序（LeetCode 147）：核心是在已排序链表中找插入位置，用哑节点消除头节点特判，带末尾节点优化的版本对近似有序数据性能更好。时间 $O(n^2)$，空间 $O(1)$。

2. 链表归并排序（LeetCode 148）：分三个子步骤——快慢指针找中点、切断链表、合并有序链表。递归版本 $O(\log n)$ 空间，迭代（自底向上）版本 $O(1)$ 空间。面试中推荐先写递归版，再补充说明迭代版的思路。

链表排序的核心技巧：找中点用快慢指针，合并用哑节点 + 双指针，切断要显式设 null，迭代用自底向上按步长翻倍。

---

上一篇：02 归并排序实战三连：有序数组与有序链表的合并艺术 下一篇：04 创意排序：荷兰国旗问题与桶排序思想