力扣hot100里的第29题“合并K个升序链表”是链表类题目里性价比极高的一道题。它表面上只是把“合并两个有序链表”的逻辑复制K次但真正做进去会发现它把多路归并、堆、分治三条主线全串在了一起。我第一次刷的时候先用最暴力的“把所有节点收集起来排序”通过了后来被追问到“这道题到底比全排序快在哪”时答不上来才回去把堆解法和分治解法重新研究透。这篇就把几种解法的思路、代码模板、复杂度细节和容易翻车的地方整理出来给正在刷这题的同学一份可以直接抄作业的笔记。先说一个总体判断这道题没有“唯一的正解”。根据链表条数K和总节点数N的比例取舍会不一样从最朴素的顺序合并到堆排序、分治归并都能通过但性能差距可以很大。适合正在准备面试、被“K个有序数据合并”类题目折磨过的人也适合想一次性把链表基本功打扎实的读者。代码以Java为主C和Python的差异我会单独指出来。1. 题目拆解这道题到底在考什么1.1 题面里容易被忽略的三个细节题目本身不复杂给你一个链表数组lists每个链表都已经按升序排列要求把所有链表合并进一个新的升序链表并返回头节点。但有三处细节很多人刷的时候一带而过恰恰是后面所有解法选择的依据。第一K是不固定的。少的时候只有两个链表多的时候可能上万。面试官不会只满足于“能跑通”他更想看到你能根据不同K值给出不同方案。如果K等于2直接写二路归并就可以如果K非常大堆和分治才是合理选择。这个“根据参数选算法”的判断力比默写一种AC代码值钱得多。第二链表可以是空的lists本身也可以是空数组。这直接决定了代码开头是否要判空。我在本地调试时经常习惯性输入一个非空用例就跑结果一提交就被空输入的教育。凡是链表类题目先把“空”的可能性处理干净能避免一半以上的提交失败。第三也是最重要的每个链表已经升序。这句话是整个多路归并思路的前提。如果你打算把所有节点收集起来重新排序就等于把这个现成的有序条件白白扔掉了。后面所有高效解法全部建立在“链表内部有序因此当前头节点就是该链表剩余部分的最小值”这个事实上。1.2 为什么值得反复刷这道题在hot100里的位置很特殊。往下看它是合并两个有序链表那类基础题的扩展往上看它是K个有序数组、K路归并、外部排序这类进阶题的地基。面试官经常从这道题往外延伸比如“如果内存装不下全部数据怎么办”“如果还想知道每次取出的最小节点来自第几个链表怎么办”。能把这些追问都接住才算真正吃透了。我见过不少同学把答案背下来但换一道“合并K个有序数组”就懵了。原因在于他们只记住了“用优先队列”这个结论没有理解为什么能用、什么时候该用。本文后面也会顺着这个思路展开重点讲“为什么”而不是只给一份能AC的代码。2. 地基合并两条升序链表决定整道题的成败2.1 迭代版mergeTwo的模板合并K条链表最底层就是合并两条。不管外层用堆、用分治还是顺序遍历最后都要落到一个“给定两条升序链表合成一条升序链表”的函数上。这个函数必须熟练到能盲写不要在现场临时推。private ListNode mergeTwo(ListNode a, ListNode b) { if (a null) return b; if (b null) return a; ListNode dummy new ListNode(-1); ListNode cur dummy; while (a ! null b ! null) { if (a.val b.val) { cur.next a; a a.next; } else { cur.next b; b b.next; } cur cur.next; } cur.next (a ! null) ? a : b; return dummy.next; }这里有两个关键点。一是哑节点dummy的使用不需要单独处理“新链表第一个节点到底取谁”的分支最后统一返回dummy.next代码会干净很多。二是循环结束后不需要再遍历剩余链表直接把没走完的那条整体接上因为剩余部分本来就是升序的。另一个容易忽略的点是这个函数没有创建新节点它只是调整引用。时间复杂度O(N1N2)空间O(1)。合并K个链表时每个节点被复用不额外申请内存这也是链表操作的标准姿势。2.2 为什么优先练迭代而不是递归两条链表合并的递归写法非常短很多人喜欢背递归版private ListNode mergeTwo(ListNode a, ListNode b) { if (a null) return b; if (b null) return a; if (a.val b.val) { a.next mergeTwo(a.next, b); return a; } else { b.next mergeTwo(a, b.next); return b; } }简洁确实简洁但它会直接修改原链表的next指针递归深度又最坏达到两条链表长度之和。在链表很长、系统栈有限的环境里这就是隐患。刷题阶段为了稳我建议优先把迭代版练熟。递归版可以作为一种“思维验证”实际写代码时用迭代版调试成本低也不容易在指针关系上绕晕。把mergeTwo写好接下来讨论的几种合并K条链表的方案都是在回答同一个问题外层怎么组织这K次的归并。3. 暴力解法不是没用收集排序和顺序合并3.1 全部收集再排序最快过但面试官会追问第一次遇到这题最容易想到的办法是遍历所有链表把所有节点的值放进一个数组排序后再重新串成链表。public ListNode mergeKLists(ListNode[] lists) { ListInteger values new ArrayList(); for (ListNode head : lists) { while (head ! null) { values.add(head.val); head head.next; } } Collections.sort(values); ListNode dummy new ListNode(-1); ListNode cur dummy; for (int v : values) { cur.next new ListNode(v); cur cur.next; } return dummy.next; }这段代码在力扣上也能AC因为总节点数N有限O(N logN)的排序不至于超时。但面试官大概率会追问一句“K条链表已经各自有序你这个解法利用到这个条件了吗”答不上来会非常尴尬。问题的核心在于全排序把每个节点当成独立元素处理完全丢失了“链表内有序”的先验信息。排序比较器会对同一个链表内部的相邻节点也进行比较而其实它们在输入里已经是升序这部分比较就是白做的。3.2 顺序合并最朴素的K次二路归并收集排序之外另一个直观思路是先让结果为空链表然后从第一条链表开始依次把每条链表和当前结果合并。这相当于把mergeTwo重复K次。public ListNode mergeKLists(ListNode[] lists) { if (lists null || lists.length 0) return null; ListNode res null; for (ListNode list : lists) { res mergeTwo(res, list); } return res; }这个解法真正用上了“链表有序”的条件代码几乎不需要额外思考。但效率一般假设总节点数是NK条链表长度近似相等第一次合成长度约为2倍的链表长度第二次变成3倍越往后结果越长每次都要从头扫一遍。整体时间复杂度是O(NK)。顺序合并并不是一无是处。当K很小比如只有2条或3条时它的代码最简单常数也小没必要引入堆。但当K变成几十、几百时它会明显变慢。这个解法的定位是“思路正确效率一般”面试时可以当作递进方案的起点不要一上来就否定它。4. 高效解法一小根堆维护K个候选头节点4.1 核心不变量最小值只可能来自K个链表的头堆解法的核心我习惯称之为“K个头的不变量”。任何时候K条链表各自剩余部分的头节点就是这条链表当前最小的元素。那么整个尚未合并的节点集合里全局最小值一定在这K个头节点当中。道理很直白每个链表内部升序头节点已经是链表里的最小值跨链表比较只需要比较这些头。用一个小根堆最小堆来维护这K个候选值。每次从堆里弹出最小值接到结果链表尾部再把这个节点所在链表的下一个节点补进堆里让“K个候选头”的不变量继续成立。重复到堆为空合并就完成了。这个思路解决了两个问题一是避免了顺序合并那种反复重扫长链表的浪费每次从堆取都是O(logK)二是每个节点进堆一次、出堆一次整个过程中没有额外比较已经有序的节点。4.2 堆的完整Java代码与生命周期public ListNode mergeKLists(ListNode[] lists) { if (lists null || lists.length 0) return null; PriorityQueueListNode heap new PriorityQueue( (a, b) - Integer.compare(a.val, b.val) ); for (ListNode node : lists) { if (node ! null) heap.offer(node); } ListNode dummy new ListNode(-1); ListNode tail dummy; while (!heap.isEmpty()) { ListNode cur heap.poll(); tail.next cur; tail tail.next; if (cur.next ! null) heap.offer(cur.next); } return dummy.next; }强调几个生命周期管理的细节。初始化阶段只放K个链表各自的头节点不是把整个链表都丢进堆。如果某个头节点是null说明这条链表已经空了跳过即可。弹出阶段cur被接进结果链表后原链表的下一个节点cur.next就变成了这条链表的“新候选头”要果断补进堆。不补这条链表就断档了补了堆始终维持“当前每条非空链表的最小头节点”的语义。最后是返回。dummy是哨兵节点真正的头节点是dummy.next。有人会把上一次合并的结果或原链表的头节点误当作最终头返回这种错误很隐蔽提交后通常会在边界用例上暴露。C写在优先级队列时需要自定义比较器因为ListNode指针没有默认的比较规则注意要让比较器返回true时表示“优先级更低”写成小根堆的语义即可。Python则要留心heapq无法直接比较ListNode对象一种稳妥的做法是往堆里存三元组(val, index, node)用链表下标做第二关键字避免比较节点本身。4.3 为什么它比全排序快直观感受上堆解法的时间复杂度是O(N logK)全排序是O(N logN)。只要K明显小于N堆解法就更优。这个“优”的根源不是堆这个数据结构本身有什么魔法而是它少做了大量无效比较。全排序会对所有N个节点做两两比较复杂度里的logN来自全局排序的决策树深度堆解法只对“跨越链表边界”的候选节点做比较。同一个链表内部的相对顺序是输入条件白送的不需要重新计算。外部排序里的K路归并也是这个思想把数据切成K个有序段然后反复从K个段的头部找最小元素写回结果堆在这里正好扮演“K段中最值查询器”的角色。堆解法唯一的额外成本是O(K)的空间。堆里最多同时存在K个节点不会因为总节点数N变大而膨胀。这一点在很多内存敏感的场景里非常好用。5. 高效解法二分治两两归并5.1 归并树视角每轮总工作量都是N分治解法的框架很简单把K条链表从中间切一刀左边先合并右边先合并最后把两个结果再合并。任何一个稍微了解归并排序的人都会觉得眼熟它就是把“二路归并”从数组搬到了链表上并且从2路扩展成了K路。用归并树的视角看第一轮K条链表两两配对合并成K/2条第二轮K/2条再两两配对变成K/4条一直合并到只剩下一条。每一轮中所有链表的总长度始终是N所以每层归并的总工作量就是O(N)。一共logK层总复杂度O(N logK)。关键区别在于顺序合并为什么慢顺序合并每轮处理的结果会越来越长相当于把一条长链表反复和其他链表扫描分治则是把K条链表尽量“均衡”地配对避免某条结果链被反复完整扫很多次。分治的每一轮每条链表的长度都参与了一次完整的归并但不重复参与其他链表的扫描。5.2 递归分治模板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 - left) / 2; ListNode leftHead mergeRange(lists, left, mid); ListNode rightHead mergeRange(lists, mid 1, right); return mergeTwo(leftHead, rightHead); }递归出口是left right表示只剩下一条链表直接返回。这个模板和数组归并排序的递归结构几乎一样差别只是不需要真正“切成两段”因为每段链表天然独立。这里有个小细节mid的计算用left (right - left) / 2而不要写成(left right) / 2。虽然数组长度在int范围内几乎不会溢出但规范写法能避免极端情况下的整数溢出属于面试官会盯一眼的代码习惯。5.3 迭代版两两合并避免递归有些同学对递归有心理障碍或者担心递归栈深度可以写迭代版。思路是维护一个列表里面是当前轮次的所有链表头每轮两两取出合并把结果放进新列表直到只剩一个。public ListNode mergeKLists(ListNode[] lists) { if (lists null || lists.length 0) return null; ListListNode level new ArrayList(); for (ListNode node : lists) level.add(node); while (level.size() 1) { ListListNode nextLevel new ArrayList(); for (int i 0; i level.size(); i 2) { if (i 1 level.size()) { nextLevel.add(mergeTwo(level.get(i), level.get(i 1))); } else { nextLevel.add(level.get(i)); } } level nextLevel; } return level.get(0); }这个写法最贴近归并排序的物理过程每轮两两合并剩余一条落单就直接顺延到下一轮。空间上多了一个链表头列表但链表节点本身依然只是调整引用不额外创建。相比递归栈的O(logK)迭代版实现起来更符合直觉也方便在调试时打印每一轮的中间结果。6. 复杂度账本与选型建议6.1 四种解法横向对比表解法时间复杂度空间复杂度关键优点关键缺点收集排序O(N logN)O(N)代码最短、思路直白丢弃有序条件、大量无效比较顺序合并O(NK)O(1)只用mergeTwo、容易理解K越大越慢小根堆O(N logK)O(K)时间最优、适合大K需要额外堆空间分治归并O(N logK)O(logK)递归栈空间省、可扩展性好代码结构相对复杂单看时间堆和分治都是O(N logK)属于同一档次收集排序和顺序合并在特定场景下也各有存在意义。顺序合并在K很小的时候常数非常低。比如K2它就是一次mergeTwo比堆少了很多建堆和维护堆的开销。如果K2还去开堆就显得用力过猛了。收集排序唯一的优势是“零思考”。我偶尔在竞赛里用它快速拿分但平时练习和面试不建议把它当成主方案。尤其是当面试官明确考“多路归并”时收集排序几乎一定会被追问答不好反而减分。6.2 根据N和K的相对关系选型我自己的选型经验可以总结成三句话K很小比如2到4直接用顺序合并代码最少。K中等但链表很长优先堆解法。堆的O(N logK)稳定友好而且不需要递归出bug概率低。如果对空间有要求不希望额外维护O(K)的堆或者K非常大导致堆操作也有明显开销分治归并更合适。它只有递归栈的O(logK)理论上更省。说得更直白一点面试中如果时间紧张推荐优先写堆解法因为它的代码短、语言表达清楚面试官也容易看。如果想展示自己思路更多维度可以在堆解法前先花两分钟讲讲顺序合并的问题再给出分治归并的优化这样整个答案会有明显的递进感。7. 提交失败过的坑和调试经验7.1 最容易翻车的五个细节第一忘记判空。lists本身是null或者长度为0两种都要处理。有人只写了length为0的判断遇到null输入照样空指针。第二把null丢进堆。初始化时如果某个链表是空的而你没做if (node ! null)判断堆里就会出现null元素poll出来直接空指针。这是堆解法最经典的提交失败原因。第三比较器写成a.val - b.val。当两个值一个是Integer.MAX_VALUE另一个是Integer.MIN_VALUE时相减会溢出排序结果出错。LeetCode的测试数据可能刚好绕过了但这不是好习惯。用Integer.compare或Comparator.comparingInt更稳妥。第四返回了dummy而不是dummy.next。新建链表时用哨兵节点确实方便但最后忘记取next就会把哨兵节点也带进结果通常会错误输出一个多余的节点。第五分治递归里把left right的出口写成left right。如果lists本身不为空这个递归每次都会缩小范围left right一定先触达不需要额外判断left right。但如果列表为空上层已经做了处理这里保持简单的出口语义即可。7.2 本地调试辅助函数在LeetCode上直接调试链表看不到中间状态除非打印。很多同学不会自己构造链表导致只能在脑海里推演效率很低。我建议本地维护两个工具函数一个用数组构造链表一个把链表转成字符串。public static ListNode build(int[] values) { ListNode dummy new ListNode(-1); ListNode tail dummy; for (int v : values) { tail.next new ListNode(v); tail tail.next; } return dummy.next; } public static String listToString(ListNode head) { StringBuilder sb new StringBuilder(); while (head ! null) { sb.append(head.val).append( - ); head head.next; } sb.append(null); return sb.toString(); }有了这两个函数main方法里就能写类似这样的自测ListNode[] lists new ListNode[]{ build(new int[]{1, 4, 5}), build(new int[]{1, 3, 4}), build(new int[]{2, 6}) }; System.out.println(listToString(mergeKLists(lists)));只要输出结果和期望一致再提交到平台基本十拿九稳。7.3 自测用例清单我每次提交前都会自测至少三组用例。第一组是常规数据比如[1,4,5]、[1,3,4]、[2,6]用来验证核心逻辑是否正确。第二组是空输入lists为空数组应该返回null或者lists里只有一个空链表返回null。第三组是极端分布比如一条链表很长、其他链表很短或者所有链表都只有单节点这时候要留意节点引用是否被正确串接。还有一个容易忽视的场景链表数组里既有空链表又有正常链表比如[[], [0]]。这类用例能一次性暴露初始化时没有判空的问题。把这些用例跑一遍再提交很少会栽在边界条件上。8. 从这题延伸出去多路归并是通用内功8.1 堆解法直接迁移到K个有序数组、topK问题合并K个升序链表的堆解法一旦理解透可以直接迁移到很多看起来毫不相干的题目上。比如“K个有序数组合并成一个有序数组”思路几乎一模一样堆里放K个数组的当前指针每次弹出最小值再补进同一个数组的下一个元素。再比如“从K个有序数据源中找最小的N个元素”也就是topK问题同样是维护一个小根堆或大根堆不断用新值顶掉堆里的极端值。外部排序里的K路归并也是这个套路内存装不下大数据时把数据切分成多个有序片段然后每次从各片段头部取最小写入磁盘堆就是在每轮快速定位全局最小值的关键结构。理解了“K个有序数据源最小值定位”这个模型很多题本质上都是同一道题换皮。8.2 链表题的几个母题套路这道题也用到了链表题里几个极其通用的套路值得单独记录。第一个是哑节点dummy。几乎所有“需要从头部开始拼接新链表”的题目都适用不止这一题。第二个是“在原有节点上调整next引用不新建节点”。这是链表操作和数组操作的核心差异也是空间复杂度能压到O(1)的根本。第三个是“两个链表/多个链表同时推进”的指针模式它贯穿了二路归并、K路归并、找相交节点、判断回文链表等一大片题目。把这些母题套路想明白再看“合并K个升序链表”会发现它的难点根本不在指针操作上而在“如何组织K路之间的比较顺序”。堆和分治回答的正是这个问题。如果只让我留一条核心心得那就是先把mergeTwo练到能盲写然后用“K个头节点中取最小”这个不变量去理解堆解法。这题吃透之后再看外部排序、K路归并、topK问题都会觉得它们在用同一套内功。最后给个实际建议不管采用哪种解法先在手边备好能构造链表和打印链表的工具函数提交前自测边界能省掉大量冤枉的罚时。我现在看到任何“K个有序数据源合并”的需求第一反应是先问K和总量N的量级关系——能把一道题做到这个思考层面才算真正刷透了。