从逐一合并到多路归并：力扣23「合并K个升序链表」的三种解法进化之路

前言

在力扣21「合并两个有序链表」中，我们学会了如何优雅地将两条有序链表合并成一条。那如果这个数字从 2 变成了 K 呢？话说回来，今天我们要攻克的。正是这道大名鼎鼎的力扣23. 合并K个升序链表。

这道题在 LeetCode 上标记为困难但它的解法思路其实清晰明了。它之所以被评为 Hard，是因为它考察的不是单一的算法技巧。而是你对多种数据结构与算法范式的综合运用能力。在字节跳动、腾讯、Google、Amazon的面试中，这道题几乎是“必刷清单”上的常客。

题目要求你合并 k 个升序链表，返回一个升序链表。这 K 条链表的总节点数为 N。按理说，

使用者痛点：

• 面试时常被问到“如果 K 很大怎么办”。很多人只能说“再循环一次”，却不知道时间复杂度到底是多少。不过，
• 卡在 “如何高效取出 K 条链表中最小节点” 这一步。不知道该用遍历还是堆，
• 实现递归分治时总担心栈溢出或代码难以阅读。

题目回顾

再看主要难点。从“一对一”到“一对多”的质变

在力扣21中，我们有两个指针分别指向两个链表的当前节点，每次取较小的那个。这相当于一场擂台赛只有两个选手，每次比较即可出结果。

K 个选手上场后最让人抓狂的是：

• 每轮都要遍历 K 条头节点寻找最小值 → O 的额外开销，让代码在大数据下直接 TLE。按理说，
• K 越大。手工维护排序越不靠谱 → 容易出现 “漏掉某条链表” 或 “重复取值” 的 bug。
• 递归层数不明确 → 担心栈溢出或递归写错导致无限循环。按理说，

# 解决思路 #

• 方案一： 每次遍历所有 K 个头节点找最小值。复杂度 O，太慢，
• 方案二： 把所有节点收集起来排序。O，浪费了已有有序特性，
• 方案三： 优先级队列 让堆帮我们维护 K 个头节点的顺序。取数 O，
• 方案四： 两两归并 把 K 条链表转化为 log K 轮两两合并问题。

说到第一层。顺序合并 —— 最直观的“逐一击破”

User Pain Point： 很多人看到 “K 条”，第一反应就是写一个 for 循环，却忽视了每次合并时 ans 链表会越来越长，导致整体时间爆炸。

class Solution {
public ListNode mergeKLists {
if return null;ListNode ans = null;for {
ans = mergeTwoLists;}
return ans;}
// 复用 “合并两个有序链表” 的标准解法
private ListNode mergeTwoLists {
ListNode dummy = new ListNode;ListNode tail = dummy;while {
if {
tail.next = l1;怎么说呢，l1 = l1.next;} else {
tail.next = l2;l2 = l2.next;}
tail = tail.next;老实说，}
tail.next =?l2 : l1，return dummy.next;}
}

复杂度分析：

• 时间复杂度： . 第一次合并处理 N₁ 节点，第二次处理 N₁+N₂ … 按理说，最坏情况下等价于 O。当 k 很大时容易超时，不过，
• 空间复杂度： 。

# 小结 #

• This method is safest fallback – if you’re stuck in an interview you can always write it and discuss its bottleneck.
• Avoid underestimating its cost: 在面试里直接说 “时间复杂度是 O” 能帮助你抢回思考时间，让面试官主动引导你调整。按理说，

至于第二层。分治法 —— 教科书级的“两两归并”

User Pain Point： 不少同学看到递归就慌：“递归深度会不会爆？说起来，”、“怎么把列表切分？”、“如何避免重复代码，” 本节通过图示和代码一步步拆解这些疑惑。

主要实现方式

class Solution {
public ListNode mergeKLists {
if return null;return merge;}
private ListNode merge {
if return lists;int mid = left + / 2;ListNode l1 = merge;ListNode l2 = merge;return mergeTwoLists;按理说，// 同上
}
// mergeTwoLists 与上一节相同
}

# 为什么能降到 O #

• K 条链表只会参与
• The recursion depth is at most log₂k → safe stack usage.

# 优缺点对比 #

至于第三层。优先队列 —— 最优雅的“多路归并”

User Pain Point： 很多语言里自带堆，但**ListNode** 没有可比性；还有人担心每弹出一个元素后忘记把 next 加回堆导致死循环或遗漏节点。其实，本段提供完整防错模板。

主要思想步骤

1. Create a min‑heap that orders nodes by ir .val..
2. Add first non‑null node of each list into heap.
3. .next..
4. The loop ends when heap becomes empty.

 // 小根堆：按照节点值升序排列
PriorityQueue pq = new PriorityQueue<>(
-> Integer.compare
);// 将所有非空头结点加入堆
for {
if pq.offer;}
ListNode dummy = new ListNode;ListNode tail = dummy;while ) {
ListNode min = pq.poll;// 弹出当前最小节点
tail.next = min;不过，tail = tail.next;// 把弹出节点的后继继续放入堆，以保持 K 路竞争
if pq.offer;}
return dummy.next;}

 heap = # 存储元组
# index 防止 val 相同导致比较错误
for i,node in enumerate:
if node:
heapq.heappush)
dummy = ListNode