LeetCode第21题“合并两个有序链表”应该是我见过最经典的一道链表入门题。不管是校招笔试、考研数据结构还是平时刷题练手它出现的频率都高得惊人。题面看起来也简单给你两个已经按升序排好的单链表把它们合并成一个新的升序链表返回合并后的头节点。但真正动手写的时候很多人会在头节点处理、指针移动顺序、循环结束后的收尾这些地方卡住。这篇文章就从思路到细节完整拆一遍这道题同时把链表操作里那些容易被忽略的底层功夫也一并讲清楚。适合刚开始接触链表的同学也适合想把自己的解法讲得更严谨的人面试前拿这篇文章快速过一遍尤其实用。1. 题目本质与核心思路拆解1.1 先读懂题目再动手题面到底在说什么这道题输入是两个单链表的头节点一般定义成l1和l2。每个链表节点包含一个整数val和一个指向下一个节点的指针next。链表本身是按非递减顺序排列的也就是说1-2-4这种形式节点值从头到尾不下降。输出要求是返回合并后的链表的头节点合并后的链表也要升序。很多初学者上来就闷头写写到一半才发现自己都没搞清楚“能不能新建节点”“要不要保留原链表结构”这些问题。在 LeetCode 这个题的标准设定下你不需要新建额外节点直接复用原来的节点、修改它们的next指针就行。这一点很关键它决定了这道题的空间复杂度能做到 O(1)也是链表合并和数组合并最大的区别。数组合并两个有序数组通常要开一个额外数组来放结果链表合并只需要“改指针”不需要搬动节点本身。这里还需要搞清楚单链表的节点定义不同语言写法略有差异。Python 里是这个样子class ListNode: def __init__(self, val0, nextNone): self.val val self.next nextC 里则是struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };理解这个结构是后面所有操作的基础。链表的每个节点在内存里不一定是连续存放的正是靠next指针串成一条链。这也意味着合并链表最核心的动作不是“移动数据”而是“改变指针指向”。1.2 核心策略谁小谁接上合并两个有序链表的迭代思路一句话就能说清两个指针分别指向两条链的当前节点每次比较这两个节点的值把值较小的节点摘下来接到结果链表的尾部然后让那个链表的指针往后挪一位另一个指针不动继续比较。为什么这样一定能得到正确的升序链表因为两个输入链表各自都是升序的所以两个链表当前节点中较小的那个就是所有剩余节点中最小的。拿走它之后剩下两条链依然各自有序问题规模缩小了但性质不变。这就是典型的“贪心”策略每一步都做当前看起来最优的选择最终全局最优。生活里也好理解两摞按时间排好的档案你要把它们合成一摞只需要每次看两摞最上面那张谁的日期更早把它抽出来放在新的一摞最上面重复到全部抽完。每次比较只需要一次被选中的节点就永久进入了结果链表不会再被访问。所以整道题最多比较m n - 1次时间复杂度是 O(mn)其中m和n分别是两个链表的长度。因为全程只用了几个指针变量没有申请额外节点空间复杂度是 O(1)。1.3 哑节点为什么要一个占位符新手写这道题最容易卡住的地方就是“返回哪个节点”。如果用最朴素的写法第一轮比较前结果链表的头节点还是未知的你必须先单独判断一次if l1.val l2.val: head l1 l1 l1.next else: head l2 l2 l2.next然后才进入循环。这种写法不是不行但它把“第一轮”变成了特殊情况代码里凭空多出一堆分支逻辑一旦复杂就容易出错。而且如果在循环里维护一个tail指针指向结果链表尾部那么head和tail是分开初始化的看代码时脑子要多转一下。解决办法就是引入哑节点也叫占位节点、哨兵节点。它本身不存有效数据只是为了让“当前结果链表的尾部”这个角色在第一步就有着落dummy ListNode(0) cur dummy之后每轮比较只需要把选中的节点接到cur.next然后cur cur.next。从头到尾所有轮次的逻辑完全一致不用对第一轮做任何特殊处理。循环结束后dummy.next就是合并后链表的真实头节点直接返回它就行。哑节点是链表题里极其常用的技巧不只是这道题。删除链表倒数第 N 个节点、在链表头部插入节点、反转链表的一部分都经常用到它。它的本质是“用一个不参与业务逻辑的额外节点抹平边界情况的特殊处理”让代码更规整也更不容易漏掉边界分支。2. 迭代解法实现与细节深挖2.1 代码全貌先跑通再讲道理直接给出可用的迭代版本Python 写法是def merge_two_lists(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) cur dummy while l1 and l2: if l1.val l2.val: cur.next l1 l1 l1.next else: cur.next l2 l2 l2.next cur cur.next cur.next l1 if l1 else l2 return dummy.next这几行代码说它是链表题里的“标准答案”也不为过。思路清晰边界干净几乎没有多余成分。我第一次认真琢磨这段代码的时候惊讶于它竟然能把合并两个有序链表写得这么利落。但越是简洁的代码越需要拆开看每一行在干什么否则面试时你可能连cur cur.next忘了写都不知道问题出在哪里。C 版本也顺带贴一下逻辑完全一样ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* dummy new ListNode(0); ListNode* cur dummy; while (l1 l2) { if (l1-val l2-val) { cur-next l1; l1 l1-next; } else { cur-next l2; l2 l2-next; } cur cur-next; } cur-next l1 ? l1 : l2; return dummy-next; }注意这里如果new出来的dummy是手动分配的内存实际工程里记得要释放否则会有小内存泄漏。在线评测一般不管这个但写工程代码时最好是栈上创建或者用智能指针。2.2 三个变量各司其职循环不变量是关键这段代码里有几个变量它们的职责要分清楚dummy占位节点最终不参与结果链表的业务数据它的next指向结果链表的第一个真实节点。cur结果链表当前的尾节点始终保持指向“已经串好的最后一个节点”。l1、l2两个原链表中还没被合并的剩余部分各自的头指针。理解这段代码最好的方式是把它当成一个“循环不变量”来维护。所谓循环不变量就是在每次循环执行前都必须成立的性质。这里的不变量是结果链表从dummy.next到cur已经是升序的且l1、l2各自仍然保持升序它们的所有节点值都不小于已合并部分的最大值。每轮循环做的事情就是从l1和l2的当前头节点里选出值较小的那个接到cur.next上然后更新cur和对应链表的指针让上述不变量继续保持。循环结束时有一条链已经为空另一条链剩下的所有节点都大于等于已合并部分的末尾值所以直接拼上去就行。调试的时候你甚至可以在循环体里临时加个断言检查结果链表的单调性这样能早发现指针串联错误。2.3 循环退出与收尾为什么可以直接拼接循环条件是while l1 and l2也就是说只要有一条链遍历完了循环就结束。这时候出现两种情况l1为空l2还有剩余节点l2为空l1还有剩余节点两条链同时为空等价于cur.next l2而l2是空节点结果也正确。关键点是剩余的那条链本身是有序的而且剩余部分的所有节点值一定不小于cur当前指向的节点的值。为什么因为每一次迭代我们都是从两个链表的当前头节点中选出较小的那个选完之后另一个链表的头节点即剩余链表的第一个节点一定大于等于刚选走的节点。这个性质在循环过程中始终成立。所以循环结束时直接把剩下那条链接到cur.next不需要再比较也不破坏整体有序性。这里有个新手容易绕不过来的问题万一剩余链表里有比已经合并部分末尾更小的节点怎么办答案是不会。因为如果剩余链表的头节点比已合并部分末尾小那么它在某轮循环中就应该被提前选走而不可能留到现在。这个结论听着简单但自己能严谨地证明一遍比背十遍代码都有用。2.4 复杂度与边界场景一次想全调试不慌时间复杂度 O(mn) 的道理前文说过每个节点最多被比较一次、被接入一次。空间复杂度 O(1)没有额外申请节点。这个复杂度已经是最优了因为你至少要遍历一遍两个链表的全部节点才能确定顺序。边界场景提前过一遍写代码时心里就有底l1为空l2不为空循环一次都不执行cur.next l2直接返回整个l2。l1不为空l2为空同样直接返回l1。两个都为空返回None这也是合法结果。两个链表长度相差很大比如一个长度 3一个长度 10000那么循环在短链表耗尽后退出的更早长链表剩余部分整段接上去非常高效。节点值有相等的情况用判断时相等时优先取l1的节点这会让合并后的链表保持稳定即相等节点的相对顺序不会被打乱。这些边界情况建议自己在草稿纸上画几个用例跑一遍比如[1,3,5]和[2,4,6]画着画着就会对链表指针的移动产生肌肉记忆。3. 递归解法与两种思路的权衡3.1 递归代码每一层只解决“当前头节点是谁”有些题用递归写起来特别顺因为问题的结构天然就是递归的。合并两个有序链表就可以这样理解要合并l1和l2只需要确定合并后链表的第一个节点是谁——它肯定是l1.val和l2.val中较小的那个确定好第一个节点之后剩下的就是“把较小的那个链表的 next 指向 merge(较小链表.next, 另一条链表)”这是一个规模更小的同样问题。写成代码就是def merge_two_lists(l1: ListNode, l2: ListNode) - ListNode: if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next merge_two_lists(l1.next, l2) return l1 else: l2.next merge_two_lists(l1, l2.next) return l2递归代码的出口就是空链表判断如果l1空就直接返回l2如果l2空就直接返回l1。两个都空的情况已经被第一个判断覆盖了因为not l1为真时直接返回l2此时的l2就是None。3.2 递归执行过程拆解用一个小例子走到底代码短不代表看得懂。我拿l1 [1,3,5]、l2 [2,4,6]来手动展开一下递归调用。先调用merge(1, 2)因为1 2所以这一层要返回的节点是1但它的next要先由merge(3, 2)的结果决定。接着merge(3, 2)里2 3返回2它的next由merge(3, 4)决定。merge(3, 4)返回3next由merge(5, 4)决定……这样一层一层“递”下去直到某一侧链表先变成空就开始逐层“归”回来。真正的回溯顺序是最底层返回某个剩余链表后上一层把返回结果接到自己的next上然后带着自己这个节点继续往上返回。最终整条链就变成了1-2-3-4-5-6。这个过程用文字描述有点绕但在纸上画几层调用关系就非常直观。建议新手一定要把调用树画一遍否则面试时写递归很容易写反。3.3 迭代 vs 递归到底选哪个两种解法都能 AC但实际使用时要权衡。我整理了一张对比表对比维度迭代法递归法时间复杂度O(mn)O(mn)空间复杂度O(1)O(mn)递归调用栈深度代码可读性稍长但逻辑直白非常简洁模式化强超大链表风险无可能栈溢出工程环境偏好优先选择理论漂亮但慎用超长链表递归版虽然看起来只有四行核心逻辑但每递归一层就要占用一份函数调用栈空间。递归深度最大会达到mn而且两个链表长度都很大时这个深度在 Python、C 里都有可能触发栈溢出。所以工程代码里我一般推荐迭代版空间确定是 O(1)不会出现调用栈爆炸。面试时可以先给递归版展示思路再补一句“如果链表很长我会改成迭代版”显得你对两种方案的风险都心里有数。3.4 递归的常见误解与易错点我见过不少同学栽在递归的几个细节上。第一个误解是“递归会新建节点”。不会的递归返回的都是原链表里的节点只是修改了next指向本质上还是在改原链表结构。第二个误解是“递归比迭代更省空间”实际上刚才说了递归额外消耗调用栈空间空间复杂度是 O(mn)比迭代高。第三个易错点是搞混赋值顺序。递归体里必须先确定本层返回的节点再修改它的next。如果你反过来先改了next再返回就可能把本层节点和递归结果的关系搞乱。第四个易错点是只写一个空链表出口比如只判断if not l1: return l2忘了l2为空的情况。递归出口一定要两个都判断缺一个就会在某些输入下报空指针异常或者返回错误结果。4. 测试用例设计与常见问题排查4.1 一套可以直接抄的测试用例写算法题代码跑通只是第一步能不能想到全面的测试用例才是真正拉开差距的地方。我习惯在本地为这道题准备这样一组用例用例编号输入 l1输入 l2期望输出覆盖点1[][][]两个空链2[][0][0]单侧空链3[1,2,4][1,3,4][1,1,2,3,4,4]标准用例 相等值4[1,2,3][4,5,6][1,2,3,4,5,6]左侧链先耗尽5[4,5,6][1,2,3][1,2,3,4,5,6]右侧链先耗尽6[-3,-1][0,2][-3,-1,0,2]负数与正数混合7[1][1][1,1]所有节点相等这些用例基本覆盖了题目可能出现的所有形态。跑测试的时候除了看最终的结果链表值顺序对不对还要注意别把原链表改得乱七八糟。有些在线平台会把l1、l2的原始结构用于后续测试如果你改坏了原链表后面用例可能莫名其妙失败。4.2 代码调试中最容易踩的几个坑指针类 bug 是最难肉眼发现的一类问题因为代码看着都对但运行结果就是不对。我帮你把高频坑集中列一下。第一个坑是忘记移动cur指针。很多人写完cur.next l1之后忘了写cur cur.next导致下一轮又把新节点接在同一个位置上结果链表永远只有最后一个节点前面的节点全丢了。这个问题在纸上推演一遍就能发现关键是在循环体结束前cur必须指向最新接上的节点。第二个坑是返回了dummy而不是dummy.next。dummy是一个值无关紧要的占位节点如果直接返回它结果链表就多了一个多余的头节点判题必然报错。写代码时最后一行的return dummy.next要形成肌肉记忆。第三个坑是提前修改了l1或l2的头指针导致后续判断出错。比如你先把较小节点接到cur.next上然后又用l1 l1.next如果这段代码写错顺序就可能跳过节点或者把同一个节点接入两次。正确的做法是先保留要移动的指针比如tmp l1.next然后再修改l1。当然标准写法里直接l1 l1.next放在cur.next l1之后是安全的因为此时l1还没被覆盖。第四个坑是在 C/C 场景下如果手动delete了节点可能会导致返回的链表指针悬空。这个题的标准解法不会删除节点但如果你自己加了一些“清理”逻辑要注意不是所有被遍历过的节点都能释放被合并进结果链表的节点必须保留。4.3 面试官围绕这道题常追问的几个点这道题虽然简单但面试官很擅长在它基础上加问。我总结几个出现频率极高的问题。第一个是稳定性。如果两个链表里有相同值的节点合并后它们的相对顺序会改变吗用取l1的节点那么l1中相同值的节点会排在l2中相同值的节点之前这种归并是稳定的。如果改用相等时就会取l2的节点稳定性就反了。弄清楚这个细节能体现你对归并过程有深入理解。第二个问题是能否做到不修改原链表。题目默认允许复用原节点但有些场景要求合并结果是一份全新链表原链表保持不变。这种情况下就不能直接改next需要每一步新建节点并复制val时间复杂度仍然 O(mn)空间复杂度变成 O(mn)。面试时可以主动提一句显得你考虑过只读场景。第三个问题是如果输入的是降序链表怎么办。把比较符号反过来就行核心逻辑完全一致所以这道题并不只适用于升序。第四个问题是如果链表里有环呢。这个题默认输入是两个无环的单链表。如果面临有环的输入必须先做环检测否则合并过程会死循环。把这些追问提前想明白面这道题的时候就会从容很多。5. 延伸扩展从合并两个到合并 K 个5.1 合并 K 个有序链表的三种常见思路掌握了两个链表的合并就掌握了更复杂问题的地基。LeetCode 第 23 题“合并 K 个升序链表”正是这道题的直接升级版。给定 K 个有序链表把它们合并成一个有序链表常见思路有三种。第一种是逐个合并。把第一个和第二个合并结果再和第三个合并依次类推。假设链表总节点数是 N这种做法的总复杂度是 O(KN)因为越到后面当前结果链表越长反复被扫描的开销越大。优点是代码最简单但效率在 K 较大时不理想。第二种是分治合并也叫两两合并。把 K 个链表两两配对每一对用我们这道题的mergeTwoLists合并得到约 K/2 个新链表再两两合并重复直到只剩一个链表。这个过程很像归并排序每一轮的总操作量是 O(N)一共进行 logK 轮总复杂度 O(NlogK)。这个思路在面试里是加分项因为它体现了对“归并”思想的理解。第三种是优先队列最小堆。先把 K 个链表的头节点全部放入一个小根堆每次弹出最小的节点接入结果链表尾部然后把该节点的next节点再入堆。循环直到堆为空。时间复杂度同样是 O(NlogK)空间复杂度 O(K)。在 K 比链表长度还大的场景里这个方案很实用。5.2 归并思想在链表题里的渗透对链表的归并思想一旦熟练很多题都能迎刃而解。最典型的就是链表排序LeetCode 第 148 题。对一个单链表排序最常见的高效做法就是“自顶向下归并排序”先用快慢指针找到链表中点把链表拆成左右两半递归排序然后用我们这道题的合并函数把两个有序链表合起来。整个过程几乎是本题的复用。还有一些题看着不一样但底层也是归并的影子。比如“合并两个有序数组”用的是类似的双指针思路只是数组不能像链表那样只改指针需要额外空间。再比如“两个有序链表求交集”也可以借鉴双指针同时推进的框架。把这道题练熟相当于给未来的链表题打下了一个很扎实的地基。5.3 真实工程里的多路归并影子有同学会问这种纯粹的算法题实际工作里真的用得上吗当然用得上。多路归并是很多底层系统的核心逻辑。外部排序就是典型场景当要排序的数据量远超内存时系统会先把大文件切分成多个小片段每个片段在内存里排序后写成有序片段文件然后对这些有序片段做多路归并最终得到一个整体有序的大文件。这个多路归并过程和“合并 K 个有序链表”的概念几乎一模一样只是操作对象从链表的节点变成了文件里的数据块。数据库里也有类似的东西。比如 sort merge join 在处理两个有序表时就是双指针同时扫两条有序序列按连接条件逐步推进。再比如 Git 在合并多个分支时本质上也在处理多个有序或可排序的提交序列之间的关系。所以哪怕你现在只是刷题这些“无聊的链表题”其实都对应着一套真实存在的工程范式。我个人带过不少同学刷这道题最大的感受是不要觉得自己看懂了就跳过。链表题的熟练度是画图画出来的不是肉眼读代码读出来的。花 20 分钟在纸上把迭代版和递归版的指针变化各自推演一遍比刷十道同类题更有用。如果在线判题时出现“改来改去还是错”的玄学 bug别硬想先回到草稿纸上跑一个小用例把每次循环后的链表状态写出来问题基本一眼就能看见。这个习惯也是我至今写链表代码不慌的原因。