合并K个升序链表——优先队列与分治归并的性能对比
合并K个升序链表——优先队列与分治归并的性能对比
适读人群：Java 后端工程师、准备大厂面试的同学 | 阅读时长：约22分钟 | 难度：Hard
开篇故事
这道题我第一次碰到是在一家大厂的笔试里。当时我脑子里第一个想法是：不就是合并两个有序链表（21题）的扩展吗？把 K 个链表两两合并，重复 K-1 次，就完了。
写完提交，答案正确，但时间复杂度是 O(KN)，勉强过了，但有几个用例差点超时。出来之后我就开始想有没有更好的方法。研究了一下，发现优先队列和分治归并才是正解，两种方法的时间复杂度都能达到 O(NlogK)——这道题的关键就在于这个 logK 从哪来。
这篇文章把三种解法都完整实现，并且专门分析时间复杂度的差异，讲清楚为什么分治和优先队列都能达到 O(N*logK)，以及实际工程中该怎么选。
一、题目解析
题目：LeetCode 23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：三个链表合并后为：1->1->2->3->4->4->5->6
输入：lists = []
输出：[]
输入：lists = [[]]
输出：[]约束条件：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500- 所有 lists[i] 已按升序排列
考点梳理：
- 合并两个有序链表的基础能力
- 优先队列（堆）的使用
- 分治思想——递归将问题规模减半
- 时间复杂度分析——从 O(KN) 优化到 O(NlogK)
设 N 为所有链表节点总数，K 为链表数量。
二、解法一：暴力解法——顺序逐一合并
思路
把 K 个链表两两合并，从第一个链表开始，依次与后续链表合并。
合并两个有序链表是经典的 LeetCode 21 题，这里直接复用。
完整代码
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
ListNode result = lists[0];
for (int i = 1; i < lists.length; i++) {
result = mergeTwoLists(result, lists[i]);
}
return result;
}
// 合并两个有序链表（LeetCode 21）
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;
}
}复杂度分析
设 K 个链表，每个链表平均长度为 N/K（总节点数为 N）。
- 合并第1和第2个链表：处理约 N/K + N/K = 2N/K 个节点
- 合并结果和第3个链表：处理约 2N/K + N/K = 3N/K 个节点
- 合并结果和第i个链表：处理约 i*N/K 个节点
总时间 = N/K * (2 + 3 + ... + K) = N/K * (K*(K+1)/2 - 1) ≈ O(K*N)
时间复杂度：O(K*N)。当 K 很大时，这个复杂度非常差。 空间复杂度：O(1)。只用了常数个额外指针（不计结果链表本身）。
适用场景
K 很小时（比如只有 2-3 个链表）可以用这个方法，代码最简单。K 稍大就不行了。
三、解法二：优先队列（小顶堆）
思路
核心思想：每次从 K 个链表的当前头节点中，选出值最小的那个，加入结果链表。
用一个大小为 K 的小顶堆来维护这 K 个链表的当前头节点。每次从堆里取出最小节点，加入结果，然后把该节点的 next 节点（如果有）推入堆。
这就是经典的"多路归并"思路，O(logK) 来自堆的插入和弹出操作。
完整代码
class Solution {
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 minNode = pq.poll();
curr.next = minNode;
curr = curr.next;
// 将该链表的下一个节点加入堆
if (minNode.next != null) {
pq.offer(minNode.next);
}
}
return dummy.next;
}
}复杂度分析
- 时间复杂度：O(N * logK)。堆的大小始终为 K（最大），每次 poll 和 offer 操作为 O(logK)，总共 N 个节点，故 O(N*logK)。
- 空间复杂度：O(K)。堆中最多存 K 个节点。
适用场景
工程中最常用的多路归并方式。K 个数据流的归并（比如分布式系统中多个 Partition 的数据合并）就是这个模式。代码简洁，性能稳定。
提交结果：时间击败约 90% 用户，空间击败约 60% 用户。
四、解法三：最优解法——分治归并
思路
分治思路：把 K 个链表两两配对合并，第一轮得到 K/2 个合并结果，第二轮再两两配对，... 直到只剩一个链表。
这和归并排序的思路完全一致——每轮处理的工作量是 O(N)，共有 logK 轮，总时间 O(N*logK)。
为什么分治比顺序逐一合并好？
顺序合并的问题是：最终的大链表被反复遍历。分治让每个节点平均只参与 logK 次合并，而顺序合并中靠前的节点参与了 K-1 次合并。
Mermaid 图——分治过程
完整代码
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if (lists == null || lists.length == 0) return null;
return mergeRange(lists, 0, lists.length - 1);
}
// 分治：合并 lists[left..right] 范围内的所有链表
private ListNode mergeRange(ListNode[] lists, int left, int right) {
if (left == right) return lists[left]; // 只剩一个链表
if (left + 1 == right) return mergeTwoLists(lists[left], lists[right]); // 两个链表直接合并
int mid = left + (right - left) / 2;
ListNode leftMerged = mergeRange(lists, left, mid);
ListNode rightMerged = mergeRange(lists, mid + 1, right);
return mergeTwoLists(leftMerged, rightMerged);
}
// 合并两个有序链表（迭代版本，O(1) 空间）
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;
}
}复杂度分析
设 K 个链表，总节点数 N。
- 每一轮合并的节点总数为 N（所有节点恰好各参与一次合并）
- 共有 logK 轮合并
时间复杂度：O(N * logK)。 空间复杂度：O(logK)。递归调用栈深度为 logK。
性能对比
| 方法 | 时间复杂度 | 空间复杂度 | 实际表现 |
|---|---|---|---|
| 顺序合并 | O(KN) | O(1) | K大时极慢 |
| 优先队列 | O(NlogK) | O(K) | 稳定，工程首选 |
| 分治归并 | O(NlogK) | O(logK) | 空间略优，递归清晰 |
实测提交结果：
- 优先队列：时间击败约 90%，空间击败约 60%
- 分治归并：时间击败约 99%，空间击败约 90%
分治归并在 LeetCode 实测中略优于优先队列，主要原因是堆的常数因子较大，而分治的递归层次少，缓存友好性更好。
五、举一反三
同类题目
LeetCode 21. 合并两个有序链表 本题的 K=2 特例，是本题的基础子过程。
LeetCode 373. 查找和最小的K对数字 类似的优先队列多路归并思路。
LeetCode 378. 有序矩阵中第K小的元素 二维矩阵的多路归并，同样用优先队列。
LeetCode 786. 第K个最小的素数分数 优先队列在排序问题中的典型应用。
解题模板
多路归并优先队列模板：
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
// 初始化：加入各路的起始元素
for (ListNode head : lists) {
if (head != null) pq.offer(head);
}
ListNode dummy = new ListNode(0), curr = dummy;
while (!pq.isEmpty()) {
ListNode node = pq.poll();
curr.next = node;
curr = curr.next;
if (node.next != null) pq.offer(node.next); // 补充下一个元素
}
return dummy.next;六、踩坑实录
坑一：优先队列的比较器用减法出现整数溢出
// 有溢出风险的写法
(a, b) -> a.val - b.val
// 安全写法
(a, b) -> Integer.compare(a.val, b.val)节点值范围 [-10^4, 10^4]，虽然题目约束里不会溢出，但养成用 Integer.compare 的习惯更安全。
坑二：分治的边界条件不全
只判断了 left == right，没有判断 left + 1 == right，导致在两个链表时继续递归，最终栈溢出或逻辑出错。
坑三：初始化优先队列时加入了空链表
如果链表头节点为 null，不能加入优先队列，否则后续 pq.poll() 出来的节点是 null，访问 .val 时 NPE。
for (ListNode node : lists) {
if (node != null) pq.offer(node); // 必须判空
}坑四：合并两个链表时最后没有接上剩余部分
// 错误写法：循环结束后没有处理剩余节点
while (l1 != null && l2 != null) {
// ...
}
// 少了下面这行
curr.next = (l1 != null) ? l1 : l2;循环结束后，l1 或 l2 中还有剩余节点没有接入结果，必须补充这行。
坑五：空输入没有判断
lists 为空数组时，直接返回 null。不做判断会在 for 循环或递归里出现边界问题。
七、总结
这道题考察的核心是：当面对 K 路数据需要归并时，如何把时间复杂度从 O(KN) 优化到 O(NlogK)。两种方法——优先队列和分治归并——都能达到这个目标，区别在于思路和常数因子。
在实际工程中，分布式系统里多个节点的数据合并、多个排序文件的外排序、多个有序数据流的实时归并，用的都是优先队列的多路归并模式。这道题的思路有很强的工程背景，不只是纸面算法。
如果面试官问"两种方法哪个更好"，我的回答是：工程上优先队列更灵活（支持动态增减数据流），理论上分治更简洁（递归栈空间 O(logK) < 堆空间 O(K)），具体看场景。