23. 合并K个排序链表（Merge k Sorted Lists）
频次 ★★★★ · 难度 🔴 · 高频：阿里/字节
题目
给定 k 个升序链表，将它们合并为一个升序链表并返回。
示例：
输入: lists = [[1,4,5],[1,3,4],[2,6]]
输出: 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
思路
小顶堆（优先队列）：维护一个按节点值排序的最小堆，初始把每条链表的头节点都放进去。每次弹出堆顶（当前全局最小的节点）接到结果链表末尾，如果它还有下一个节点就把 next 放入堆中。堆里最多同时存在 k 个节点，每次弹出/插入都是 O(log k)。
（也可以两两合并 —— 分治法，把 k 条链表两两合并直到剩一条，复杂度同样是 O(n log k)，思路上是”归并排序”的链表版；堆做法代码更短。）
代码
public ListNode mergeKLists(ListNode[] lists) {
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 node = pq.poll();
cur.next = node;
cur = cur.next;
if (node.next != null) {
pq.offer(node.next);
}
}
return dummy.next;
}复杂度
- 时间：O(n log k) — n 是节点总数，堆大小恒为 k
- 空间：O(k) — 堆最多存 k 个节点
边界条件
lists为空数组：堆一直为空，循环不执行，返回dummy.next == null。- 所有链表都为空：初始化时全部被过滤掉，堆为空，同上返回
null。 - 只有一条非空链表：堆里只有一个节点，每次弹出后放入它的
next，退化为直接遍历这条链表。
变式
- 分治法（两两合并）：把 k 条链表两两配对合并（类似归并排序的思路），合并后剩下 k/2 条，重复直到只剩一条，复杂度同样是 O(n log k)，不需要额外的堆结构，但需要实现”合并两个有序链表”这个子过程。
- 顺序合并（一条一条往后接）：每次把结果和下一条链表合并，复杂度是 O(k × n)，当 k 较大时明显慢于堆或分治解法，通常作为”暴力解法”先提出再优化。
易错点
- 堆里存的是节点而不是值，弹出后要检查
node.next是否为空再决定要不要继续放入堆。 k条链表里可能有空链表（null），初始化时要过滤掉，否则堆里会存入null导致比较器调用时空指针异常。
面试追问
- 堆解法和分治解法，时间复杂度都是 O(n log k)，实际该选哪个？ 两者渐进复杂度相同，分治法常数因子更小（不需要维护堆的上浮下沉开销），但堆解法代码更短、更容易写对；面试中如果被问”还有更优的做法吗”，分治法是标准答案，但堆解法作为第一反应也是可以接受的。
- 如果 k 特别大（远大于每条链表的长度），有没有更好的做法？ 分治法在这种场景下优势更明显，因为它是”多条短链表两两合并”，递归的层数是 log k，堆解法的堆大小恒为 k，当 k 很大时堆的调整开销（log k）仍然存在，但分治法可以更好地利用局部性；实际数量级差异不大时两者选择不影响整体复杂度量级。
关联题
- 同套路：21. 合并两个有序链表 —— 两两合并的基础子过程；88. 合并两个有序数组 —— 数组版合并
- 进阶：148. 排序链表 —— 同为归并思想，本题的分治两两合并与它的递归切分互为镜像
- 知识点：小顶堆解法就是 K 路归并，也是 LSM/外部排序多路段合并的算法内核，堆结构见数据结构与算法