适用读者：已经会 LC 21（合并两个有序链表），想把这题从「背模板」推进到「说清复杂度」的人
技术栈：Python 为主，三种解法都附 Java 版
难度：困难（但难点不在代码，在为什么是 O(N log k)）
收获：顺序 / 分治 / 最小堆三种做法的完整对比、一份可复现的比较次数实测表，以及一个反直觉的结论——小 k 时堆反而最慢
题目
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,5,6]
解释：将所有链表合并到一个升序链表中，得到 1→1→2→3→4→5→6
输入：lists = []
输出：[]
输入：lists = [[]]
输出：[]
约束：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i] 按升序排列lists[i].length 的总和不超过 10^4
节点定义沿用前两篇：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
留意约束里的两个数字：
k 可以到 10⁴，但所有链表的节点总数不超过 10⁴。这两句话放在一起，其实已经把「朴素做法会死在哪」提示出来了——后面细说。
一、先把「贵在哪」算清楚
1.1 这题是 LC 21 的 K 元版
上一篇 LC 21 我们拿到的是这段 8 行代码：
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
tail = dummy
while l1 and l2:
if l1.val <= l2.val:
tail.next = l1
l1 = l1.next
else:
tail.next = l2
l2 = l2.next
tail = tail.next
tail.next = l1 if l1 else l2
return dummy.next
LC 23 要做的就是把它用 K-1 次（或更多次）。所以本文不再重复哑结点、
tail 指针、先接再走这些东西——
那部分的地基在上一篇，这里只讨论「怎么用这 8 行代码」以及「用几次」。
1.2 最直觉的做法：顺序两两合并
def mergeKLists(lists):
if not lists:
return None
result = lists[0]
for lst in lists[1:]:
result = mergeTwoLists(result, lst)
return result
对，能过。但慢。
慢在哪？
早期接进 result 的节点，会被后面每一轮反复摸一遍。
设 K 条链表每条长 n，总节点数 N = k·n。第 i 轮合并时，
result 已经长到约
i·n 个节点，这一轮要遍历
i·n + n 个节点。把 K-1 轮加起来：
总访问次数 ≈ n·(2 + 3 + … + k) = n · (k(k+1)/2 − 1) ≈ N·k/2
——不是 O(kN)，是 k²N。因为每一轮的成本随 i 线性增长，而轮数也是 k，两次累加就出了平方。
一个具体的数：k = 1000、每条 10 个节点（N = 10,000）时，顺序合并要摸
4,543,137 次比较。而同样的 N，换成分治只要
97,987 次。差了 46 倍。
1.3 分治：把轮数从 k 压到 log k
问题出在「一条一条往后接」——每接一条，前面接好的都要再走一遍。
那就换个接法：
两两配对。
第 1 轮：k 条 → k/2 条 （每两条合并成一条）
第 2 轮：k/2 条 → k/4 条
…
第 r 轮：链表条数减半，直到剩 1 条
条数每次减半，所以只需要
⌈log₂k⌉ 轮。而每一轮里，所有节点加起来恰好被摸一次，单轮成本 O(N)。乘起来：
k = 1000 时 log₂k ≈ 10，也就是
十轮——而不是顺序做法的 999 轮。
1.4 最小堆：换个角度想「下一个该出谁」
分治是「改变合并的顺序」，堆是「换掉选择的方式」。
回到 LC 21 的核心观察：
全局最小的元素只可能出现在两条链表的头部。这个观察在 K 元下依然成立，只是从「两个头部」变成「K 个头部」：
任何时刻，全局最小的元素，一定是 K 条链表各自当前头部里的最小值。
所以我们要的其实是一台机器：
能随时塞进一个新元素、随时取出最小的那个。这正是优先队列（堆）的职责。
时间账：每个节点被取出一次、被塞入一次，共 2N 次堆操作，每次 O(log k)——注意是
log k 而不是 log N，因为堆里最多只有 k 个元素。总时间
O(N log k)。
1.5 三笔账放在一起
上面都是渐近分析。但渐近分析有个毛病：它把常数藏起来了，而
小 k 的时候常数说了算。所以我写了个脚本
tools/count_lc23_work.py，把三种解法各实现一遍，用带计数的比较键统计
真实的比较次数。
为什么是计数不是计时：计数是确定性算术，同一份输入跑一百遍都是同一个数，不受机器负载影响；计时在这台机器上的噪声底是 12%，跨会话能涨到 57%，那种数字没有可复现性。
backend/venv/Scripts/python.exe tools/count_lc23_work.py
结果：
最后两行的 N 都是 10,000，只是 k 差了 10 倍。看顺序合并那一列：
500,165 → 4,543,137，涨了 9 倍；分治只从 68,611 涨到 97,987，堆从 86,005 涨到 116,530。这就是 O(k²N) 和 O(N log k) 被隔离出来的样子。
但还有两件反直觉的事，这张表同样摆出来了：
- k = 4 的时候，顺序合并只比分治慢 14%，而最小堆慢了 64%。 堆不是银弹——建堆、上浮、下沉都是实打实的比较，k 小的时候「两两比较」比「维护一个堆」便宜得多。
- 分治在每一档都赢过最小堆。 两者同为 O(N log k)，但分治的比较次数一直最少。原因在第三节末尾展开。
二、最小堆：关键不在堆，在「堆里放几个」
2.1 先把一个错误做法排除掉
既然要「随时取最小」，一个很自然的想法是：
把全部 N 个节点都塞进堆，然后一个个弹出来。
这写法没错，结果也对。但它的时间是
O(N log N) ——你花了 O(N log N) 去把一个已经「分成 K 段有序」的序列重新排了一遍序。
这等于把题目给的条件扔了。 题目特意告诉你「每条链表已经升序」，这个条件的价值就是让你不必做全排序。K = N 时（每条链表只有一个节点），O(N log k) 就退化成了 O(N log N)，此时这个「优化」和直接对数组排序没有区别。
2.2 所以堆里只放 K 个节点
正确的做法基于 1.4 节那个观察：
全局最小只在 K 个头部产生。因此：
- 堆的初始内容：K 条链表各自的头节点，别的什么都不放；
- 每轮：弹出堆顶（当前全局最小），接到结果链表尾部；
- 然后把这个节点所在链表的下一个节点塞进堆；
- 堆空则结束。
堆的大小永远不超过 K。 这是 O(N log k) 里那个 k 的全部来源——不是 log N，是 log k。
这条不变式值得在面试里主动说出来，因为它正是这题的分水岭：能说出「堆里只放 K 个」的人，是真的理解了为什么复杂度里是 log k。
2.3 代码
import heapq
def mergeKLists(lists):
dummy = ListNode(0)
tail = dummy
heap = []
# 建堆：K 个头部入堆
for i, head in enumerate(lists):
if head: # 空链表直接跳过
heapq.heappush(heap, (head.val, i, head))
while heap:
val, i, node = heapq.heappop(heap) # 取出全局最小
tail.next = node # 接到结果尾部
tail = tail.next
if node.next: # 该链表前移一格
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
几个细节，每一个都是坑：
① 元组里的 i 不是装饰品。 heapq 用
< 比较元素。两个元素是元组时，Python 会先比第一个元素；如果相等，就继续比第二个。如果堆里存的是
(val, node)，值相等时 Python 会去比较
node ——而
ListNode 没有定义
__lt__，直接抛
TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'。
塞一个
互不相同的整数 i 垫背，比较在第二个元素上就分出胜负了，永远走不到
node。这就是「值相同时按链表序号定序」——顺带还让结果可复现。
② heapq 是小顶堆。 Python 的
heapq 只有
heappush /
heappop /
heapify，而且
是最小堆。这正是本题要的（取最小）。如果需要大顶堆，得自己把值取负再塞进去。
Java 那边同理：
PriorityQueue 默认是
小顶堆（注意 Java 的命名容易让人以为默认是大顶堆，其实不是）；要改顺序得传
Comparator。
③ 建堆的复杂度。 逐个
heappush 是 O(k log k)；用
heapify 一次性建堆是 O(k)。这里 k ≤ N，无论哪种都只是常数因子，不影响 O(N log k) 的量级。面试里被追问时可以提一句，但不必为它纠结。
④ 空链表要在入堆前跳过。 head 是
None 的时候取
head.val 会直接崩。
[[], []] 这种输入在测试用例里是有的。
2.4 看着它跑一遍
下面这个动画把 4 条链表
[1,4] [2,5] [3,6] [0,7] 的完整过程演了一遍。四条各两个节点，结果正好是 0 到 7。
右边那棵树就是堆。
盯住它的大小：从头到尾最多 4 个节点，而且随着链表被取空会越来越小。左侧每行的实线框是该链表当前的头部——
这些高亮的头部，就是堆里那 K 个候选。
对着动画读代码，几件事会变得很直观：堆顶出堆之后，末位元素补到根再下沉；新头入堆之后沿父链上浮；堆里换了人的那两个槽会被加粗标出来。
2.5 堆数组推演表
把动画里堆数组的变化抄成表（
(值, 来自哪条链表)）：
两处值得多看一眼：
- 第 1 轮建堆后的堆数组是
0/D, 1/A, 3/C, 2/B，不是 0,1,2,3。堆数组的顺序是「堆序」不是「值序」——它只保证父节点不大于子节点，不保证整体有序。别把堆数组当成排序结果读。
- 第 5 到 8 轮没有入堆，因为对应的链表已经取空了。堆的大小从 4 一路缩到 0，这也说明堆里元素个数是动态的，上界是 K。
2.6 边界情况
lists = []：建堆循环一次都不进，堆为空，while 不执行，返回 dummy.next 即 None。不需要特判——这和 LC 21 里哑结点吞掉特判是同一个套路。lists = [[]]：同上，head 为假被跳过，返回 None。lists 里混着空链表：只有非空的头部进堆，逻辑不变。k = 1：堆里永远只有 1 个元素，退化成顺着链表走一遍，O(N)。符合预期。- 值相等：靠元组第二个元素
i 定序。注意 i 用的是链表序号而不是全局序号，所以相等值会按「链表编号小的先出」排列——结果是确定的，但不必是稳定的（题目没要求稳定）。
2.7 Java 版
public ListNode mergeKLists(ListNode[] lists) {
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
// PriorityQueue 默认就是小顶堆；这里按节点值排序
PriorityQueue<ListNode> heap =
new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
for (ListNode head : lists) {
if (head != null) heap.offer(head);
}
while (!heap.isEmpty()) {
ListNode node = heap.poll();
tail.next = node;
tail = tail.next;
if (node.next != null) heap.offer(node.next);
}
return dummy.next;
}
注意 Java 版的堆里直接放
ListNode 本身，
不需要像 Python 那样塞一个序号垫背。原因是 Java 传了显式的
Comparator，比较逻辑由你定义，不会退化成去比较
ListNode 对象本身。Python 的
heapq 没有
key 参数，所以才必须靠元组做手脚——这是两个语言在这题上唯一真正不同的地方。
三、分治：轮数就是 log k
3.1 归并树
分治的做法是把 K 条链表看成一排，每一轮两两配对合并：
输入 [7] [2] [5] [1] [8] [3] [6] [4] 8 条
╲╱ ╲╱ ╲╱ ╲╱
第 1 轮 [2 7] [1 5] [3 8] [4 6] 4 条
╲───╱ ╲───╱
第 2 轮 [1 2 5 7] [3 4 6 8] 2 条
╲───────╱
第 3 轮 [1 2 3 4 5 6 7 8] 1 条
这个形状就是
归并排序的归并树倒过来。注意每一层的节点总数都是 8，变的只是分组的粒度：1 个一组 → 2 个一组 → 4 个一组。所以
每层的宽度是一样的，只是条数在减半——「轮数 = ⌈log₂k⌉」这句话，看图比看公式清楚得多。
3.2 代码
递归版（最好写，也最好讲）：
def mergeKLists(lists):
if not lists:
return None
return merge_range(lists, 0, len(lists) - 1)
def merge_range(lists, lo, hi):
if lo == hi: # 只剩一条，直接返回
return lists[lo]
mid = (lo + hi) // 2
left = merge_range(lists, lo, mid) # 排左半边
right = merge_range(lists, mid + 1, hi) # 排右半边
return mergeTwoLists(left, right) # 合并两半（LC 21 的代码）
读递归还是那个老办法：问清楚
merge_range(lists, lo, hi) 的契约是什么——「把
lists[lo..hi] 这一段合并成一条有序链表，返回它的头」。那么把区间从中间切开，两边各自兑现契约，再用 LC 21 合并两个结果，契约就兑现了。
递归的账单：递归深度是 ⌈log₂k⌉ 层，所以额外空间是 O(log k) 栈帧——比堆解法的 O(k) 还小。但 Python 里 k 很大时…其实 log₂(10⁴) ≈ 14 层，完全不会爆栈。这是分治在空间上的一个隐性优势。
迭代版（自底向上，没有递归栈，额外空间 O(1)）：
def mergeKLists(lists):
if not lists:
return None
level = lists
while len(level) > 1:
nxt = []
for i in range(0, len(level), 2):
if i + 1 < len(level):
nxt.append(mergeTwoLists(level[i], level[i + 1]))
else:
nxt.append(level[i]) # 轮空，原样进下一轮
level = nxt
return level[0]
3.3 奇数条的轮空
k 是奇数时，最后一轮会剩下一条配不上对。
处理方式是原样带进下一轮，不是丢掉。
这一点写错的方式很隐蔽：如果
nxt.append(...) 只写在
if 分支里，奇数条时最后一条会被静默丢弃——结果少一截，而且只有 k 为奇数时才复现。上面代码里那个
else: nxt.append(level[i]) 就是为它存在的。
（顺带一个反直觉点：轮空的那条链表
不会被摸。所以「每轮 O(N)」在奇数 k 时其实是「每轮 ≤ O(N)」，是个上界。
count_lc23_work.py 里统计的就是真实被摸到的节点数，不是按 N 估的。）
3.4 分治和堆同为 O(N log k)，为什么分治的比较次数一直更少
回到 1.5 节那张表：k = 1000 时，分治 97,987 次比较，堆 116,530 次。分治一直赢。
原因是两者对「每个节点要花多少次比较」的算法不同：
- 堆：每个节点入堆一次、出堆一次，每次操作最多走 log₂k 层，每层一次比较 → 每个节点约 2·log₂k 次比较。
- 分治：每个节点在每一轮里参与一次合并，每轮最多被比较一次 → 每个节点约 log₂k 次比较。
堆多出来的那一倍，就是「维护堆结构」本身的成本（上浮 + 下沉）。
但堆有一个分治比不了的优势，藏在同一份脚本的第二列——
节点访问次数：
分治要摸 99,840 次节点，堆只要 19,000 次——因为
每个节点在堆里只进出一次，而分治里每个节点每一轮都要被搬到新的结果链表上，一共搬了约 log₂k 遍。
比较少 vs 搬运少，这是两个不同的成本。在链表上「搬运」只是改几根指针（O(1)），所以这个差异不影响复杂度；但如果把同样的思路用在
数组上，搬运就是实打实的内存拷贝，堆的「少搬运」优势会立刻显现出来。面试里能主动讲清这个区别，比背下两个 O(N log k) 有分量得多。
四、三种做法总账
什么时候选哪个：
- k 很小（比如 ≤ 8）：直接用顺序合并。代码最短，实测比较次数和分治几乎持平，还省掉了建堆。别为了「看起来高级」而引入堆。
- k 大、N 大：分治或堆。两者同阶，分治比较次数更少、空间更小；堆的写法更「顺」，而且它天然适合流式场景——比如 K 路归并排序的外排（external sort），或者数据源是 K 个无法一次性读入的流。堆只需要同时持有 K 个头部，分治则需要同时持有 K 条链表的全部内容。
- 面试：先给分治或堆，再主动补一句「如果 k 很小，顺序合并反而更好」——这句话比多写一个解法更能说明你在按情况判断，而不是背题。
五、常见坑
写完代码按这个清单过一遍：
TypeError: '<' not supported between instances of 'ListNode' —— 堆里存了 (val, node) 而没有序号垫背，遇到相等值就崩。这是本题 Python 版最高频的报错。- 把 N 个节点全塞进堆 —— 结果对，但退化成 O(N log N)，白瞎了「每条链表已升序」这个条件。
- 建堆时没判空 ——
lists 里混着空链表时取 head.val 直接崩。for 循环里那句 if head 不能省。
- 忘了把新头入堆 —— 弹出堆顶之后不补位，堆很快就空了，结果只输出前面几个节点。
- 分治里丢掉奇数条的最后一条 ——
nxt.append 只写在 if i + 1 < len(level) 分支里。只有 k 为奇数才复现，很容易漏测。
lists = [] 没特判 —— 堆解法靠 while heap 天然兜住；但顺序合并的 result = lists[0] 和分治的 level[0] 都会 IndexError。- 递归版里忘了
if not lists: return None —— merge_range(lists, 0, -1) 会走进 lo == hi 都不成立的分支。
- 以为
heapq 是大顶堆 —— 它是小顶堆，本题正好要小的；要大的得取负。Java 的 PriorityQueue 也默认是小顶堆。
六、面试怎么答
30 秒版本（以最小堆为例）：
用一个最小堆维护 K 条链表当前的头部。建堆时把 K 个头放进去；每轮弹出堆顶接到结果链表尾部，然后把这个节点所在链表的下一个节点补进堆。堆里始终不超过 K 个元素，每个节点进出堆各一次，每次 O(log k)，所以总时间 O(N log k)，空间 O(k)。K 个头部以外的节点不用进堆——这是 log k 里那个 k 的来源。
追问预判：
- 「为什么不是 O(N log N)？」 → 因为堆里只放 K 个头部，不是全部 N 个节点。放全部就是全排序，把题目给的有序条件浪费了。
- 「分治和堆哪个好？」 → 同阶。分治的比较次数更少（每节点约 log k 次 vs 堆的 2·log k 次），空间也更小；堆的节点访问次数更少（每节点只进出一次），适合流式 / 外排场景。
- 「顺序合并为什么是 O(k²N)？」 → 第 i 轮要遍历已经接好的 i·n 个节点，累加起来是 n·k(k+1)/2 量级。
- 「k 很小时呢？」 → 顺序合并反而更好。实测 k = 4 时它只比分治慢 14%，而堆慢了 64%。
- 「Python 里为什么要塞一个序号？」 →
heapq 比较元组时会依次比较各元素，值相等时会去比较 ListNode，而它没有 __lt__，直接 TypeError。Java 因为要显式传 Comparator，不需要这一步。
- 「怎么处理空链表？」 → 建堆时跳过，逻辑天然兼容；
lists 本身为空时靠 while heap 或提前返回兜住。
结语
把 LC 21 和 LC 23 放在一起看，这题其实在教一件事：
同一份子程序，用不同的组织方式调用，复杂度能差一个数量级。
LC 21 那 8 行代码一个字没改，只是从「一条一条往后接」换成「两两配对」，复杂度就从 O(k²N) 掉到 O(N log k)；再换成「K 个头部放堆里」，同样是 O(N log k)，但换来了流式处理的可能。真正难的部分从来不是那 8 行，是
你选择怎么调用它。
另一个值得记住的教训是 1.5 节那张表：渐近复杂度只告诉你 k 变大以后会怎样，它不管 k = 4 的时候谁快。
「O(N log k) 更优」不等于「堆在这道题的每个输入上都更快」——实测 k = 4 时堆是三种做法里最慢的。面试官如果问「你会选哪个」，说「看 k 多大」比直接背「堆」要好。
上一篇 LC 206 讲的是「指针操作的本质是维护边界」，LC 21 讲的是「哑结点把特例变成通例」，这一篇讲的是「复杂度取决于你怎么调用子程序」。三篇连起来，链表这条线的骨架就基本齐了。
下一篇大概率是 LC 148（排序链表）——把 LC 21 的合并和 LC 206 的指针操作拼起来，你就能拿到一个 O(1) 额外空间的链表归并排序。