02 归并排序实战三连：有序数组与有序链表的合并艺术

归并排序实战三连：有序数组与有序链表的合并艺术

摘要

“合并有序序列”是归并排序的核心子操作，也是面试中出现频率极高的一组题型。本文通过三道由易到难的经典题目，深度剖析”归并”这个操作的所有变体：合并两个有序数组（原地操作的倒序技巧）、合并两个有序链表（哑节点 + 双指针）、合并 k 个有序链表（优先队列多路归并 vs 分治二路归并）。每道题不只给答案，而是推导为什么这么做，以及为什么其他思路不行。

---

第 1 章 归并操作的本质

1.1 双指针归并：有序性带来的礼物

“合并两个有序序列”是一个典型的”利用有序性降低复杂度”的例子。如果没有有序性，合并两个各有 $m$ 和 $n$ 个元素的序列，最快也要 $O((m+n)\log (m+n))$（建立新序列然后排序）。但有了有序性，我们只需线性时间：

核心思路：维护两个指针，分别指向两个序列的当前位置，每次从两个指针所指的元素中取较小的那个放入结果，然后推进对应指针。

序列 A：[1, 3, 5, 7]
序列 B：[2, 4, 6, 8]

i=0, j=0: A[0]=1 < B[0]=2, 取 1, i→1
i=1, j=0: A[1]=3 > B[0]=2, 取 2, j→1
i=1, j=1: A[1]=3 < B[1]=4, 取 3, i→2
...

这个过程的时间复杂度是 $O(m+n)$，每一步只做一次比较，逻辑极为简洁。这就是”有序性”的价值：它让我们在每一步都能做出确定性的选择，无需回头查找。

1.2 三道题的难度梯度

题目	核心难点	关键技巧
Merge Sorted Array（88）	原地合并，不能开新数组	从后往前写，避免覆盖
Merge Two Sorted Lists（21）	链表指针管理	哑节点消除边界特判
Merge k Sorted Lists（23）	$k$ 路合并的效率	优先队列 / 分治归并

---

第 2 章 LeetCode 88：合并两个有序数组

2.1 题目

LeetCode 88 - Merge Sorted Array（简单）

给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n，分别表示 nums1 和 nums2 中的元素数目。请你合并 nums2 到 nums1 中，使合并后的数组同样按非递减顺序排列。

注意：最终合并后的数组不应由函数返回，而应存储在数组 nums1 中。为此，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0，应被忽略。

输入: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]

输入: nums1 = [1], m = 1, nums2 = [], n = 0
输出: [1]

2.2 为什么正向合并不行

第一直觉：两个指针 i=0、j=0，每次取较小的写到 nums1[k]，然后 k++。

问题：写入 nums1[k] 时，会覆盖 nums1[k] 原来存放的有效数据！

举例：nums1 = [1, 2, 3, 0, 0, 0]，当我们把 nums2[0]=2 写入 nums1[1] 时，原来 nums1[1]=2 被覆盖。虽然这个例子中值相同没有问题，但如果 nums1 = [3, 5, 7, 0, 0, 0] 和 nums2 = [1, 2, 4]，当写入 nums2[0]=1 到 nums1[0] 时，原来 nums1[0]=3 丢失了，后续就无法正确继续。

根本矛盾：正向合并时，“写入区域”和”待读取区域”有重叠，写入会破坏待读取数据。

2.3 逆向合并：从后往前写

突破口在于：nums1 的尾部（下标 m 到 m+n-1）存放的全是 0，是空闲空间。如果从后往前写入，写入的位置始终在未读取区域的后面，不会产生覆盖。

算法设计：

• 三个指针：i = m-1（指向 nums1 最后一个有效元素）、j = n-1（指向 nums2 最后一个元素）、k = m+n-1（指向写入位置）
• 每次比较 nums1[i] 和 nums2[j]，取较大的写入 nums1[k]，对应指针左移
• 当 j < 0（nums2 已全部处理），结束（nums1 剩余部分本来就在原位）
• 当 i < 0（nums1 有效部分已全部处理），将 nums2 的剩余部分复制到 nums1[0..j]

