合并 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)从空链表开始依次和每条链表 mergeTwoK 很小或练手时可用分治两两合并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; } PriorityQueueListNode 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((NK) 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)的习惯总没坏处。第二种常见写法是匿名内部类PriorityQueueListNode pq new PriorityQueue(lists.length, new ComparatorListNode() { 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 理解成“当前要合并的两条链表在原数组中的距离”第一轮 step1合并 i 和 i1跨两步第二轮 step2合并 i 和 i2跨四步。每轮结束后 step 翻倍。如果数组长度是奇数最后落单的那条链表不参与合并直接保留下一轮再和前面的结果合并。理解了这个语义写起来就不容易错。3.3 为什么分治能绕过顺序合并的退化我们具体算一笔账。假设 N 个节点平均分布在 K 条链表上每条长度约 N/K。顺序合并第一轮合并第 0 和第 1 条扫描约 2N/K 个节点第二轮合并结果和第 2 条扫描约 3N/K 个节点到第 i 轮扫描约 (i1)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) 是怎么来的用数据说话只看公式可能不够直观我拿具体数字算一次。假设 K100N100000每条链表平均长度 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.valInteger.compare(a.val, b.val)或Comparator.comparingInt(a - a.val)未判空入堆pq.offer(lists[i])先判断lists[i] ! null再 offer虚拟头节点返回错return curreturn 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)。”通常这时候面试官会让你选一个写优先队列写起来最顺手。第四步等写完代码主动说一下复杂度推导过程和关键边界条件比如 K0、空链表、虚拟头节点、比较器选择。最好再补一句“堆里最多只有 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 路归并、外部排序、优先队列应用和链表指针操作。下一次再遇到任何“多个有序流合并”的变体你都应该有底气说这题的核心我熟。