合并 K 个升序链表，这道题几乎每个刷算法的人都会碰到。它题目很短，但考点密度相当高：链表遍历、指针修改、堆的使用、分治思想、复杂度推导，甚至还能延展到外部排序。如果你只是背一个 PriorityQueue 版本，面试时被追问“为什么能做到 O(N log K)”“和顺序合并差在哪”往往会卡住。这篇文章我打算把这道题从直觉到代码、从暴力到最优、从刷题到工程类比全部过一遍，尤其适合那种“看得懂答案、自己写总是差一点”的读者。
1. 先把题目拆开：K 个升序链表到底在考什么
1.1 题目原型与核心考点
题目本身很简洁：给你 K 个已经按升序排列的单链表，每个链表内部有序，但链表之间的节点值没有全局顺序，要求把这 K 条链表合并成一条完整升序链表。比如输入三条链表[1,4,5]、[1,3,4]、[2,6]，合并后应该是[1,1,2,3,4,4,5,6]。特别注意：这里的 K 可以是 0，可以是 1，也可以很大，输入数组中的某个链表还可能是空链表。
这道题表面上是链表操作，本质上却是“多路归并”问题。所谓多路归并，就是从 K 个已经有序的序列中，每次选出当前最小元素，依次拼接成全局有序序列。在数据库排序、外部排序、日志合并、多路文件归并这些真实场景里，你面对的不是 K 个链表，而是 K 个有序文件或 K 个有序数据流，但核心逻辑完全一致。所以这道题才这么常考：它不是单纯的链表练习，而是用链表这种数据结构，考察你能否理解多路归并的最优实现。
考点可以拆成三层。第一层是链表基本功，虚拟头节点、尾插法、空指针判空，这些写不对就直接崩。第二层是数据结构和算法选择，到底是顺序合并、分治合并还是最小堆，每种做法的复杂度和适用场景必须能讲清楚。第三层是思维延展，能不能从“合并 K 个升序链表”联想到“合并 K 个升序数组”“外部排序里的 K 路归并”，面试官往往从这里判断你是背题还是真懂。
1.2 复杂度下界：为什么至少要想清楚 N 和 K
在写代码之前，先把复杂度问题想明白。设所有链表一共有 N 个节点，链表个数为 K。极端情况是 K 等于 1，那直接返回原链表，复杂度 O(N)；另一个极端是 K 接近 N，比如 N 个链表每个链表只有一个节点，这等价于对 N 个元素做全排序，复杂度至少是 O(N log N)。所以这道题的复杂度会随 K 的变化在一个范围内浮动。
最直观的做法是每次扫描 K 个链表的头节点，选出最小那个取出来，输出一个节点就要比较 K 次，总共 N 个节点，整体复杂度 O(KN)。当 K 很小的时候这没什么，但 K 一大就彻底废掉。要想优化，核心在于“每次从 K 个候选里快速找到最小值”。线性扫描是 O(K)，如果能用堆把这一步降到 O(log K)，整体就是 O(N log K)。这就是这个题目最重要的思路转折：候选集合不变，变的只是从候选集中取最小值的代价。
严格说，基于比较的模型下，合并 K 个有序序列的复杂度下界是 O(N log K)，因为每个元素在归并过程中需要参与约 log K 次选择。你不需要把这个下界背得多么数学化，但至少要明白：O(N log K) 不是凭空想出来的最优解，而是“多路归并用堆取最小”的自然结果。
1.3 三种主流解法横向对比
我在看别人代码的时候，习惯先把所有解法的复杂度摆在一张表里，然后才动手写。这里也先给你一张对比表。
| 解法 | 时间复杂度 | 空间复杂度 | 核心思路 | 推荐指数 |
|---|---|---|---|---|
| 全部收集再排序 | O(N log N) | O(N) | 遍历所有节点存数组，排序后重建链表 | 不推荐，但可作为开场白 |
| 顺序两两合并 | O(KN) | O(1) | 从空链表开始，依次和每条链表 mergeTwo | K 很小或练手时可用 |
| 分治两两合并 | O(N log K) | O(log K) 递归栈 / O(1) 迭代 | 两两配对合并，每轮链表数减半 | 空间敏感场景优先 |
| 优先队列（最小堆） | O(N log K) | O(K) | 维护 K 个头节点，每次取最小 | 面试最推荐 |
这张表应该背下来。面试时如果被要求“写一个效率高的解法”，优先队列是最稳妥的选择；如果被问“能不能不用额外堆”，分治合并就是答案；如果被问“最笨的办法是什么”，顺序合并或者全部排序都能讲。真正拉开差距的，是你能不能把这些解法按演进顺序讲成一个完整的故事，而不是只会其中一种。
2. 优先队列解法：面试最推荐的入口
2.1 最小堆维护“当前最小候选”
优先队列解法的直觉非常容易建立：既然 K 个链表都是升序的，那么全局最小值一定在这 K 个头节点里。取出这个最小值之后，下一个全局最小值会在“原来那个链表的第二个节点”和“剩下 K-1 个头节点”之间产生。所以你需要维护一个动态变化的候选集合，这个集合始终装的是每个链表当前还没被取出的最前面的节点，也就是所谓的“当前头节点”。
如果每次从 K 个候选里线性找最小，最坏情况是 O(K)。但如果把这些候选放进一个最小堆，堆顶永远是全局最小，取堆顶是 O(1)，删除堆顶（poll）是 O(log K)，插入一个新候选也是 O(log K)。每个节点最多进入堆一次、出堆一次，所以总复杂度就是 O(N log K)。这个复杂度分析必须当场能推出来，否则面试官会觉得你只是背了代码。
堆的规模始终不会超过 K，因为每个链表在任何时刻最多只有一个节点在堆里。这一点很重要：如果一个链表当前头节点已经被取走，只有它的 next 才有资格进入堆，所以堆中不会同时出现同一个链表的两个节点。这也是为什么空间复杂度是 O(K)，而不是 O(N)。
2.2 Java 实现与关键注释
用 Java 写最直接的版本，PriorityQueue 天然就是最小堆。完整代码如下：
public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } PriorityQueue<ListNode> pq = new PriorityQueue<>( Comparator.comparingInt((ListNode node) -> node.val) ); for (ListNode head : lists) { if (head != null) { pq.offer(head); } } 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; }几个地方必须注意。第一，lists本身可能是 null，数组长度可能是 0，所以要提前判空。第二，入堆时要跳过空链表，否则pq.offer(null)会在比较器里直接空指针。第三，一定要用虚拟头节点dummy，这样不需要单独处理“结果链表第一个节点从哪来”的问题，最后return dummy.next就是完整结果。第四，node.next入堆前不需要把node.next置空，因为后面cur.next = node和cur = cur.next会逐渐把node.next覆盖成真正的后继节点。
这里我想重点解释一下“不需要断链”这个很多人容易想不通的点。假设有三个节点依次出堆，前一个节点出堆时，它的 next 指向的还是原来链表中的后继。但当你把下一个出堆节点挂到cur.next时，实际上就是把上一个节点的 next 覆盖成了新的后继。整个过程相当于用归并顺序重排了原链表节点之间的连接，最终结果天然就是一条完整、无环的升序链表。真正出堆的最后一个节点一定是某个链表的尾节点，next 本来就是 null，所以结果链表的尾部也不会残留多余指针。
2.3 复杂度与空间占用逐项算清
优先队列解法的复杂度可以拆成三部分看。
第一部分是初始化：把 K 个头节点依次 offer 进堆，单次 offer 最坏 O(log K)，所以初始化是 O(K log K)。第二部分是主循环：一共有 N 个节点会从堆里 poll 出来，每次 poll 是 O(log K)，所以这部分是 O(N log K)。第三部分是重新入堆：每个节点被 poll 后，如果它有 next，就会把 next offer 进堆。这里要注意，除了初始那 K 个头节点，剩下的 N-K 个节点都是在某个前驱节点被 poll 时才入堆的，所以总共入堆次数也是 N 次，单次 O(log K)，总 O(N log K)。
常有人问：为什么不是 O((N+K) log K)？其实 K 个初始头节点和后续节点都属于 N 个总节点的一部分，合并起来就是 O(N log K)。当 K 远小于 N 时，这个复杂度比 O(N log N) 要好不少；当 K 接近 N 时，退化成 O(N log N)，这也是合理的，因为那时候问题本质上就是一个排序问题。
空间占用主要有两块。第一块是堆本身，最多 K 个节点，空间 O(K)。第二块是虚拟头节点和几个指针，O(1)。如果你选择新建节点而不是复用原节点，额外空间会变成 O(N)；但通常算法题允许修改原链表，所以复用节点才是默认做法。我在面试时一般会主动说一句“我复用原链表节点，不额外申请节点对象”，这会让面试官知道你有空间意识。
2.4 比较器细节：别在这里写出隐蔽 Bug
写 PriorityQueue 时最容易翻车的不是主体逻辑，而是比较器。
第一种常见写法是 lambda：(a, b) -> a.val - b.val。这种写法看起来没问题，但理论上有整数溢出风险。如果a.val恰好是Integer.MAX_VALUE，而b.val是负数，相减可能越界，导致比较结果错误。刷题时节点值一般不会给你这种极端数据，但养成用Integer.compare(a.val, b.val)的习惯总没坏处。
第二种常见写法是匿名内部类：
PriorityQueue<ListNode> pq = new PriorityQueue<>(lists.length, new Comparator<ListNode>() { public int compare(ListNode a, ListNode b) { return Integer.compare(a.val, b.val); } });这段代码能正常工作，但如果你忘了写Comparator，直接new PriorityQueue<>(lists.length)，那么 PriorityQueue 会尝试用 ListNode 的自然顺序，也就是Comparable接口。ListNode 没有实现Comparable，会在运行时抛出ClassCastException。我见过不少人死在这里，报错信息一出来还一脸懵。
还有一个细节：当两个节点的 val 相等时，比较器返回 0，堆并不保证它们的相对顺序，但对这道题没有影响，因为相等值的节点谁先谁后最终结果都是升序。如果你是处女座，想保证稳定顺序，可以在比较器里继续比较节点编号或对象内存地址，但那是画蛇添足，还会引入不确定性。所以直接什么都别做，返回 0 就完事。
3. 分治合并：不借助堆也能做到 O(N log K)
3.1 两两合并的递归模型
如果你觉得堆解法很巧妙，那么分治合并的思路更直白：先写一个合并两条升序链表的函数 mergeTwo，然后把 K 条链表两两配对，合并成 K/2 条，再把这些结果两两配对，直到只剩下一条。这个过程和归并排序的“分治”完全同构，区别只是归并排序处理的是数组区间，这里处理的是链表数组。
举个例子。假设有 8 条链表，第一轮把第 0 和第 1 条合并、第 2 和第 3 条合并、第 4 和第 5 条合并、第 6 和第 7 条合并，得到 4 条链表；第二轮再把得到的 4 条两两合并，得到 2 条；第三轮合并最后 2 条，得到 1 条。每一轮处理的所有节点加起来都是 N 个，但一共只进行 log2(K) 轮，所以总复杂度是 O(N log K)。
最关键的一点是：分治避免了顺序合并那种“前面越合并越长，后面每一轮都要重新扫一遍前面所有节点”的退化。分治的每一轮都是均匀地把链表数量减半，每条链表在每一轮里只被扫描一次，不存在反复扫描累计长度的问题。
3.2 递归与迭代两种实现
先写 mergeTwo，这是最基础的能力：
private ListNode mergeTwo(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 != null ? l1 : l2; return dummy.next; }然后分治合并有两种写法。递归版更贴近“分治”的语义，代码很清晰：
public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } return mergeRange(lists, 0, lists.length - 1); } private ListNode mergeRange(ListNode[] lists, int left, int right) { if (left == right) { return lists[left]; } int mid = (left + right) >>> 1; ListNode l1 = mergeRange(lists, left, mid); ListNode l2 = mergeRange(lists, mid + 1, right); return mergeTwo(l1, l2); }这里mid = (left + right) >>> 1是为了防止 left + right 整数溢出，虽然在这个场景不太可能，但好习惯值得保留。递归深度是 log K，所以递归栈空间是 O(log K)。
迭代版更省空间，不需要递归栈，也避免了递归方法调用带来的微小开销：
public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } int step = 1; while (step < lists.length) { for (int i = 0; i + step < lists.length; i += step * 2) { lists[i] = mergeTwo(lists[i], lists[i + step]); } step *= 2; } return lists[0]; }迭代版的循环变量很容易写错。我建议先把 step 理解成“当前要合并的两条链表在原数组中的距离”，第一轮 step=1，合并 i 和 i+1，跨两步；第二轮 step=2，合并 i 和 i+2，跨四步。每轮结束后 step 翻倍。如果数组长度是奇数，最后落单的那条链表不参与合并，直接保留，下一轮再和前面的结果合并。理解了这个语义，写起来就不容易错。
3.3 为什么分治能绕过顺序合并的退化
我们具体算一笔账。假设 N 个节点平均分布在 K 条链表上，每条长度约 N/K。顺序合并第一轮合并第 0 和第 1 条，扫描约 2N/K 个节点；第二轮合并结果和第 2 条，扫描约 3N/K 个节点；到第 i 轮，扫描约 (i+1)N/K 个节点。把所有轮叠加起来，大约是 (N/K) * (1 + 2 + ... + K) = O(KN)。
分治合并就不是这个加法。第一轮每两条链表合并，每条长度 N/K，两条合起来长度 2N/K，一共有 K/2 组合并，所以第一轮扫描总量约 (2N/K) * (K/2) = N。第二轮合并长度 2N/K 的两条链表，结果是长度 4N/K，合并次数 K/4，扫描总量还是约 N。每一轮都扫描约 N 个节点，一共有 log K 轮，总 O(N log K)。差别就在这里：顺序合并是“累积扫描”，分治是“轮转扫描”。
这个对比是我觉得整道题最值得讲透的地方。很多人会背分治复杂度是 O(N log K)，但被问“为什么和顺序合并不一样”就卡壳。你可以用这个计算方式现场推导，不需要记任何结论。
3.4 优先队列与分治的场景选择
既然两种解法都能达到 O(N log K)，面试时到底选哪个？我的判断标准有三个。
第一，如果面试官没有额外限制，优先队列代码更短，思路更直观，推荐优先写它。面试时写代码速度快、不容易出错，本身就是很大的优势。
第二，如果面试官追问“能不能不用额外堆”“空间复杂度能不能更低”，分治合并就是答案。迭代版分治的空间复杂度是 O(1)（不算结果链表），递归版是 O(log K) 的栈空间，明显比优先队列的 O(K) 更省。
第三，如果 K 特别大，比如几万条链表，优先队列的堆维护成本仍然可控，但初始化堆和频繁 offer/poll 的常数并不小；分治合并没有堆的常数开销，但链表数组本身需要反复访问。实际工程里还要考虑 IO 成本，比如合并 K 个文件，优先队列每次取一个元素就要从对应文件读一次，分治合并则每轮都要重新读一遍文件，这时候优先队列往往更合适。
所以不存在绝对优劣，只有“在什么约束下选什么”。面试时能说出这种权衡，比给一个标准答案更值钱。
4. 顺序合并：最直觉的解法，也是最容易翻车的解法
4.1 顺序合并的代码与复杂度
顺序合并应该是所有人第一反应能想到的解法：先让结果链表 res 等于空，然后依次把每条链表和 res 合并，调用之前写好的 mergeTwo。代码如下：
public ListNode mergeKLists(ListNode[] lists) { ListNode res = null; for (ListNode list : lists) { res = mergeTwo(res, list); } return res; }这段代码非常短，正确性也好理解：维护一个“当前已经合并好的链表”，每遇到一条新链表，就和它做一次两两合并。它的时间复杂度和上面的分治计算差不多：第 i 次合并的对象是已合并的 i 条链表，长度大约是之前的累计，每次合并都要扫描到其中较短的一条链表走到末尾。整体加起来就是 O(KN)。
换句话说，顺序合并和分治合并虽然都叫“两两合并”，但顺序合并每一次都是把当前结果和一个新链表合并，结果链表长度单调增长；分治合并则是把短链表先合并成中等链表，再合并成长链表，有效避免了对长链表的反复扫描。
4.2 O(KN) 是怎么来的，用数据说话
只看公式可能不够直观，我拿具体数字算一次。假设 K=100，N=100000，每条链表平均长度 1000。顺序合并时，前几次还能接受，到第 50 次以后，res 长度已经接近 50000，每次 mergeTwo 都要扫完这 50000 个节点的一半或全部；等到了最后一次，res 长度是 99000，再和最后一条 1000 长度的链表合并，又要扫接近 10 万个节点。所有轮次加起来，总的扫描次数大约是 1000 * (1 + 2 + ... + 100) = 505 万，这是百万级。如果 K 变成 10000，哪怕 N 不变，这个数会变成 5000 万甚至更多，肉眼可见地变慢。
所以面试如果说了顺序合并，必须主动补一句：“这个解法在 K 很大的时候会退化成 O(KN)，我可以继续优化。”这句话一说，面试官就知道你不是只会写暴力解。最怕的是你写完顺序合并就停下来，觉得题目已经做完了，那面试评价会非常低。
4.3 什么时候顺序合并反而够用
虽然 O(KN) 听起来吓人，但实际工程里 K 很小的时候根本没有必要上堆。比如你手上只有 2 条有序链表，mergeTwo 是标准的链表合并操作，随手写出来就是最优。3 条、4 条的时候顺序合并也完全能扛住，代码简单，出 bug 概率低，比维护一个堆更不容易写错。
所以真正的判断标准不是“哪种解法复杂度好看”，而是“你的数据规模是什么”。如果 K 是常数且很小，O(KN) 和 O(N log K) 的差距不大，选最简单的实现反而更符合工程精神。这一点在面试里可以体现你的工程判断力，而不是盲目追求“最优复杂度”。
5. 实操中的边界、指针与常见错误
5.1 空输入与单链表这些边界条件
链表题十有八九的 bug 出在边界条件。这道题的输入是一个链表数组，所以边界比单链表题还多一些。
第一，lists本身可能是 null，也可能是长度为 0 的数组，两者都要返回 null。有的写法只判断lists.length == 0，一旦传入 null 就直接空指针。第二，lists.length == 1时，直接返回lists[0]即可，不需要走堆或分治。第三，数组里某些元素可能是 null，也就是存在空链表，入堆时要跳过。第四，如果所有链表都为空，结果应该是 null，而不是一个包含头节点 0 的链表，所以dummy.next天然就是 null，不需要额外处理。
还有一个容易被忽略的点：链表长度可能很大，节点值可能是负数。最小堆的比较器要能处理负数，这本身不是问题，但如果你在代码里用了类似“先把最小值设成 0”的变量，就可能会漏掉负数。好在堆解法不涉及手动维护最小值变量，这件事只在一开始写暴力扫描时会出现。
5.2 复用节点还是新建节点
算法题里通常允许复用原节点，也就是说你可以直接改变节点的 next 指针，把原链表节点重新串成结果链表。这样做的空间复杂度是 O(1)，对堆解法来说额外空间只有堆里的 O(K) 指针。
如果题目要求不能修改原链表，或者你担心面试官不喜欢副作用，那就得新建节点：每次从堆里取出一个节点，就new ListNode(node.val)并挂到结果链上。这样空间复杂度变成 O(N)，但原链表完全不受影响。实际刷题时我默认按“复用节点”写，因为大多数在线评测系统不限制修改输入链表，而且代码更省空间。如果你拿不准，可以写代码前问一句“可以修改原链表吗”，这比默默新建 N 个节点更稳妥。
复用节点唯一需要小心的点是别让结果链表里残留旧链表的 next 指针。虽然我前面解释过，按正确顺序从堆里取节点并重新连接，最后一个出堆节点一定是原链表的尾节点，next 为 null，但如果你用顺序合并并搞错了 mergeTwo 的 tail 维护，就可能出现“链表尾部莫名其妙多出一截”的现象。所以写完代码一定要在脑子里跑一个跨越两条以上链表的用例，比如[1, 3]和[2, 4]，确认最后 tail 的 next 是 null。
5.3 高频 Bug：比较器、断链与死循环
把我在调试中见过的高频 bug 整理成一张速查表：
| 问题 | 错误写法 | 正确做法 |
|---|---|---|
| 比较器溢出 | (a,b) -> a.val - b.val | Integer.compare(a.val, b.val)或Comparator.comparingInt(a -> a.val) |
| 未判空入堆 | pq.offer(lists[i]) | 先判断lists[i] != null再 offer |
| 虚拟头节点返回错 | return cur | return dummy.next |
| 分治递归边界错 | 递归时 mid 取错，导致区间重叠 | 用mid = (left + right) >>> 1，分治区间要互斥 |
| 迭代步长错 | for (int i = 0; i < lists.length; i += step) | 应该是i += step * 2，并且只合并i + step < lists.length |
| 没有复用 mergeTwo | 每轮都重新写合并逻辑 | 单独写一个mergeTwo工具函数，减少出 bug 概率 |
还有一个比较隐蔽的坑是“节点的 next 指向自己”。这种情况不会出现在这道题的正常输入里，但如果你在优化时试图手动把某节点从原链表里“拆出来”，用类似node.next = null的操作，然后又把节点挂回结果链，容易搞混指向。标准解法并不需要手动拆节点，因为堆只保存节点的值信息，真正连接关系是在cur.next = node时重建的。所以老老实实按标准写法，不要过度设计。
死循环的常见来源是 while 条件写错。堆解法的while (!pq.isEmpty())很安全；顺序合并的while (l1 != null && l2 != null)也安全，但如果你写成while (l1 != null || l2 != null)而不在循环体里判空，就可能在内层一直尝试访问空节点。分治递归则要注意left == right一定要返回lists[left]，否则无限递归。这些都是老生常谈，但每次都会有人踩。
5.4 逃不开的工程类比：多路归并与外部排序
前面说了这道题本质是多路归并，工程上最经典的对应就是外部排序。当数据量大到无法全部读入内存时，你需要先把大文件切分成若干块，每块内部排序后写回磁盘，形成多个有序片段，然后再把这些有序片段合并成一个完整有序的大文件。合并过程就是 K 路归并：从 K 个文件中各读一条当前最小记录，放进优先队列，每次取出一条写入输出文件，再从对应文件补一条。
这个场景和合并 K 个升序链表一一对应。链表节点就是文件中的一条记录，链表头就是每个文件的当前读指针，优先队列就是负责快速选出最小值的内存缓冲区。区别只有一个：链表节点的 next 天然指向下一条，而文件读取需要你手动 from statement 文件读入下一条。想通这一点，这道题就不再是死记的算法题，而是一类真实系统的核心抽象。
所以我在带人刷题时经常说：合并 K 个升序链表不只是为了面试，它是“多路归并”这个工程思想的最小可执行示例。你以后写归并排序、外部排序、数据库的 merge join、日志系统的多源合并，底层逻辑全是这一套。把它彻底吃透，性价比极高。
6. 面试进阶：从“会做”到“讲清楚”
6.1 给面试官的解题演进路线
如果你在面试现场遇到这道题，我建议按下面这个顺序表达，而不是直接甩最优解。
第一步，先说你马上想到的笨办法：“我可以把所有链表节点收集到一个数组里，排序后再串成链表，时间复杂度 O(N log N)，空间 O(N)。”说完这句话，马上补一句“但这样没有利用链表本身已经有序这个条件，所以不够好”。
第二步，说顺序合并：“我可以写一个 mergeTwo，然后一条一条合进来，时间复杂度 O(KN)。K 小的时候够用，K 大时会退化。”这句话展示你知道暴力解不是终点。
第三步，说有优化的两种主流方案：“一是我用最小堆维护 K 个当前头节点，每次取堆顶，时间复杂度 O(N log K)，空间 O(K)；二是我用分治两两合并，同样 O(N log K)，迭代版空间 O(1)。”通常这时候面试官会让你选一个写，优先队列写起来最顺手。
第四步，等写完代码，主动说一下复杂度推导过程和关键边界条件，比如 K=0、空链表、虚拟头节点、比较器选择。最好再补一句“堆里最多只有 K 个节点，所以空间是 O(K)”，而不是 O(N)。
这套表达不会让人觉得你在背题，因为它展示了一个从暴力到最优的自然思考过程。真正的加分项不是你第一次就写出堆解法，而是你能解释清楚为什么每一步都比上一步好。
6.2 几个值得展开的变形题
掌握了这道题，可以顺手把几个常见变形过一遍。
第一个是合并 K 个升序数组。数组和链表的核心区别是数组用下标访问，链表用 next 指针。解法完全相通：用一个类或数组存三个信息：当前值、属于哪个数组、当前下标。每次取出最小值，就把同数组的下一个下标入堆。如果你用 Java，可以定义一个内部类Node存val, row, col，或者用int[]{val, row, col}配合比较器。
第二个是找 K 个有序数组里的全局最小值或第 K 小。这其实就是堆解法只做 K 次 poll 的结果。面试官如果问“你能用 O(K log K) 找到 K 个升序数组中的全局最小吗”，本质就是把这道题换了个问法。
第三个是“合并 K 个降序链表”，解决办法只需要把最小堆改成最大堆，或者把比较器反过来。这个变形看起来简单，但能检验你是否真的理解堆的方向。
第四个是“如果链表数量极大，比如几十万条，且内存紧张”，K 路归并可能不再适合堆，因为堆需要 O(K) 内存；外部排序里会换成败者树或更节省内存的赢者树。这个问题偏系统设计，面试中如果被问到，你可以把“堆内存 O(K)”和“分治空间 O(1)”的权衡讲出来，基本就能过关。
这些变形题不用全部刷完，但至少要在脑子里过一遍思路。因为面试官很可能会在追问环节问“如果我把链表换成数组你会怎么写”，你要是当场懵掉，前面的分就白拿了。
6.3 我的个人实操体会
最后分享一点我自己刷题和带人刷题的心得。
第一，链表题永远优先写虚拟头节点。不管问题是合并两个链表、合并 K 个链表，还是反转链表的一部分，虚拟头节点能省掉至少一半的空指针判断。你可以觉得多了一个节点对象是浪费，但这点开销在算法题里完全无所谓，换来的是代码简洁和不易出错。
第二，优先队列的代码写完后，不要急着提交，先在脑子里跑三个用例：lists = []、lists = [[1]]、lists = [[1,3],[2]]。这三个用例分别覆盖空输入、单链表、跨链表交叉，能找出绝大多数边界 bug。
第三，如果你在练习时反复在同一类题上出错，大概率不是代码能力问题，而是对“多路归并”和“指针重连”的抽象没到位。我建议把 K 路归并当成一个固定套路来记：候选集用堆、每次取最小、取完补下一个。以后遇到任何“多个有序序列合并”的题，这个套路都能直接套用。
第四，不要因为这道题代码短就小看它。我见过很多人能把堆解法背得滚瓜烂熟，被问一句“分治解法的迭代版怎么写”就露馅。所以练习时优先队列和分治两个版本都要写，而且要能互推。面试真正考察的，是你对一类问题的理解深度，而不是某一个解法的肌肉记忆。
这道题能延展出去的东西比想象中多，把它的思路吃透，相当于同时掌握了 K 路归并、外部排序、优先队列应用和链表指针操作。下一次再遇到任何“多个有序流合并”的变体，你都应该有底气说：这题的核心，我熟。
