在链表题中，“合并两个升序链表”属于基础题，而“合并 K 个升序链表”则进一步考查我们如何从多个候选节点中快速找到最小值。
如果每次都遍历 K 条链表寻找最小节点，当然可以完成合并，但效率并不理想。更合适的做法是使用 PriorityQueue 构造小顶堆，让当前最小节点始终位于堆顶。
本文以 LeetCode 23 为例，讲清楚小顶堆解法的思考过程、Java 实现、复杂度，以及面试中常见的易错点。
一、题目描述
给定一个链表数组，每条链表都已经按照升序排列，请将所有链表合并为一条升序链表，并返回合并后的头节点。
例如：
输入：lists = [[1,4,5], [1,3,4], [2,6]]
输出：[1,1,2,3,4,4,5,6]
三条链表分别为：
1 → 4 → 5
1 → 3 → 4
2 → 6
由于每条链表内部已经有序，我们不需要把所有节点一次性取出再排序。真正需要解决的问题是：在每一步中，怎样快速找到所有剩余节点里的最小值？
二、最直接的思路为什么不够好
假设当前有 K 条链表，每次从它们的头节点中遍历寻找最小值，然后把该节点接到结果链表后面。
如果所有链表一共有 N 个节点，那么每加入一个节点，最坏情况下都需要比较 K 次，因此时间复杂度为：
O(NK)
当 K 较小时，这种方案可以使用；但如果要合并几百甚至几千条链表，重复扫描 K 个候选节点会造成明显浪费。
我们需要一种数据结构，能够快速返回当前最小的头节点，这正是小顶堆擅长解决的问题。
三、为什么可以使用小顶堆
小顶堆具有两个重要特点：
-
堆顶始终是当前最小元素；
-
插入和删除堆顶的时间复杂度均为
O(log K)。
一开始，我们只需要把每条非空链表的头节点放入小顶堆。每次从堆中弹出最小节点，将它连接到结果链表后面；如果该节点还有下一个节点，就把它的下一个节点加入堆中。
这里有一个关键问题：为什么每条链表只放一个节点就够了？
因为每条链表本身已经升序排列。假设某条链表当前的头节点是 1，后面是 4、5，那么在 1 被取出之前，4 和 5 不可能成为全局最小值。只有取出 1 后，4 才有资格参与下一轮比较。
因此，堆中最多只会保留每条链表的一个候选节点，堆的大小不会超过 K。
四、用示例推演执行过程
仍然使用下面三条链表：
L1：1 → 4 → 5
L2：1 → 3 → 4
L3：2 → 6
首先，把三条链表的头节点加入小顶堆：
堆中元素：[1, 1, 2]
后续过程如下：
| 步骤 | 弹出的最小节点 | 新加入堆的节点 | 已合并结果 |
|---|---|---|---|
| 1 | 1（L1） | 4 | 1 |
| 2 | 1（L2） | 3 | 1 → 1 |
| 3 | 2（L3） | 6 | 1 → 1 → 2 |
| 4 | 3（L2） | 4 | 1 → 1 → 2 → 3 |
| 5 | 4（L1） | 5 | 1 → 1 → 2 → 3 → 4 |
| 6 | 4（L2） | 无 | 1 → 1 → 2 → 3 → 4 → 4 |
| 7 | 5（L1） | 无 | 1 → 1 → 2 → 3 → 4 → 4 → 5 |
| 8 | 6（L3） | 无 | 1 → 1 → 2 → 3 → 4 → 4 → 5 → 6 |
当堆为空时，说明所有链表节点都已经处理完毕。
整个过程可以概括为三步：
-
将所有非空链表的头节点加入小顶堆；
-
弹出堆顶节点，并连接到结果链表；
-
如果弹出节点存在后继节点，就将后继节点加入堆中。
五、Java 完整代码
import java.util.PriorityQueue;
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) {
return null;
}
PriorityQueue<ListNode> minHeap =
new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
// 每条非空链表先放入一个头节点
for (ListNode head : lists) {
if (head != null) {
minHeap.offer(head);
}
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!minHeap.isEmpty()) {
// 取出当前所有候选节点中的最小值
ListNode minNode = minHeap.poll();
tail.next = minNode;
tail = tail.next;
// 当前链表向后移动一位，让下一个节点参与比较
if (minNode.next != null) {
minHeap.offer(minNode.next);
}
}
return dummy.next;
}
}
LeetCode 已经提供了 ListNode。如果需要在本地运行，可以补充如下定义：
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
六、代码中的三个关键点
1. 为什么使用哑节点
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
哑节点 dummy 不保存真正的结果数据，它的作用是统一链表拼接逻辑。无论当前加入的是第一个节点还是后续节点，都可以直接执行：
tail.next = minNode;
tail = tail.next;
最后返回 dummy.next 即可，不必单独判断结果链表是否为空。
2. 为什么不能把空节点加入堆
PriorityQueue 不允许插入 null，因此初始化时必须先判断：
if (head != null) {
minHeap.offer(head);
}
这也能正确处理 lists = [[]] 的情况：堆从一开始就是空的，最终返回 null。
3. 比较器为什么推荐使用 Integer.compare
截图中常见的写法是：
(a, b) -> a.val - b.val
这种写法在数值范围较大时可能发生整数溢出，进而得到错误的比较结果。更稳妥的写法是：
(a, b) -> Integer.compare(a.val, b.val)
这是面试和工程代码中都更推荐的写法。
七、复杂度分析
设 K 为链表数量，N 为所有链表的节点总数。
每个节点都会经历一次入堆和一次出堆，而堆中最多存在 K 个节点，因此单次堆操作的复杂度为 O(log K)。
-
时间复杂度：
O(N log K)； -
空间复杂度：
O(K)，这里指小顶堆占用的额外空间。
与直接扫描 K 条链表的 O(NK) 相比，当 K 较大时，小顶堆的优势非常明显。
八、还有其他解法吗
这道题还有一种经典的分治解法：两两合并链表。
第一轮把 K 条链表两两合并，得到大约 K/2 条链表；第二轮继续两两合并，直到只剩下一条。由于一共需要约 log K 轮，每一轮处理的节点总数都是 N，因此时间复杂度同样为：
O(N log K)
两种最优方案可以这样比较：
| 方案 | 时间复杂度 | 额外空间 | 特点 |
| 小顶堆 | O(N log K) | O(K) | 思路直观，适合流式获取最小节点 |
| 分治合并 | O(N log K) | 取决于实现 | 复用合并两个链表，常数开销通常较小 |
如果面试官指定使用优先队列，选择小顶堆；如果要求减少堆操作或继续追问其他最优解，可以回答分治合并。
九、常见错误
错误一：把所有节点一次性放入堆
这样虽然也能得到正确答案，但堆的大小会变成 N，空间复杂度提高到 O(N)。题目已经给出了每条链表有序的条件，应当充分利用它，只维护 K 个候选节点。
错误二：弹出节点后忘记加入其后继节点
如果没有执行：
if (minNode.next != null) {
minHeap.offer(minNode.next);
}
每条链表就只会处理第一个节点，后续节点全部丢失。
错误三：返回 dummy 而不是 dummy.next
dummy 是辅助节点，并不属于结果链表。正确返回值应为：
return dummy.next;
错误四：只判断 lists.length，没有判断 lists 是否为 null
工程代码中可以同时处理两种情况：
if (lists == null || lists.length == 0) {
return null;
}
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/weixin_51228134/article/details/163544254
