题目描述
思路解析
一句话答案：LeetCode 23 合并 K 个升序链表的经典解是最小堆（优先队列）：堆里只放每条链当前的头节点，堆顶永远是全局最小，弹出接进结果链、再把它的后继补进堆。N 个节点各进出堆一次，总时间 O(N log K)、空间 O(K)；分治两两归并同样能做到 O(N log K)。
从合并两条到合并 K 条，难在哪里
合并两条有序链表时，每一步只需比较两个头节点、取小的接走。链表变成 K 条后，问题的本质没变——结果链的下一个节点，永远是「K 个当前头里最小的那个」。难点只剩一个：怎么快速地从 K 个候选里反复取最小。每次线性扫一遍 K 个头要 O(K)，N 个节点总共就是 O(NK)，链表条数一多就顶不住了。
为什么逐条合并和全量排序都不划算
一个直觉做法是把第一条和第二条合并，结果再和第三条合并，如此推进。问题在于结果链越合越长，靠前的节点会被反复扫描，最坏总代价同样是 O(NK)。另一个做法是把所有节点值收进数组排序再重建链表，时间 O(N log N)、还要 O(N) 空间，而且完全没利用「每条链本来就有序」这个现成条件——有序意味着全局最小的候选其实只有 K 个头，这条信息被白白浪费了。
为什么最小堆正好卡在这个需求上
「维护一批候选、随时弹出最小、随时补充新候选」正是最小堆（优先队列）的本职：弹出和插入都只要 O(log K)。做法是先把 K 条链的头节点全部入堆，循环里弹出堆顶接到结果链尾部，若被弹出的节点还有后继，就把后继入堆，堆空时合并结束。
整个过程保持一个不变量：堆里装的恰好是每条还没走完的链的当前头。有了这个不变量，堆顶必然是所有剩余节点的全局最小，每次接走堆顶，结果链自然严格升序，正确性就立在这里。
为什么弹出一个只需要补一个
某条链的头被取走后，这条链新的最小值就是原头的 next——链本身有序保证了这一点，更靠后的节点不可能抢在 next 前面成为候选。所以每弹一个只补一个，堆的大小始终不超过 K。这也解释了一个常见错误：把所有节点一次性全塞进堆，结果虽然也对，但堆膨胀到 N 个元素，时间退化成 O(N log N)，空间从 O(K) 涨到 O(N)，最小堆的精髓恰恰在于堆要小。
不用堆还能怎么做：分治两两归并
分治是等价的另一条路：把 K 条链两两配对合并成约一半，再两两合并，重复 log K 轮；每一轮所有节点被扫一遍，总时间同样 O(N log K)，额外空间只有递归栈。两种写法复杂度相同，堆版思路更直白，分治版不依赖堆结构，面试时任选其一并能说出另一种，是很好的加分点。
复杂度与容易翻车的细节
堆版总时间 O(N log K)：N 个节点各入堆、出堆一次，每次堆操作 O(log K)；空间 O(K)。三个细节：入堆前要跳过空链表，空节点入堆会直接报错；弹出后忘记补后继，那条链剩下的节点就永远丢了；Python 里两个链表节点对象不能直接比较大小，堆元素要写成「值、链序号、节点」三元组，值相等时靠序号打破平局。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
思路口诀：K 个头进堆·弹最小·补下一个，堆顶永远是全局最小、循环到堆空即升序结果。下面一步步演给你看。
开始：堆是空的（容量 3，空位用占位表示）。先把 K 个链表的第一个头依次入堆。
把 链A 的头 1 入堆： 先把它放到堆的末尾(下标0)，再向上浮到该去的位置。
把 链B 的头 1 入堆： 先把它放到堆的末尾(下标1)，再向上浮到该去的位置。
新节点 1 ≥ 父节点 1，不再上浮，就位(标绿)。堆顶 1 仍是当前最小。
把 链C 的头 2 入堆： 先把它放到堆的末尾(下标2)，再向上浮到该去的位置。
新节点 2 ≥ 父节点 1，不再上浮，就位(标绿)。堆顶 1 仍是当前最小。
堆顶 1(链A) 是当前所有链头里最小的，把它弹出接走。
1 接入结果链(第1个)。把堆末元素 2 暂放到堆顶(标紫)，再向下沉到该去的位置。
比较 2 与较小的子节点 1：子节点更小，下沉——交换。
交换完成，2 沉到下标1。
2 已不大于子节点，下沉结束(标绿就位)，堆顶 1 又是当前最小。
链A 刚被取走一个，补它的下一个 4 入堆： 先把它放到堆的末尾(下标2)，再向上浮到该去的位置。
新节点 4 ≥ 父节点 1，不再上浮，就位(标绿)。堆顶 1 仍是当前最小。
堆顶 1(链B) 是当前所有链头里最小的，把它弹出接走。
1 接入结果链(第2个)。把堆末元素 4 暂放到堆顶(标紫)，再向下沉到该去的位置。
比较 4 与较小的子节点 2：子节点更小，下沉——交换。
交换完成，4 沉到下标1。
4 已不大于子节点，下沉结束(标绿就位)，堆顶 2 又是当前最小。
链B 刚被取走一个，补它的下一个 3 入堆： 先把它放到堆的末尾(下标2)，再向上浮到该去的位置。
新节点 3 ≥ 父节点 2，不再上浮，就位(标绿)。堆顶 2 仍是当前最小。
堆顶 2(链C) 是当前所有链头里最小的，把它弹出接走。
2 接入结果链(第3个)。把堆末元素 3 暂放到堆顶(标紫)，再向下沉到该去的位置。
3 已不大于子节点，下沉结束(标绿就位)，堆顶 3 又是当前最小。
链C 刚被取走一个，补它的下一个 6 入堆： 先把它放到堆的末尾(下标2)，再向上浮到该去的位置。
新节点 6 ≥ 父节点 3，不再上浮，就位(标绿)。堆顶 3 仍是当前最小。
堆顶 3(链B) 是当前所有链头里最小的，把它弹出接走。
3 接入结果链(第4个)。把堆末元素 6 暂放到堆顶(标紫)，再向下沉到该去的位置。
比较 6 与较小的子节点 4：子节点更小，下沉——交换。
交换完成，6 沉到下标1。
6 已不大于子节点，下沉结束(标绿就位)，堆顶 4 又是当前最小。
链B 刚被取走一个，补它的下一个 4 入堆： 先把它放到堆的末尾(下标2)，再向上浮到该去的位置。
新节点 4 ≥ 父节点 4，不再上浮，就位(标绿)。堆顶 4 仍是当前最小。
堆顶 4(链A) 是当前所有链头里最小的，把它弹出接走。
4 接入结果链(第5个)。把堆末元素 4 暂放到堆顶(标紫)，再向下沉到该去的位置。
4 已不大于子节点，下沉结束(标绿就位)，堆顶 4 又是当前最小。
链A 刚被取走一个，补它的下一个 5 入堆： 先把它放到堆的末尾(下标2)，再向上浮到该去的位置。
新节点 5 ≥ 父节点 4，不再上浮，就位(标绿)。堆顶 4 仍是当前最小。
堆顶 4(链B) 是当前所有链头里最小的，把它弹出接走。
4 接入结果链(第6个)。把堆末元素 5 暂放到堆顶(标紫)，再向下沉到该去的位置。
5 已不大于子节点，下沉结束(标绿就位)，堆顶 5 又是当前最小。
链B 已经走空，没有后继可补，堆里还剩 2 个头(堆顶 5，标蓝)继续处理。
堆顶 5(链A) 是当前所有链头里最小的，把它弹出接走。
5 接入结果链(第7个)。把堆末元素 6 暂放到堆顶(标紫)，再向下沉到该去的位置。
6 已不大于子节点，下沉结束(标绿就位)，堆顶 6 又是当前最小。
链A 已经走空，没有后继可补，堆里还剩 1 个头(堆顶 6，标蓝)继续处理。
堆顶 6(链C) 是当前所有链头里最小的，把它弹出接走。
堆空了，所有节点都已弹出接走。结果链 1→1→2→3→4→4→5→6，全程升序，合并完成。
空链表集合、全空链、单链三个边界先想清。
两个高频追问：分治替代方案、元组里为何带序号。
参考代码
import heapqdef mergeKLists(lists): h = [] # 最小堆，元素 (值, 链序号, 节点) for i, node in enumerate(lists): if node: heapq.heappush(h, (node.val, i, node)) dummy = tail = ListNode() while h: val, i, node = heapq.heappop(h) # 弹最小 tail.next = node; tail = node if node.next: # 补后继 heapq.heappush(h, (node.next.val, i, node.next)) return dummy.next复杂度
- 时间：O(N log K)，N 个节点各进出堆一次，每次堆操作 O(log K)
- 空间：O(K)，堆里最多 K 个当前头
易错点
面试追问把动画讲成自己的话
追问不用堆还能怎么合并 K 条链表？
追问为什么堆里要带链表序号 i？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
K 个一组翻转链表
LeetCode 25 · 困难 · 沿着 链表 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题