合并K个升序链表：三种解法与复杂度拆解

做过这道题的人都有同感：第一次看到“合并 K 个升序链表”，脑子里蹦出来的方案往往是“每次从 K 个链表的头节点里挑最小的，拼到结果后面”。这个直觉完全没错，但很多人第一版代码交上去就超时，倒不是思路不对，而是没想清楚“每次挑最小”这件事本身有多贵。如果每个链表平均有 N 个节点，线性扫描 K 个头节点来找最小值，整体复杂度直接干到 O(K²N)，K 稍微大一点就跑不动了。本文就从这道题出发，把三种主流解法、每行代码背后的代价、以及刷题时容易踩的坑一次性讲透。适合正在集中刷链表题、准备算法面试，或者对多路归并思想想建立更系统认识的读者。

1. 先写能跑的顺序合并：复杂度是怎么一步步变差的

1.1 合并两个升序链表是前置技能

做 K 个之前，先把“合并两个升序链表”写熟。这道题的基础操作就是它，不管后面用堆还是分治，最后都要落到这个函数上。

def mergeTwoLists(l1, l2): dummy = ListNode(-1) 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

这里的核心套路是“哑节点 + 尾指针”。dummy的作用是避免处理头节点为空的特殊情况，让tail始终指向已构建链表的最后一个节点，最后直接返回dummy.next就是整个有序链表的头部。这个写法是链表题的基本功，顺手要能默写。

有读者可能问：tail = tail.next为什么不能省略？因为每次接入一个新节点后，尾指针必须跟着走，否则下一轮会一直在同一个位置后面追加，链表结构立刻乱掉。你可以把tail理解成一个“施工队队长”，他必须永远站在工地最后一段，工人（新节点）才能依次排在他后面。

1.2 顺序合并的复杂度推导

有了mergeTwoLists，最朴素的“合并 K 个升序链表”就是一条一条来：先合并第一条和第二条，得到的新链表再和第三条合并，如此反复。

def mergeKLists(lists): if not lists: return None merged = None for head in lists: merged = mergeTwoLists(merged, head) return merged

这个写法逻辑上没毛病，但复杂度非常糟糕。假设 K 条链表，每条平均 N 个节点，总节点数 T = K × N：

• 第一轮：None和链表 1 合并，访问 N 个节点。
• 第二轮：已合并链长 N，和链表 2 合并，访问 2N 个节点。
• 第三轮：访问 3N 个节点。
• ……
• 第 K 轮：访问 K×N 个节点。

总访问次数大约是 N × (1 + 2 + … + K) = N × K(K+1)/2，也就是 O(K²N)。用总节点数 T 表示，就是 O(TK)。

很多人在这里会算错，以为循环 K 次、每次合成长度 N，复杂度是 O(KN)。问题在于，每条链表的节点不止被访问一次。前几条链表先合在一起，后面每来一条新链表，这一大串老节点就要被重新扫描一遍。你可以想象成排队做核酸：每一轮都让前面所有已经排过队的人重新排一次，队伍越长，重复劳动越多。当 K 很大时，这个平方级的增长会非常明显，测试用例里链表数量一多，超时几乎是必然的。

2. 把三种主流解法放在同一张表里对比

2.1 三行表格与复杂度换算

刷题到后期，我发现拿到一道“合并 K 个升序链表”这种题，先别急着写代码，而是先在草稿纸上做个横向对比。这事关你是否真正理解了每种做法的定位。

这里 T 表示所有链表节点的总数。题目里如果每条链表平均长度是 N，那 T = K×N，所以有些题解写 O(NK log K)，和这里的 O(T log K) 是一回事。

从表格能看出，顺序合并虽然代码最容易写，但复杂度比另外两种高了一个量级。分治合并和优先队列在时间复杂度上打平，区别主要在空间和实现方式上。

2.2 不同场景下解法怎么选

面试里碰到这道题，选哪种解法不只是“能不能 AC”，还得看面试官想考察什么。