public void merge(int[] nums1, int m, int[] nums2, int n) {
    int i = m - 1;      // nums1 有效部分的末尾
    int j = n - 1;      // nums2 的末尾
    int k = m + n - 1;  // 写入位置（从末尾开始）
 
    while (i >= 0 && j >= 0) {
        if (nums1[i] >= nums2[j]) {
            nums1[k--] = nums1[i--];  // nums1 当前元素更大，取它
        } else {
            nums1[k--] = nums2[j--];  // nums2 当前元素更大，取它
        }
    }
 
    // nums1 的有效部分已用完，把 nums2 剩余的搬进来
    // 如果是 nums2 先用完，nums1 剩余部分无需移动（本就在 nums1 里）
    while (j >= 0) {
        nums1[k--] = nums2[j--];
    }
}

复杂度分析：

• 时间：$O(m+n)$，每个元素恰好被处理一次
• 空间：$O(1)$，原地操作，无额外空间

2.4 不变量验证

循环不变量：在每次循环迭代结束后，nums1[k+1..m+n-1] 区域存放的是所有已处理元素中最大的 $m+n-1-k$ 个，且有序。

初始状态（k = m+n-1，尚未处理任何元素）：nums1[m+n..m+n-1] 是空区间，不变量成立。每次迭代后：我们取了 nums1[i] 和 nums2[j] 中的较大者写入 nums1[k]，不变量依然成立。循环结束时，k 已经走完整个数组，不变量告诉我们 nums1[0..m+n-1] 已经有序。

生产避坑：为什么只需处理 j≥0 的情况

当循环因 i < 0 结束时，nums2[0..j] 都还没处理。把它们依次填入 nums1[0..k] 即可。 当循环因 j < 0 结束时，nums1[0..i] 都还没处理。但它们本来就在 nums1 的前段，而且 nums2 已全部是比 nums1[k+1..m+n-1] 小的元素，所以 nums1[0..i] 的元素已经在正确位置了，无需移动。

---

第 3 章 LeetCode 21：合并两个有序链表

3.1 题目

LeetCode 21 - Merge Two Sorted Lists（简单）

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

输入: l1 = 1->2->4, l2 = 1->3->4
输出: 1->1->2->3->4->4

输入: l1 = [], l2 = []
输出: []

3.2 哑节点（Dummy Node）的价值

链表题的难点通常不在逻辑本身，而在于边界条件的处理：当链表为空时怎么办？当第一个节点就要插入时怎么办？

直觉写法（不用哑节点）：

// 需要单独处理头节点
ListNode head;
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val <= l2.val) {
    head = l1;
    l1 = l1.next;
} else {
    head = l2;
    l2 = l2.next;
}
ListNode curr = head;
while (l1 != null && l2 != null) {
    // ...
}

这段代码里，确定头节点的逻辑单独写了一遍，然后主循环又写了一遍——代码结构不统一，容易出错。

哑节点技巧：引入一个值任意的虚拟头节点 dummy，curr 从 dummy 出发。这样主循环可以统一处理所有节点（包括第一个），最后返回 dummy.next 即可。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);  // 哑节点，值无关紧要
    ListNode curr = dummy;             // curr 始终指向已合并链表的末尾
 
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            curr.next = l1;   // 把 l1 当前节点接到已合并链表
            l1 = l1.next;     // l1 前进
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;     // curr 跟进
    }
 
    // 其中一个链表已处理完，把另一个的剩余部分直接接上
    curr.next = (l1 != null) ? l1 : l2;
 
    return dummy.next;  // dummy.next 就是合并后链表的真实头节点
}

复杂度分析：

• 时间：$O(m+n)$，每个节点只被访问一次
• 空间：$O(1)$，只使用了常数个额外指针（注意：是复用原链表的节点，没有创建新节点）

3.3 递归版本：另一种视角

有些人更喜欢递归版本，因为它直接反映了”合并”的递推定义：两个链表中头节点较小的那个，其 next 指向”另一个链表的头节点”和”自己的 next 合并后的结果”。

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;  // 其中一个为空，返回另一个
    if (l2 == null) return l1;
 
    if (l1.val <= l2.val) {
        l1.next = mergeTwoLists(l1.next, l2);  // l1 的头更小，取它
        return l1;
    } else {
        l2.next = mergeTwoLists(l1, l2.next);  // l2 的头更小，取它
        return l2;
    }
}

