LeetCode 23. 合并 K 个升序链表
目录
题目描述
题意分析
输入是一个链表数组，数组里每条链表本身已经按升序排好，要求把它们合成一条升序链表并返回新的头节点。
把链表条数固定为 2，这就是第 21 题「合并两个有序链表」；本题是它从两条到
k条的规模化版本，难度也从简单跳到了困难。多出来的那一层不在「怎么合并两条」，而在「同一时刻有k个来源，每一步该从谁那里取」——规模化把一个比较问题升级成了调度问题。「每条链表本身已经升序」是全题唯一的题设条件，也是它区别于普通排序的地方。忽略这句话，把所有值收集起来排一遍序当然也能得到答案，但那意味着重新比较了大量早就确定了相对顺序的元素——题目被标为困难，考的正是怎么把这份已有的有序性用掉。
返回值是节点指针，题目也没要求保留输入结构，因此可以直接重接输入节点的指针，不必新建节点。这决定了合并过程的额外空间可以做到与节点总数无关。
需要单独想清楚的边界有四种：数组本身为空（长度 0），此时答案是空链表；数组非空但某些元素是空链表，它们不能参与后续比较，却也不能让流程崩掉；数组只有一个元素，答案就是它本身；所有元素都是空链表，答案仍是空。这四种里前两种最常被漏掉。
解法：最小堆多路归并
核心思路
每条链表当前未合并的头节点都是候选，所有剩余节点的最小值一定在这些候选中。用最小堆维护最多
k个候选：每次取出最小节点接到结果末尾，再把它的后继加入堆。
解题步骤
- 将每条非空链表的头节点加入最小堆。
- 使用哨兵节点和尾指针维护结果链表。
- 反复弹出堆顶节点接到结果末尾；若该节点有后继，将后继加入堆。
- 堆为空时，返回哨兵节点的后继。
代码实现
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> heap =
new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
for (ListNode node : lists) {
if (node != null) {
heap.offer(node);
}
}
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
while (!heap.isEmpty()) {
ListNode node = heap.poll();
tail.next = node;
tail = node;
if (node.next != null) {
heap.offer(node.next);
}
}
return dummy.next;
}
}
import "container/heap"
type nodeHeap []*ListNode
func (h nodeHeap) Len() int { return len(h) }
func (h nodeHeap) Less(i, j int) bool { return h[i].Val < h[j].Val }
func (h nodeHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *nodeHeap) Push(value any) {
*h = append(*h, value.(*ListNode))
}
func (h *nodeHeap) Pop() any {
old := *h
last := len(old) - 1
node := old[last]
old[last] = nil
*h = old[:last]
return node
}
func mergeKLists(lists []*ListNode) *ListNode {
minHeap := &nodeHeap{}
heap.Init(minHeap)
for _, node := range lists {
if node != nil {
heap.Push(minHeap, node)
}
}
dummy := &ListNode{}
tail := dummy
for minHeap.Len() > 0 {
node := heap.Pop(minHeap).(*ListNode)
tail.Next = node
tail = node
if node.Next != nil {
heap.Push(minHeap, node.Next)
}
}
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(n \log k)$，
n为节点总数，堆中最多有k个节点。- 空间复杂度：$O(k)$，用于保存每条链表的当前候选节点。
关键点总结
- 堆中每条非空链表最多保留一个候选节点。
- 弹出节点后必须加入它的后继，才能继续归并该链表。
- 直接复用原链表节点，只修改
next指针，不需要复制节点。- 比较器使用
Integer.compare，避免相减造成整数溢出。
易错点总结
- 将空链表放入 Java 的优先队列会抛出异常。
- 弹出节点后忘记把后继入堆，会丢失该链表剩余部分。
- 一次把所有节点放入堆会把空间从 $O(k)$ 扩大到 $O(n)$。
- 比较器写成
a.val - b.val可能发生整数溢出。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 21. 合并两个有序链表 | 简单 | 只有两条链，是本题的归并原语，不涉及候选集调度与合并顺序 |
| 88. 合并两个有序数组 | 简单 | 载体换成数组，因为能随机访问，可以从后往前填，做到不占额外空间 |
| 148. 排序链表 | 中等 | 对单条无序链表做归并排序，多了「快慢指针找中点并断链」这一步 |
| 373. 查找和最小的 K 对数字 | 中等 | 候选来自两个数组的下标组合而非链表，入堆时要去重，避免同一对被压两次 |
| 632. 最小区间 | 困难 | 同样多路推进 k 条有序表，但要维护候选集内的最大值，求覆盖所有表的最小区间 |
| LCR 078. 合并 K 个升序链表 | 困难 | 与本题同题换皮，可原样套用堆或分治两种写法 |
| 剑指 Offer 25. 合并两个排序的链表 | 简单 | 与 21 同题换皮，常被额外要求给出递归版的两路归并 |
| 滴滴面试题-合并 k 个排序数组 | 中等 | 数据源换成数组，堆里必须存「数组下标 + 元素下标」二元组，节点不自带后继指针 |