【LeetHOT100】合并 K 个升序链表——Java多解法详解
一、题目描述
23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：
lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：text
[ 1->4->5, 1->3->4, 2->6 ]将它们合并到一个有序链表中得到：1->1->2->3->4->4->5->6
示例 2：
输入：
lists = []
输出：[]
示例 3：
输入：
lists = [[]]
输出：[]
提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按升序排列lists[i].length的总和不超过10^4
二、解题思路概览
合并 K 个升序链表，是“合并两个有序链表”（LeetCode 21）的扩展。常见解法有四种：
| 解法 | 时间复杂度 | 空间复杂度 | 特点 | 面试推荐 |
|---|---|---|---|---|
| 顺序合并 | O(k² × n) | O(1) | 最直观，效率最低 | ⭐ |
| 优先队列（最小堆） | O(N × log k) | O(k) | 代码简洁，面试常考 | ⭐⭐⭐⭐⭐ |
| 分治合并 | O(N × log k) | O(log k) | 效率高，无额外数据结构 | ⭐⭐⭐⭐⭐ |
| 暴力收集+排序 | O(N × log N) | O(N) | 简单但浪费链表有序性 | ⭐ |
其中：k 为链表个数，n 为每个链表的平均长度，N 为总节点数（N = k × n）
三、解法一：顺序合并（最直观）
3.1 思路
依次遍历链表数组，将当前结果链表与下一个链表合并，重复直到所有链表合并完成。
3.2 代码实现
java
class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; ListNode result = null; for (ListNode list : lists) { result = mergeTwoLists(result, list); } return result; } // 合并两个有序链表（复用 LeetCode 21 的代码） private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 != null) ? l1 : l2; return dummy.next; } }3.3 复杂度分析
时间复杂度：O(k² × n)。第一次合并 O(2n)，第二次 O(3n)... 第 k 次 O(kn)，总和为 O(k²n)
空间复杂度：O(1)
3.4 为什么不推荐？
当 k 很大时（如 k = 10⁴），O(k²n) 会非常大，无法通过测试。
四、解法二：优先队列（最小堆）⭐⭐⭐⭐⭐
4.1 核心思路
创建一个最小堆，将所有链表的头节点加入堆中
每次从堆中取出最小的节点，接到结果链表尾部
如果该节点还有下一个节点，将下一个节点加入堆中
重复直到堆为空
4.2 代码实现
java
class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; // 最小堆，按节点值排序 PriorityQueue<ListNode> pq = new PriorityQueue<>( (a, b) -> a.val - b.val ); // 将所有非空链表的头节点加入堆 for (ListNode node : lists) { if (node != null) { pq.offer(node); } } ListNode dummy = new ListNode(0); ListNode cur = dummy; while (!pq.isEmpty()) { ListNode smallest = pq.poll(); // 取出最小值节点 cur.next = smallest; cur = cur.next; if (smallest.next != null) { pq.offer(smallest.next); // 将下一个节点加入堆 } } return dummy.next; } }4.3 图解示例
以lists = [[1,4,5], [1,3,4], [2,6]]为例：
text
初始堆: [1(来自第1个), 1(来自第2个), 2(来自第3个)] 第1步: 取出最小1(第1个) → 结果:1, 加入4 → 堆:[1(第2个),2,4] 第2步: 取出最小1(第2个) → 结果:1→1, 加入3 → 堆:[2,3,4] 第3步: 取出最小2(第3个) → 结果:1→1→2, 加入6 → 堆:[3,4,6] 第4步: 取出最小3(第2个) → 结果:1→1→2→3, 加入4 → 堆:[4,4,6] 第5步: 取出最小4(第1个) → 结果:1→1→2→3→4, 加入5 → 堆:[4,5,6] 第6步: 取出最小4(第2个) → 结果:...→4, 该链表结束 → 堆:[5,6] 第7步: 取出最小5 → 结果:...→5, 链表结束 → 堆:[6] 第8步: 取出最小6 → 结果:...→6, 链表结束 → 堆:[] 最终: 1→1→2→3→4→4→5→6
4.4 复杂度分析
时间复杂度：O(N × log k)。N 为总节点数，每次入堆/出堆操作 O(log k)，共 N 次操作
空间复杂度：O(k)。堆中最多存储 k 个节点
五、解法三：分治合并⭐⭐⭐⭐⭐
5.1 核心思路
将链表数组两两配对，合并每一对，重复直到只剩一条链表。类似于归并排序的分治思想。
5.2 代码实现
java
class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) return null; return merge(lists, 0, lists.length - 1); } // 分治合并 [left, right] 区间的链表 private ListNode merge(ListNode[] lists, int left, int right) { if (left == right) return lists[left]; if (left > right) return null; int mid = left + (right - left) / 2; ListNode l1 = merge(lists, left, mid); ListNode l2 = merge(lists, mid + 1, right); return mergeTwoLists(l1, l2); } // 合并两个有序链表 private ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 != null) ? l1 : l2; return dummy.next; } }5.3 图解示例
以lists = [[1,4,5], [1,3,4], [2,6]]为例：
text
第一层分治: merge(0,2) / \ merge(0,1) merge(2,2) / \ | merge(0,0) merge(1,1) lists[2] 第二层合并: merge(0,0) = [1,4,5] merge(1,1) = [1,3,4] merge(0,1) = 合并 [1,4,5] 和 [1,3,4] → [1,1,3,4,4,5] 第三层合并: merge(2,2) = [2,6] merge(0,2) = 合并 [1,1,3,4,4,5] 和 [2,6] → [1,1,2,3,4,4,5,6]
5.4 复杂度分析
时间复杂度：O(N × log k)。每层总合并时间为 O(N)，共 log k 层
空间复杂度：O(log k)。递归调用栈的深度
六、解法四：暴力收集 + 排序（不推荐）
6.1 思路
将所有链表的值收集到一个列表中，排序后重新构建链表。虽然简单，但完全浪费了链表有序的条件。
6.2 代码实现
java
class Solution { public ListNode mergeKLists(ListNode[] lists) { List<Integer> values = new ArrayList<>(); for (ListNode node : lists) { while (node != null) { values.add(node.val); node = node.next; } } Collections.sort(values); ListNode dummy = new ListNode(0); ListNode cur = dummy; for (int val : values) { cur.next = new ListNode(val); cur = cur.next; } return dummy.next; } }6.3 复杂度分析
时间复杂度：O(N × log N)，排序是主要耗时
空间复杂度：O(N)，存储所有值
七、解法对比与总结
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 顺序合并 | O(k²n) | O(1) | 简单直观 | 效率极低，k 大时不可用 |
| 优先队列 | O(N log k) | O(k) | 代码简洁，面试常考 | 需要额外堆空间 |
| 分治合并 | O(N log k) | O(log k) | 无额外数据结构，效率高 | 递归理解稍复杂 |
| 暴力排序 | O(N log N) | O(N) | 思路最简单 | 空间大，未利用有序性 |
八、面试建议
8.1 优先选择哪个？
| 场景 | 推荐解法 |
|---|---|
| 面试标准答案 | 优先队列或分治合并 |
| 追求代码简洁 | 优先队列（Java PriorityQueue） |
| 追求极致效率 | 分治合并（常数更小） |
| 不允许用堆 | 分治合并 |
| 快速实现 | 暴力收集+排序（仅限练习） |
8.2 常见错误
忘记处理空链表：加入堆前要判断
node != null堆的 Comparator 写反：
(a,b) -> a.val - b.val是最小堆，a.val - b.val是升序分治递归时 left > right 返回 null：但要注意处理空数组的情况
在循环中重复创建 PriorityQueue：应该只创建一个
8.3 扩展问题
Q：如果链表数量特别多（如 10⁶），但总节点数不多，哪个方法好？
A：优先队列更好，因为堆中只存储 k 个节点，空间 O(k)，而分治合并的递归深度可能很大。
Q：如果要求 O(1) 空间，怎么办？
A：可以用“顺序合并”（O(k²n)）或“分治合并”（但递归栈不算 O(1)）。实际上，O(1) 空间解法在这道题中效率很低，面试中一般不会这样要求。
九、相关链接
题目链接：23. 合并 K 个升序链表 - 力扣（LeetCode）
官方题解：合并 K 个升序链表官方题解