递归版本代码极为简洁，但有一个潜在问题：递归深度是 $O(m+n)$，对于非常长的链表（如 $10^5$ 个节点），可能导致栈溢出。面试中推荐使用迭代版本。

设计哲学：哑节点消除边界特判

哑节点（Dummy Node）是链表题中最重要的编程技巧之一。它的本质是：将”处理第一个节点”和”处理后续节点”统一成同一段逻辑，避免讨论”链表是否为空”或”是否要特殊处理头节点”。凡是需要”动链表头部”的操作，几乎都应该第一时间想到哑节点。

---

第 4 章 LeetCode 23：合并 K 个有序链表

4.1 题目

LeetCode 23 - Merge k Sorted Lists（困难）

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

输入: lists = [[1,4,5],[1,3,4],[2,6]]
输出: 1->1->2->3->4->4->5->6

输入: lists = []
输出: []

4.2 朴素思路的瓶颈

思路一：顺序两两合并

依次将 lists[0] 和 lists[1] 合并，结果再和 lists[2] 合并，以此类推。

设每个链表有 $n$ 个元素，共 $k$ 个链表。

• 第 1 次合并：lists[0]（$n$ 个）+ lists[1]（$n$ 个）= 耗时 $O(2n)$
• 第 2 次合并：结果（$2n$ 个）+ lists[2]（$n$ 个）= 耗时 $O(3n)$
• …
• 第 $k-1$ 次合并：结果（$(k-1)n$ 个）+ lists[k-1]（$n$ 个）= 耗时 $O(kn)$

总时间：$O(2n+3n+\cdots +kn)=O(kn\cdot \frac{k+2}{2})=O(k^{2}n)$。

当 $k$ 很大时（如 $k=10000$，$n=1000$），这是 $10^{11}$ 的操作量，完全不可接受。

问题根源：第一个链表的每个元素被合并了 $k-1$ 次，被反复”拖着走”。

4.3 解法一：优先队列（最小堆）

核心思路：维护一个大小为 $k$ 的最小堆，堆中始终存放每个链表当前的”候选头节点”。每次从堆中取出最小节点，接入结果链表，然后把该节点的 next（如果存在）重新入堆。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
 
    // 最小堆，按节点值排序
    PriorityQueue<ListNode> pq = new PriorityQueue<>(
        lists.length,
        (a, b) -> a.val - b.val
    );
 
    // 初始化：把每个链表的头节点加入堆
    for (ListNode node : lists) {
        if (node != null) pq.offer(node);
    }
 
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
 
    while (!pq.isEmpty()) {
        ListNode smallest = pq.poll();  // 取出堆中最小节点
        curr.next = smallest;
        curr = curr.next;
        if (smallest.next != null) {
            pq.offer(smallest.next);    // 把该节点的后继加入堆
        }
    }
 
    return dummy.next;
}

复杂度分析：

• 每个节点恰好入堆一次、出堆一次，每次堆操作 $O(\log k)$（堆大小始终不超过 $k$）
• 总时间：$O(N\log k)$，$N$ 是所有节点总数，$k$ 是链表数量
• 空间：$O(k)$（堆的大小）

为什么这比顺序合并好？ 顺序合并是 $O(k^{2}n)=O(kN)$（$N=kn$），而优先队列是 $O(N\log k)$。当 $k$ 很大时，$\log k\ll k$，优先队列有本质性的改进。

4.4 解法二：分治归并

核心思路：将 $k$ 个链表两两配对合并，得到 $k/2$ 个链表；再两两配对，得到 $k/4$ 个；以此类推，共 $\log k$ 轮。这正是归并排序的分治结构。

public ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return mergeRange(lists, 0, lists.length - 1);
}
 
private ListNode mergeRange(ListNode[] lists, int left, int right) {
    if (left == right) return lists[left];  // 只剩一个，直接返回
    int mid = left + (right - left) / 2;
    ListNode l1 = mergeRange(lists, left, mid);      // 左半部分归并结果
    ListNode l2 = mergeRange(lists, mid + 1, right); // 右半部分归并结果
    return mergeTwoLists(l1, l2);                    // 合并两个有序链表
}
 
// 复用第 3 章的 mergeTwoLists 方法
private ListNode mergeTwoLists(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;
}

