LeetCode 23：合并 K 个升序链表（Merge k Sorted Lists）题解

Merge k Sorted Lists 是 LeetCode Hot 100 里面一道非常经典的链表题。

如果说前面的“合并两个有序链表”是在训练我们如何处理两个链表之间的有序合并，那么这道题就是在它的基础上继续升级： 不再只给两个链表，而是直接给出 k 个升序链表，要求把它们合并成一个新的升序链表。

这道题如果直接硬做，其实并不难想到思路；但真正的关键在于： 面对多个有序链表，我们该如何高效地每次找到当前最小的那个结点。

你给出的这份 Java 代码，使用的是这道题最常见、也非常高效的一种解法：

优先队列（最小堆）

这种写法思路清晰，代码也相对稳定，是面试和刷题中都非常推荐掌握的一种方案。本文就结合这段代码，系统地讲一下这道题的思路。

题目介绍

给你一个链表数组 lists，其中每个链表都已经按升序排列。

现在要求把这些链表合并成一个新的升序链表，并返回合并后的头结点。

例如：

lists = [
  1->4->5,
  1->3->4,
  2->6
]

合并之后应该得到：

1->1->2->3->4->4->5->6

题目本质上是在问：

如何把多个有序链表整合成一个更大的有序链表？

示例

示例 1

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]

因为三个链表本身都是有序的，所以每次只要把当前所有候选结点中的最小值取出来，接到结果链表后面即可。

示例 2

输入：lists = []
输出：[]

链表数组为空，自然返回空链表。

示例 3

输入：lists = [[]]
输出：[]

数组里有一个链表，但这个链表本身为空，所以最终结果依然是空链表。

最直接的想法是什么？

看到这道题，很多人第一个想到的思路可能是：

• 先把所有链表里的所有结点值都取出来

• 放到数组里统一排序

• 再根据排序结果重新构造一个新链表

这个方法理论上当然可以做出来，但问题很明显：

1. 没有充分利用“每个链表本身已经有序”这个条件

2. 需要额外存储所有节点值

3. 重新构造链表也会增加额外操作

所以这并不是最优思路。

既然每个链表本身都是升序的，我们就应该尽量利用这个性质，避免做多余工作。

从“两两合并”可以做吗？

也可以。

一个比较自然的想法是：

• 先合并前两个链表

• 再把结果和第三个链表合并

• 再把新结果和第四个链表合并

• 依次类推

这种方法是可行的，但效率未必最好。

因为每次合并都会重复扫描已经合并好的长链表。 如果链表很多，这种写法整体代价就会比较高。

所以这道题更常见的优化方式有两种：

1. 分治合并

2. 优先队列（最小堆）

而你这份代码采用的是第二种。

核心思路：优先队列 / 最小堆

这道题最关键的问题是：

在多个链表当前头结点中，如何快速找到最小的那个？

如果我们每次都手动遍历 k 个链表头去找最小值，那每一步都要花 O(k) 的时间，效率不够高。

而最小堆正好非常适合解决这种“动态维护当前最小值”的问题。

具体做法

1. 先把每个非空链表的头结点放入最小堆

2. 每次从堆中弹出最小结点

3. 把这个结点接到结果链表后面

4. 如果这个结点后面还有下一个结点，就把它的 next 再放回堆中

5. 重复这个过程，直到堆为空

这样就能始终保证：

每一次取出来的，都是当前所有候选结点中的最小值。

Java 代码

下面是你给出的代码，我这里保留原始逻辑，并加上注释：

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 最小堆，按照结点值从小到大排列
        PriorityQueue<ListNode> queue = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);
​
        // 把每个非空链表的头结点加入堆中
        for (ListNode list : lists) {
            if (list != null) queue.add(list);
        }
​
        // 哑结点，方便构造结果链表
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
​
        // 不断取出当前最小结点
        while (!queue.isEmpty()) {
            ListNode minNode = queue.poll();
​
            // 接到结果链表后面
            tail.next = minNode;
            tail = tail.next;
​
            // 如果这个结点还有下一个结点，就继续加入堆中
            if (minNode.next != null) queue.add(minNode.next);
        }
​
        tail.next = null;
        return dummy.next;
    }
}

代码拆解

这段代码整体不算长，但如果没有理解优先队列在这里扮演的角色，第一次看还是容易有点抽象。 下面一步一步来看。

1. 为什么使用优先队列？

PriorityQueue<ListNode> queue = new PriorityQueue<>((n1, n2) -> n1.val - n2.val);

优先队列本质上就是一个堆结构。

这里我们定义的是一个 最小堆，规则是：

• 结点值小的，优先级更高

• 每次 poll() 时，都会弹出当前最小的结点

而这正好符合题目的需求：

我们每次都想从多个链表当前候选结点中拿到最小的那个。

所以最小堆在这里非常合适。

为什么比较规则写成 n1.val - n2.val？

因为我们要按结点值从小到大排序。

当：

• n1.val < n2.val 时，返回负数，说明 n1 优先级更高

• n1.val > n2.val 时，返回正数，说明 n2 更靠前

这就是堆中元素排序的依据。

2. 为什么只把每个链表的头结点放进去？

for (ListNode list : lists) {
    if (list != null) queue.add(list);
}

这是这道题一个非常重要的技巧。

我们并不需要一开始就把所有结点都放进堆里。 只需要把每个链表当前“最前面那个候选结点”放进去就够了。

为什么这样就够？

因为每个链表本身已经有序。 如果某个链表当前头结点还没被取出来，那它后面的结点一定不会比它更小。

所以当前时刻，这个链表真正有资格参与全局最小值竞争的，只会是它的头结点。

这就是为什么初始时只放每条链表的头。