如果面试官先让你“想一个最简单的思路再说说怎么优化”，那顺序合并就是你展示思维递进的起点。先给出朴素写法，再点明它的平方级瓶颈，然后顺势引出分治或堆，这条叙事线非常自然。

如果面试官明确说“不用考虑空间”，优先队列（最小堆）是最直接的优化方案，代码写起来也很快，还能顺便展示你对堆这个数据结构的熟练度。尤其是 Python 和 Java 都有现成的堆实现，手写量很少。

如果面试官强调“空间最好也别用太多”，迭代版分治合并就是更优的选择。它的额外空间可以做到 O(1)（不考虑输入数组本身和递归栈），只靠两两合并就能把复杂度压到 O(T log K)。这种解法对链表操作的要求更高，更容易在细节上出 bug，但答出来会显得功底扎实。

还有一个小场景：如果 K 本身很小，比如只有 2 或 3，那顺序合并完全不亏。复杂度里的 K 是常数，和分治/堆差距不大，代码还最不容易写错。做题不必总是追求“最最优”，先把问题规模看清楚。

3. 优先队列解法：从“堆”到“指针”逐行拆解

3.1 核心循环与入堆次数

优先队列解法的思路，其实就是文章开头那句直觉的“高配版”：与其每次从头到尾扫 K 个节点找最小值，不如把这 K 个节点丢进一个小顶堆，堆顶永远是最小的那个。

过程分四步：

1. 遍历输入数组，把每个非空链表的头节点放进最小堆。
2. 从堆顶弹出一个节点，它就是当前全局最小的节点。
3. 把弹出的节点接到结果链表尾部。
4. 如果这个弹出的节点还有next，把next推入堆中。

循环往复，直到堆空。

为什么总复杂度是 O(T log K)？因为每条链表的每个节点只入堆一次、出堆一次，入堆出堆操作各 O(log K)。总共 T 个节点，堆操作带来 T × O(log K) = O(T log K)。

这里最反直觉的一点是：堆里最多同时存在 K 个节点，而不是 T 个。因为每条链表在任何时刻最多只会向堆里贡献“当前头节点”这一个元素，被弹出的节点会立刻被它的next顶替。所以你用一个容量为 K 的堆就足够，这也是空间复杂度 O(K) 的来源。

3.2 Python 实现与“元组比较”的坑

Python 里最方便的是heapq，但这里有一个 90% 新手会踩的坑：heapq默认直接比较元素大小，而链表节点对象ListNode本身没有定义大小比较。如果直接把节点推进堆，会抛错：TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'。

解决办法是往堆里存元组(val, index, node)，让元组的前两个元素先参与比较，这样永远轮不到比较node对象本身。

import heapq def mergeKLists(lists): heap = [] # 第 1 步：把所有非空头节点放入最小堆 for i, head in enumerate(lists): if head: heapq.heappush(heap, (head.val, i, head)) dummy = ListNode(-1) tail = dummy while heap: _, _, node = heapq.heappop(heap) # 接到结果链表尾部 tail.next = node tail = node # 用下一个节点填补该链表在堆中的位置 if node.next: heapq.heappush(heap, (node.val, i, node.next)) return dummy.next

注意上面代码里i在循环外部定义，严格说node.next入堆时不能复用旧的i。这里因为一个链表在堆里同时只有一个节点，所以旧的i仍然能代表这个链表的下标，但为了可读性和避免误解，更准确的做法是在弹出时把i一起取出来：

while heap: val, i, node = heapq.heappop(heap) tail.next = node tail = node if node.next: heapq.heappush(heap, (node.next.val, i, node.next))

这样每个链表的下标i跟着它的节点走，语义就干净了。

元组里放i还有一个作用：当两个节点的val相等时，元组会比较第二个元素。由于每个链表只有“当前头节点”在堆里，i是唯一的，所以一定能区分两个节点，不会触发node对象的比较。如果省掉i，只存(val, node)，两个节点值相等时就会比较node对象，又回到 TypeError。

