合并两个有序链表在LeetCode上是第21题在很多人的刷题清单里它被编排为第5题不管排在第几这道题都算得上是链表类算法题的门面担当。你随便打开哪个公司的算法面试题库大概率都能翻到它的影子或者它变种后的合并K个有序链表。题目本身看着简单——两个已经升序排列的单链表合成一个升序链表——但真要现场手写一遍能一次写对的人真不多。它考的不是什么高深数学而是三件事理解链表的结构、操作指针、把边界条件想干净。这篇文章把这套东西从头到尾剥开讲一遍适合刚把链表基础过完、准备开始刷题或者面了好几次总在链表上栽跟头的人。1. 题目本质与方案选型1.1 题意拆解和它真正考的东西题目描述是输入两个升序链表l1和l2返回合并后依然升序的新链表。注意几个隐藏条件两个链表都可能为空可能一个长一个短。节点是直接复用还是在内存里新建绝大多数解法都是直接复用原节点因为题目没有要求不能修改原来的链表而复用节点的做法能把空间复杂度压到O(1)。有些新手上来就new ListNode做深拷贝属于画蛇添足在空间紧张的真实工程里还会被扣分。真正考的东西有四个维度。第一是数据结构理解你得清楚链表的节点并不存储在连续内存里每个节点只存了一个后继指针指向下一个节点的内存地址。第二是指针操作把一个节点摘下来挂到新链上本质就是修改next的指向关系。第三是边界处理两条链表长度不一致、其中一条为空、节点值全部相等这些情况几乎每个新手都会在最后一步漏掉。第四是代码整洁度同样的逻辑写得干净的就那十来行写得乱的分支套分支bug还多。这道题看起来简单但它的价值在于当你把这道题吃透链表类的其他题型——反转链表、删除倒数第N个节点、合并K个有序链表、链表排序——都会好解很多因为它们的核心都是指针移动和边界判断这两件事。1.2 两种主流解法的取舍逻辑目前最主流的解法就是迭代双指针和递归。迭代法用两个指针分别走在两条链表上谁的值小谁先挂到新链上直观、空间复杂度O(1)。递归法把问题切小合并l1和l2等价于取下较小的那个头节点再递归去合并剩下的部分。递归写出来干净得像诗但新人容易被递归调用栈绕晕不知道每一步谁在等谁。我自己在面试中更建议优先讲迭代因为它的每一步都在明面上面试官容易跟上你的思路。如果面试官追问能不能换一种思路你再甩出递归解法让对方觉得你有全局观。但这种全局观不是背出来的是用一遍遍手推练出来的。两种解法的取舍可以简单对比对比维度迭代法递归法空间复杂度O(1)O(mn)代码量稍多但有哨兵节点后思路清晰极少逻辑高度凝练理解门槛每个操作都直观可见需要接受不求甚解的递归思维工程适用性链表很长时也安全链表过长可能栈溢出递归的空间代价是系统栈为什么递归会有O(mn)的空间因为每一层递归调用在返回之前都会在系统调用栈上保留一个栈帧。最坏情况下递归深度等于mn所以空间复杂度是O(mn)。如果面试官让你把空间优化到O(1)你就应该想到迭代法。这道题不是谁更高级而是在什么场景下选什么更合适。2. 迭代法完整拆解2.1 哨兵节点的魔力写迭代法第一个要养成的习惯就是创建哨兵节点dummy node。为什么要这个节点因为合并链表时新链表的头是谁一开始是不知道的。l1的第一个节点和l2的第一个节点谁更小谁才是结果的头。如果不用哨兵节点你得先做一次 if 判断决定头节点然后还要准备两个分支分别处理后续逻辑代码会多出不少分支。哨兵节点是一个虚拟占位节点它的值随意比如-1它不参与最终结果。我们让所有新链上的节点都先挂到sentinel后面最后返回sentinel.next这个next才是真正的头节点。这就像铺铁轨时先打一个桩后面每一节都顺着桩往后铺不用每次纠结起点在哪。提示哨兵节点不同于带头结点的链表。两者都有占位之意但哨兵节点是解题时临时创建的辅助节点不会参与最终返回结果带头结点的链表是存储结构上的设计。你可以把它们类比成临时脚手架的钉子和房屋承重结构里的螺栓。2.2 Java实现与逐步推演以下是标准的迭代实现用Java写public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode sentinel new ListNode(-1); ListNode cur sentinel; 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 sentinel.next; }假设l1是1→3→5l2是2→4→6。第一次循环l1.val1小于l2.val2所以把1挂上去l1指向3。第二次循环3大于2挂2l2指向4。第三次循环3小于4挂3l1指向5。第四次循环5大于4挂4l2指向6。第五次循环5小于6挂5l1已经空了。循环退出后l1为空那么剩下还没遍历完的l2也就是6直接接到尾巴上。最终得到1→2→3→4→5→6。注意这里有一个很多人忽略的细节每次循环末尾是cur cur.next不是cur cur.next.next。因为当前节点已经接上了新节点cur作为新链的尾部指针就要移动到新节点上下一次循环才可以把后续节点接到这个新节点后面。这一步写错结果是错乱的链表没法看。2.3 三个最容易翻车的点第一个翻车点是循环条件。写成while (l1 ! null || l2 ! null)再在循环体里写if (l1 null)这种分支也能实现但代码丑且容易在分支里漏掉cur的移动。更推荐上面这种只要有一个空了就退出剩下的整条接上的写法把循环体的复杂度压到最低。第二个翻车点是忘记拼接尾巴。很多新手把循环写完了直接return sentinel.next结果发现合并出的链表只有两链交错的中间段后面的节点全丢了。凡是在循环里用游标指针遍历链表的操作都有可能制造断链而剩下的链直接拼上恰恰是最关键的收尾。这一行像安全绳平时看不见关键时刻救命。第三个翻车点是在相等值时的取法。用在两条链出现相同值时会优先取l1的节点结果等价且不会出错。但如果你写出严格小于遇到相等值阶段两个链表交织方式会变。普通合并看不出问题一旦题目升级成类似合并后保持稳定排序或者你在工程里实现一个归并逻辑还要求稳定性这个细节就是事故现场。我的习惯是稳定地用形成肌肉记忆。3. 递归法拆解3.1 递归的思考方式递归解法在链表合并中显得格外优雅核心就一句话合并l1和l2的结果等于取下两者中较小的头节点然后让这个头节点的next指向合并剩余部分的结果。这其实是把一个大问题切成同样形式的小问题每次递归问题规模都少一个节点。很多初学者看不懂递归代码是因为总想着递归到底展开了多少层。正确的姿势是完全不展开。你只要论证三件事基准条件成立、递归调用在处理规模更小的问题、递归结果拼回去能满足题意。有点像流水线你不需要操心最终装配线上的每一次拧螺丝只要每个工位做的事是对的整条线出来的产品就是对。这句话我每教一个新人都会重复一遍——递归不是让你去跟踪每一层的细节而是让你信任一个递归函数的约定。在合并链表这道题里约定就是这个函数接收两条有序链表返回它们合并后的有序链表。在这个约定下你只需要处理当前最小的问题就可以了。3.2 递归实现与调用过程public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 null) return l2; if (l2 null) return l1; if (l1.val l2.val) { l1.next mergeTwoLists(l1.next, l2); return l1; } else { l2.next mergeTwoLists(l1, l2.next); return l2; } }还是1→3→5和2→4→6的例子。最外层调用1小于2所以最终结果的头是1接下来要合并l1.next3→5和l22→4→6。第二层3大于2结果头是2接下来合并3→5和4→6。第三层3小于4结果头是3合并5和4→6。第四层5大于4结果头是4合并5和6。第五层5小于6结果头是5合并空和6。第六层l1为空直接返回6。然后逐层往回拼接每层返回的节点就是上一层的next最终链就完整了。注意递归解法不需要哨兵节点因为递归的自然出口就是空链表返回值天然诞生了一个头节点。这种出口即结果的思路是递归与迭代最大的气质差异。迭代法是从前往后一点点搭递归法是先设计好最后一步和向下拆解的关系。3.3 递归的空间代价与面试表达技巧递归的空间复杂度是O(mn)因为递归调用会占用系统栈。在LeetCode上这不是问题但如果面试官追问能不能优化空间你就得明白他的指向是迭代法。另外工程上如果链表长度达到十万、百万级别递归法可能触发栈溢出这时候需要无脑用迭代。注意面试时如果先讲递归建议主动说明空间换代码简洁的取舍再补一句工程上我倾向迭代。这会让人觉得你不只会背模板还考虑到了实际运行的约束。我见过有些候选人写递归时很溜一问空间复杂度就愣住了。这个问题其实很好答递归的每一层调用都在等下一层的返回值在等待期间当前这层的局部变量和返回地址都必须存在栈上所以你返回之前所有层级的栈帧都在内存里空间自然就是O(mn)。4. 复杂度分析、边界案例与验证4.1 时空复杂度为什么不难算但容易说错时间上每个节点最多被访问一次所以是O(mn)m和n分别是两条链表的长度。空间上迭代法只用了一个sentinel和cur两个指针是O(1)。递归法最坏情况下会递归mn层每层调用都在栈上留一个帧是O(mn)。说错的人往往把迭代法也写成O(mn)理由是我复制了一条新链表。但标准解法是复用原节点没有创建新节点只是改了指针指向。这一点在面试中我会随口说出来作为我没有额外分配内存的佐证。理解这件事的关键在于没有new出来的节点内存就不变。4.2 六大边界案例测试表我平时写完代码会立即用这组用例过一遍几十秒就能把低级bug扫干净。用例l1l2期望输出双空空空空单空空1→21→2单空反向1→2空1→2不等长1→5→72→31→2→3→5→7全部相等1→1→11→11→1→1→1→1极端大小0→199→1000→1→99→100特别提示双空用例迭代法中循环没进cur.next直接被置为l1而l1是null返回sentinel.next即null结果正确。递归法中第一个if就返回null。单空用例则验证了剩下的整条接上是否被正确实现。全部相等用例最能测试你在相等情况下用的比较操作符如果你用严格小于合并顺序会在两个链表间交替取值虽然普通场景看不出但一旦有额外排序需求就说不清了。4.3 用纸面调试替代打印日志链表题的调试有个很有效的土办法不要一上来就断点跟先拿一张纸把每条链表按格子画出来每个节点画成一个方块上面写值下面画箭头指向下一个节点。然后对照代码用笔把指针移动的每一步画出来。你能在一张纸上把过程画顺代码通常就是对的画不顺断点大概率也白打。这个方法对付链表相关的所有题目都极其好用。它比在IDE里打断点更直观的原因在于链表问题本质是引用关系的变化你在纸上看到的箭头就是内存里的指针画得清楚就能看出指针到底指到了哪里。尤其在判断是否成环时纸面画几轮比肉眼盯着内存地址好用多了。5. 变种与应用场景5.1 合并K个有序链表从两个到N个面试里百分之八九十会从两个升级到K个。经典的实现思路有三种顺序合并、两两合并、优先队列。顺序合并是拿结果链表逐个和下一个链表merge时间复杂度会随着K的增大而线性膨胀。两两合并是每一轮两两配对合并把链表条数折半一轮下来链表数量减半整体复杂度变成O(N log K)。优先队列则是把K个链表头塞进一个小顶堆每次弹出最小值节点挂到结果上再把该节点的next入堆复杂度同样是O(N log K)。优先队列实现是工程里最常用的也是面试最能加分的写法。它本质上是在同时维护K个候选头他们就像一场选秀里K个待定选手评委每次只投票选当前最小的那个晋级晋级后顶替他位置的又是下一个选手。当K不大时两两合并完全够用K大的时候优先队列明显更稳。这道题的延伸让我看到合并两个有序链表真的是地基中的地基合并K个有序链表看起来是一个新题但核心抓手还是谁小谁上只是从二选一变成了K选一而K选一的效率问题就用堆来解决。5.2 链表类归并思想在实际工程的身影合并有序链表在真实的系统里也不少见。数据库的归并排序外排阶段就要把多个有序段合并成一个日志系统中多路归并用来把多个有序分片合并成最终有序文件git的分支合并从把两条有序提交序列交织成一条新序的角度来看和这道题有某种神似当然git背后是更加复杂的merge算法但维护多个游标每次取最小推进的思想是相通的。再举个例子PDF工具里的批量合并、表单数据的跨表合并表面上和链表毫无关系但如何把多个有序输入流合成一个有序输出流的骨架没变。刷题的时候多往自己平时写的东西上联想会让你觉得算法不只是在面试时闪光而是一种能迁移到大量普通需求里的通用思维。5.3 一道极易弄混的兄弟题链表拆分与合并判空和合并相反的操作是把一个链表拆成两个链典型题目是把链表按奇偶位置拆开。这类题强调的恰恰是合并时直接拼尾巴拆分时要记得切断尾巴两个操作互为镜像放在一起练特别容易打通指针操作的任督二脉。我自己在带新人时经常让他在同一天把这两题各写三遍写完基本不会再犯合并时丢了尾巴、拆分时忘了断尾的错误。道理很简单合并的收尾是接拆分的收尾是断两种相反操作放在一起对比记忆会深得多。如果前一道题的代码在后一道题里改错了一个符号这种融合错误往往是最值得记的。6. 常见问题与排查技巧实录6.1 链表成环是怎么发生的合并题最常见也最隐蔽的错误是结果链表成环。比如你在循环里写cur.next l1后又写cur cur.next然后下一轮如果还取到l1的同一个节点就可能把它的next改成自己或者改成之前已经挂过的节点造成环。判断链表是否成环有个土法用一个指针从头出发跑100步如果还没遇到null多半就环了。也可以用快慢指针判环但面试写代码阶段我更推荐纸面推演因为快慢指针本身就是另一道题引入它会干扰你排查重点。避免成环的纪律总结起来就三条每一轮循环最多只让cur.next指向一个节点被选中的那个链的游标必须立刻向前移cur本身也跟着向前移。三条守住环就无从发生。我早期写链表题时也掉过一次成环的坑排查了很久最后发现就是选中节点后没往前移游标从那以后这三条纪律就被我刻在脑子里了。6.2 合并后原链表变化问题复用原节点意味着原链表被拆了合并完成后l1和l2的头节点指针虽然还指向原内存但整条链的next关系已经重构。这在算法题目里没问题但如果你的代码后面还要用原来的链表做别的统计就会踩到坑。应该先想清楚题目允不允许你破坏原链表如果允许复用节点节省空间如果不允许提前深拷贝。这个判断其实也是很多真实业务中对象复用还是克隆的老话题。拿很多开发都接触过的场景举例你有两个有序的数据源要合并成一个新集合如果后续还要各自独立使用原数据就不能被挪走。所以动手之前先看题目要求这是比代码本身更重要的一步。6.3 写代码前的三分钟自查清单我一般会在动手前快速过一遍第一两个链表都可能为空我的代码同时对这两种情况成立吗第二循环终止后剩下没走完的那条链表整条接到尾部的语句写了吗第三返回的是哨兵节点的下一个节点不是哨兵自身。这三条任何一条没想清楚就动笔多半会返工。把这三条自查养成肌肉记忆能省下大量的调试时间。实际上在真实面试场景里面试官看的不是你写得多快而是你在动手前有没有把方案想清楚以及写完之后有没有主动自测。能主动说我先检查三个边界条件的人往往比一言不发就开始敲键盘的人留下好印象。从我个人的实际经验来说合并两个有序链表这道题最大的价值不是你会了它而是它把链表操作的所有基本功浓缩在一个半小时内就能反复练透的小题目里。我每次带人或者面候选人只要对方能把这道题一口气写对同时讲清楚为什么需要哨兵节点、边界条件在哪里我基本就能断定他在链表题上不会掉太多坑。你如果想去检验自己是不是真的掌握了就用我前面给的六大边界用例和纸面调试方法合起来练上十几遍练完之后再去做合并K个有序链表你会发现自己的视角已经完全不一样了——因为你会清楚地看到难题不过就是基础题加了一层壳而已。