3. dummy 和 tail 的作用是什么？

ListNode dummy = new ListNode(0);
ListNode tail = dummy;

这和很多链表构造题一样，都是标准套路。

• dummy 是哑结点，用来统一处理结果链表的头部

• tail 始终指向当前结果链表的最后一个结点

每次从堆里取出一个最小结点后，就把它接到 tail.next 上，然后让 tail 往后移动一位。

这样就能一步步把结果链表构造出来。

4. 为什么从堆里弹出最小结点后，还要把它的 next 加回堆中？

ListNode minNode = queue.poll();
...
if (minNode.next != null) queue.add(minNode.next);

这是整道题最核心的地方。

假设某次从堆里弹出了某个链表的当前头结点 minNode，那么说明这个结点已经被接入结果链表了。 接下来，这个链表还能继续参与竞争的结点是谁？

答案当然就是它的下一个结点：

minNode.next

因为原链表是升序的，所以在当前结点被取走之后，下一个结点自然就成了这个链表新的“候选头结点”。

所以我们要把它放入堆中，让它继续和其他链表的当前头结点一起竞争最小值。

整个过程其实就像是在不断维护：

每条链表当前最靠前的那个未处理结点。

5. 为什么最后要写 tail.next = null？

tail.next = null;

严格来说，这一句很多时候不是必须的，但加上它会更稳妥。

因为我们是在原链表节点基础上直接拼接结果链表。 当 tail 最终停在结果链表最后一个结点时，把它的 next 显式设成 null，可以避免某些情况下意外保留旧引用，保证链表尾部干净结束。

这是一个比较稳妥的细节处理。

手动模拟一遍

我们用经典样例来走一遍：

lists = [
  1->4->5,
  1->3->4,
  2->6
]

初始状态

先把每个链表头结点放入最小堆：

• 1(第一条链表)

• 1(第二条链表)

• 2(第三条链表)

此时堆顶最小值是 1。

第一次弹出

弹出最小结点 1，接到结果链表后面。

结果链表变成：

1

然后把这个 1 所在链表的下一个结点 4 放入堆中。

此时堆中有：

• 1

• 2

• 4

第二次弹出

再弹出最小结点 1，接到结果链表后面：

1 -> 1

然后把这个 1 后面的 3 放入堆中。

此时堆中有：

• 2

• 3

• 4

第三次弹出

弹出 2，结果链表变成：

1 -> 1 -> 2

然后把 2 后面的 6 放入堆中。

此时堆中有：

• 3

• 4

• 6

后面重复这个过程，最终结果就是：

1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

这正是题目要求的答案。

为什么这个方法是正确的？

因为在任意时刻，堆中保存的都是每条链表当前“最前面还没处理的结点”。

而每条链表本身都是升序的，所以：

• 每条链表里，当前头结点一定是这条链表剩余部分中最小的

• 把所有链表当前头结点放在一起时，堆顶元素就一定是整个全局最小值

也就是说， 每次从堆里弹出一个元素，都是在全局范围内选出了当前最小结点。

因此，按这个顺序把结点依次接到结果链表后面，最终得到的链表一定也是升序的。

复杂度分析

假设：

• 一共有 k 个链表

• 所有链表总结点数为 N

时间复杂度

每个结点都会：

• 最多进入堆一次

• 最多弹出堆一次

而堆的插入和删除操作时间复杂度都是：

O(log k)

所以总时间复杂度是：

O(N log k)

这也是这道题使用最小堆解法的最大优势。

空间复杂度

堆中同时最多存放 k 个结点（每个链表最多一个当前候选头结点），所以额外空间复杂度是：

O(k)

这道题真正想考什么？

这道题表面上是在考链表合并，但本质上是在考两个核心能力。

第一，是否能识别“多路有序合并”问题

只要题目中出现：

• 多个有序序列

• 每次都要取当前最小值

• 动态维护候选集合

这种场景时，就应该联想到：

优先队列 / 最小堆

这类题的思维模型非常常见，不只是链表，在数组、流式数据处理、Top K 问题里也会反复遇到。

第二，是否能利用“局部最优”构造全局有序结果

因为每条链表本身有序，所以每次只看每条链表当前头结点就够了。 这说明题目里的“有序性”并不是摆设，而是我们设计算法的关键突破口。

和“合并两个有序链表”有什么关系？

这两题其实是强相关的。

合并两个有序链表

只需要在两个当前头结点中选较小的一个。

合并 K 个有序链表

本质上也是一样，只不过候选集合从 2 个变成了 k 个。 当候选对象变多时，手动比较已经不划算了，所以要用最小堆来帮助我们快速找到当前最小值。

所以你可以把这题理解成：

把“两路归并”扩展成“多路归并”。

这是一个很自然的升级过程。

总结

这道题的核心思路可以概括成一句话：

用最小堆动态维护所有链表当前头结点，每次取出最小值接到结果链表中。

完整流程就是：

1. 把所有非空链表的头结点加入最小堆

2. 每次弹出堆顶最小结点

3. 接到结果链表后面

4. 如果该结点还有下一个结点，就把它的 next 放入堆中

5. 重复直到堆为空

这样就能在：

O(N log k)

的时间复杂度内完成合并。

这是一道非常经典的“链表 + 堆”题。 如果你正在系统刷 LeetCode Hot 100，这题非常值得掌握。因为它不仅本身高频，而且能帮你建立对“多路合并”和“优先队列”的直觉。

把这道题真正理解透之后，再去看：

• 合并多个有序数组

• 数据流中的第 K 大元素

• Top K 高频元素

• 堆排序相关问题

你都会更容易抓住核心。

因为“合并 K 个升序链表”，本质上就是一道非常标准的最小堆应用题。