另一种规避方案是给ListNode写__lt__方法：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def __lt__(self, other): return self.val < other.val

这样heapq可以直接对节点对象建堆。但我不太建议在刷题时改节点类定义，因为这会污染整个工程环境，而且有些平台禁止你修改已给出的类。元组大法更通用。

3.3 Java 实现与比较器细节

Java 里用PriorityQueue，它的默认堆序由Comparator决定。因为题目要求最小堆，所以比较器要让值小的节点优先级高：

public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>( (a, b) -> Integer.compare(a.val, b.val) ); for (ListNode head : lists) { if (head != null) { pq.offer(head); } } ListNode dummy = new ListNode(-1); ListNode tail = dummy; while (!pq.isEmpty()) { ListNode minNode = pq.poll(); tail.next = minNode; tail = minNode; if (minNode.next != null) { pq.offer(minNode.next); } } return dummy.next; }

这里有一个比较器的小知识点：为什么推荐Integer.compare(a.val, b.val)，而不是直接写a.val - b.val？因为减法在极端情况下可能溢出，虽然链表的 val 范围通常不会大到触发它，但写成Integer.compare是更严谨的工程习惯，面试时也能体现你的代码洁癖。

Java 的PriorityQueue和 Python 的heapq有一个差异：Java 的堆允许“相等”的元素存在。即使两个节点值相同，比较器返回 0，堆依然能正常工作，只是不保证输出稳定。本题不要求稳定，所以不存在问题。

3.4 空间复杂度复盘

“为什么堆的空间是 O(K)”这个问题，我自己一度也绕了一下。直觉上觉得所有节点都要进堆，空间应该是 O(T) 才对。但仔细看循环逻辑：每条链表每次只贡献一个“当前节点”，一个节点被弹出后，它的next才会进堆。也就是说，堆里任意时刻的元素数量最多等于还没有空的链表数量，不可能超过 K。这和“把 K 个有序数组做多路归并时，选择区只用 K 个元素”是同一个原理。

4. 分治合并：不用堆也能做到 O(T log K)

4.1 归并排序思路迁移

分治合并的思路，本质上就是把归并排序的“分组再合并”思想搬到链表上。

归并排序对数组做的事：先对半切、切到只剩一个元素，再两两有序合并，最终得到一个完整有序数组。合并 K 个升序链表也一样：先把 K 条链表两两配对合并，得到 K/2 条更长的链表；再两两配对合并，得到 K/4 条……直到只剩一条。

每一轮，所有节点恰好被访问一次。总共有 log K 轮（因为每轮链表数量减半），所以总复杂度 O(T log K)。递归版额外空间来自递归栈 O(log K)，迭代版不借助递归时，额外空间可以做到更省。

这个方法理解起来很像“比武大会”：第一轮 K 个人两两对决，第二轮胜者继续两两对决，直到决出总冠军。

4.2 递归分治模板

递归版的思路和归并排序的mergeSort几乎一模一样，写起来很直观。

def mergeKLists(lists): if not lists: return None return mergeRange(lists, 0, len(lists) - 1) def mergeRange(lists, left, right): if left == right: return lists[left] if left > right: return None mid = (left + right) // 2 l1 = mergeRange(lists, left, mid) l2 = mergeRange(lists, mid + 1, right) return mergeTwoLists(l1, l2)

这个写法的好处是结构清晰：先递归处理左半部分链表，再递归处理右半部分，最后用前面讲过的mergeTwoLists合并两条有序链表。递归层数只有 log K，栈空间很小，一般不会爆栈。

要注意left > right的情况。当lists[1..0]这种空区间出现时，返回None而不是直接访问lists[left]，否则会越界。

4.3 迭代分治写法与边界

如果你不想用递归，迭代版的经典写法是用一个interval来控制两两合并的距离：