复杂度分析：

• 共 $\log k$ 轮，每轮所有节点合计被处理 $O(N)$ 次
• 总时间：$O(N\log k)$
• 空间：$O(\log k)$（递归栈深度）

两种解法的对比：

维度	优先队列	分治归并
时间复杂度	$O(N\log k)$	$O(N\log k)$
空间复杂度	$O(k)$	$O(\log k)$
实现难度	简单（Java 直接用 PriorityQueue）	中等（需要递归）
在线处理	✅ 适合流式输入（边输入边合并）	❌ 需要预知所有链表
缓存局部性	较好（每次操作都在堆顶附近）	较好（递归合并局部性好）

面试中两种解法都可以，优先队列实现更直观，分治归并空间更优。

4.5 为什么不能用暴力法？

暴力法：把所有节点的值收集到数组里，排序，然后重建链表。

// 暴力法示意
List<Integer> vals = new ArrayList<>();
for (ListNode list : lists)
    while (list != null) { vals.add(list.val); list = list.next; }
Collections.sort(vals);
// 重建链表...

时间复杂度：$O(N\log N)$，看起来和优先队列的 $O(N\log k)$ 差不多，但有两个问题：

1. 需要 $O(N)$ 的额外空间（把所有节点值存到数组）
2. 没有利用”已有序”这个关键信息，$\log N$ 而不是 $\log k$，当 $k\ll N$ 时差距明显

核心概念：多路归并（k-way merge）

合并 $k$ 个有序序列，是数据库和大数据系统中极其常见的操作。数据库的外部排序（数据不能全装入内存时）、Hadoop 的归并阶段，本质上都是多路归并。实际系统中通常使用优先队列实现，因为它天然支持流式处理（边读边归并）。

---

第 5 章 三道题的横向比较与面试策略

5.1 核心技巧汇总

题目	核心难点	突破口
Merge Sorted Array	原地操作，正向写入会覆盖数据	从后往前写，利用尾部空闲区域
Merge Two Sorted Lists	链表头节点的特殊处理	哑节点，统一所有节点的处理逻辑
Merge k Sorted Lists	$k$ 个候选，如何高效找最小	优先队列维护候选集 / 分治降为两路归并

5.2 常见面试追问

Q：Merge Sorted Array 能不能不从后往前？

可以，但必须借助额外空间：先把 nums1 的有效部分复制到辅助数组，再正向双指针合并。代价是 $O(m)$ 的额外空间。面试中这种方案会被追问”能不能 $O(1)$ 空间”，然后引出从后往前的解法。

Q：Merge k Sorted Lists 中，优先队列里存什么？

存链表的节点引用（ListNode），而不是节点的值。因为我们需要通过节点找到其 next，只存值的话无法遍历链表。

Q：如果 k 个链表都是空链表怎么办？

• 优先队列方案：初始化时只把非空链表的头节点加入堆，循环结束后直接返回 dummy.next，天然处理了空链表的情况。
• 分治方案：递归到 left == right 时返回 lists[left]，如果 lists[left] 本身是 null，也没问题（mergeTwoLists(null, someList) 会直接返回 someList）。

---

小结

本文深入讲解了归并操作的三个典型变体：

1. Merge Sorted Array（原地合并数组）：关键是逆向双指针，利用 nums1 尾部空闲空间，从后往前写入，避免覆盖已有数据。时间 $O(m+n)$，空间 $O(1)$。

2. Merge Two Sorted Lists（合并两个有序链表）：关键是哑节点技巧，消除头节点的特殊处理。时间 $O(m+n)$，空间 $O(1)$。

3. Merge k Sorted Lists（合并 $k$ 个有序链表）：两种 $O(N\log k)$ 的优化方案——最小堆优先队列（适合流式处理，实现简单）和分治归并（空间更优，代码递归优雅）。

这三道题是面试中”排序与合并”主题的必考内容，建议在 LeetCode 上依次刷完后，尝试独立实现不带任何注释的完整代码，确保对每个细节都真正理解而不是靠记忆。

---

上一篇：01 排序算法原理全景：从 O(n²) 到 O(nlogn) 的演进之路 下一篇：03 链表排序双题精讲：插入排序与归并排序的链表实现