def mergeKLists(lists): if not lists: return None n = len(lists) interval = 1 while interval < n: for i in range(0, n - interval, interval * 2): lists[i] = mergeTwoLists(lists[i], lists[i + interval]) interval *= 2 return lists[0]

这里的interval表示当前要合并的两条链表在数组中的距离。interval = 1时，合并lists[0]和lists[1]、lists[2]和lists[3]……结果放回左边位置。interval = 2时，合并lists[0]（前两条合并完的链表）和lists[2]（第三、四条合并完的链表）。

很多人在for循环的范围上绕不清楚。range(0, n - interval, interval * 2)的作用是确保访问lists[i + interval]时不会越界。举个例子，如果n = 5, interval = 2，那么i能取 0，因为0 + 2 < 5；如果i = 2，则2 + 2 = 4 < 5其实也不越界，但因为步长是 4，i = 2不会出现。这时最后一条链表lists[4]暂时不参与合并，等到interval = 4那一轮，i = 0，lists[0]和lists[4]合并，最终所有链表还是会汇聚到lists[0]。换句话说，奇数个链表的情况会自动在最后一轮被“额外”合并进去。

这个原地改lists[i]的做法有一个额外好处：不产生新数组，空间上更省。它把合并结果直接覆盖在原有位置，原链表节点被重新拼接，不需要新建节点。

4.4 分治 vs 堆：实际写代码的风格差异

分治和堆的时间复杂度一样，但代码风格给人的感觉完全不同。堆解法更“在线”，你随时知道当前全局最小值是谁，逻辑是一条直线。分治解法更“批次化”，先把底层小问题处理好再逐层合并，逻辑是树形的。

我自己在面试手写时，更倾向于堆解法，因为它只需要维护一个容器和一条结果链，状态变量少。但如果面试官追问“能不能不用堆/减少额外空间”，分治迭代版就是一个非常漂亮的答案。两种都掌握是最好的状态，真到考场可以根据题目限制灵活出招。

5. 调试“合并 K 个升序链表”时我反复踩过的坑

5.1 空链表和空数组的边界

这种题最容易挂的地方不是合并逻辑本身，而是边界条件。

先说lists = []。这表示一条链表都没有，理应返回None。顺序合并的第一行if not lists就是干这个的。分治递归版也要注意，mergeRange只有在lists非空时才安全，所以外层要先判空。

再说lists = [None, None]。这是“有链表，但链表全是空”的情况。优先队列解法里，入堆前要检查head是否为None，否则会把None推进堆，运行时直接报错。mergeTwoLists本身能处理空链表，但入堆这个动作不能把None当节点处理。

最后是lists = [None, 1 -> 2]。堆解法进入循环后，堆里只有1 -> 2这个头节点，弹出后接到结果链，再把值为 2 的节点推入，正常跑完。分治解法中，mergeTwoLists(None, head)直接返回head，也没问题。这些边界最好在提交前用测试用例覆盖一遍。

5.2 指针丢链的具体场景

链表题最常见的 bug 是“链丢了”，也就是节点拼完后，某个指针指向了错误位置。

我曾经在一次练习中把tail = tail.next这句写在if条件外面，导致两个链表合并时，尾指针在 l1 和 l2 都不为空的情况下只跟到一个节点。最终结果是一条链表的主体正确、但尾部错乱，打印出来能看到明显的乱序。

另一个高频错误是在弹出节点后忘记让node的引用前进。比如在mergeTwoLists里：

if l1.val <= l2.val: tail.next = l1 # 少了 l1 = l1.next else: tail.next = l2 # 少了 l2 = l2.next

如果少了l1 = l1.next，下一轮循环l1还是同一个节点，这就会导致同一个节点被反复拼接，最终链表出现成环或重复节点，程序甚至可能死循环。

我总结了一个检查习惯：每次把一个节点接到新链表后，至少要同步做两件事——让新链表的尾指针前进，让原链表的当前指针也前进。这两个动作一个都不能少。

5.3 Python 堆比较报错的两个解决方案

Python 的堆比较坑我前面提过，这里再展开说明一下完整症状：当你把ListNode对象直接heappush进去时，Python 会尝试比较堆里的元素。如果两个元素都是ListNode，它就会调用<运算符，而ListNode没有定义这个运算符，于是报错。

解决方案有两个：

方案一：用元组(val, index, node)包装节点。这个方案的普适性最强，也是网上刷题最常见的写法。

方案二：给ListNode定义__lt__，让节点对象自身可比较：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def __lt__(self, other): return self.val < other.val

方案二在工程上不推荐，因为会改动公共节点类的行为，可能影响其他地方。但如果在允许修改节点类的刷题环境里，它确实让代码更简洁。

5.4 自测输出与用例核对

刷链表题一定要会写“链表转字符串”的辅助函数，否则肉眼 debug 非常痛苦。我一般这么写：

def list_to_str(head): vals = [] while head: vals.append(str(head.val)) head = head.next return " -> ".join(vals)

然后构造一个小测试：

l1 = ListNode(1, ListNode(4, ListNode(5))) l2 = ListNode(1, ListNode(3, ListNode(4))) l3 = ListNode(2, ListNode(6)) lists = [l1, l2, l3] merged = mergeKLists(lists) print(list_to_str(merged)) # 期望输出：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

这个用例覆盖了多个常见情况：链表的第一个节点值相等（1 和 1）、有链表比别的短、末尾有较大的值（5 和 6）。三种解法都要用同样的用例验证输出一致。

我还喜欢额外测一组“一条链表为空”的用例，比如lists = [None, l1]，确认输出就是l1本身。这样能快速排除边界条件写错的问题。

6. 从这题延伸出去的两条线

6.1 多路归并与外部排序

“合并 K 个升序链表”不是一个孤立的面试题，它背后是经典的多路归并（Multi-way Merge）。数据库做排序、日志系统合并多个有序文件、大数据处理里的外部排序，核心都离不开“K 路有序序列合并成一个有序序列”这个操作。

外部排序尤其典型：当数据量大到内存放不下时，会把大文件切分成多个分段，每段排好序写在磁盘上，最后用多路归并把这些分段合并成最终有序文件。归并阶段用最小堆来维护 K 路文件的当前最小记录，和这道题里用堆等价的思路完全一致。区别只是数据来源从链表节点变成了文件读取缓冲区。

所以这道题学会之后，你对堆在“流式取最小”场景下的理解会上一个台阶，不再认为堆只是用来做 Top K 的。

6.2 变体题：合并 K 个有序数组

如果把链表换成 K 个升序数组，思路几乎可以直接平移。

数组版本的区别主要在三处：

1. 你需要记录“当前索引”而不是用node.next取后继。
2. 数组为空时，要维护一个“该路已结束”的状态。
3. 分治版本的合并函数需要处理数组拷贝或原地合并。

堆版本的数组实现思路大致是：堆里每个元素是一个三元组（值, 数组编号, 元素下标），弹出后把同数组的下一个元素入堆。链表版本的哑节点和尾指针套路完全不需要，直接往结果数组里 append 就行。

这道变体题在面试里也很常见，学完原题后顺手推一下数组版，基本就是 10 分钟的事。

6.3 一点个人体会

我做完“合并 K 个升序链表”之后最大的收获，不是背下了代码模板，而是养成了一个习惯：写任何一版解法前，先问自己两个问题——每个节点会被访问几次？额外容器里最多同时存在几个元素？这两个问题想清楚，复杂度的计算自然就通了，代码也不会跑偏。刷题不是为了背答案，而是通过一道题把一类题的复杂度直觉建立起来。如果读完这篇你想动手，建议把顺序合并、分治合并、堆合并三种写法都各写一遍，再用同一组测试用例互相验证。代码写得多了，这些细节才会真正变成肌肉记忆。