合并两个有序链表这道题算得上是链表入门里最经典的一道了。很多人在 LeetCode 上刷题第一道链表题往往就是它。我当年刚开始学数据结构的时候也被这道题卡过一阵子——不是看不懂思路而是写代码的时候总是控制不好指针要么是空指针异常要么是链表断掉了。后来练多了才发现这道题其实是在考两件事第一你懂不懂链表在内存里到底是怎么串起来的第二你会不会把“合并两个有序数组”的思路灵活迁移到链表结构上来。这两点搞明白了这道题基本就没什么难度了。这篇博文我就从题目本身出发把这道题涉及的思路、两种主流写法迭代和递归、边界条件的处理、常见的坑以及它在实际场景中的价值全部拆开揉碎讲清楚。无论你是刚开始刷题的新手还是准备面试的开发者这篇文章应该都能给你一些参考。1. 题目拆解与核心思路1.1 题目到底在考什么先简单回顾一下题目本身给你两个有序链表的头节点l1和l2要求把它们合并成一个新的有序链表并返回。这里的“有序”一般默认是升序而且题目要求合并后的链表依然是升序的。链表节点的定义通常长这样class ListNode: def __init__(self, val0, nextNone): self.val val self.next next很多人在看到这道题的时候第一反应是“直接把两个链表拼接起来然后整体排序”。这个思路其实并不算错但它忽略了一个关键前提两个链表已经是分别有序的。如果你把拼接后的链表整体排序复杂度就变成了 O(n log n)。而如果利用“两个链表各自有序”这个条件用双指针一次遍历就能合并复杂度可以降到 O(n)。这道题表面上是在考“怎么合并”实际上是在考察你有没有理解并利用好“有序”这两个字。另外一个考点是“原地 vs 新建”。题目通常要求返回一个新的链表但有些变体题目会要求不改变原链表的结构或者要求尽量复用原节点。默认情况下大多数解法会选择复用原有节点——也就是说我们只是重新调整了节点的next指针并没有创建新的节点对象。这样做的好处是空间复杂度能降到 O(1)不算递归栈。1.2 从生活场景里理解合并过程把这道题翻译成生活场景其实特别简单。想象有两队人每队人都是按身高从小到大排好的。现在要把这两队人合并成一队仍然按身高从小到大排列。你应该怎么操作很简单每次比较两队最前面那个人的身高谁矮谁就站出来站到新队伍里。如果一边的队伍空了就把另一边剩下的人整个接到新队伍后面。这个比喻几乎就是迭代法的完整思路。关键点在于每次只需要看两个队列当前的“队首”谁是更小的那个就把它摘下来放到结果队列的尾部。这个过程中两队内部的有序性保证了“当前队首就是本队剩余人员里最小的”所以只要比较两个队首就能确定全局最小的那个。这里有一个容易犯迷糊的地方如果你用一个“结果队列”来接收所有节点那这个结果队列本身也需要一个指针来维护它的尾部。因为你每次都是把新节点“接到尾部”的所以需要记录当前结果队列的最后一个节点否则你就不知道新节点应该往哪里接。1.3 为什么说这是一道“必会题”说实话这道题在算法面试里出现的频率算不上最高但它依然被很多人列进“必刷 100 题”清单。原因是它有极强的代表性。链表的操作无外乎就是遍历、插入、删除、反转、合并这几类而这道题几乎把链表的遍历和插入都包含了。更重要的是合并两个有序链表的思路是很多复杂算法的基石。最典型的例子是归并排序。归并排序的“合并”步骤就是把两个有序序列合并成一个有序序列。如果序列是用链表存储的那这个“合并”步骤用的就是这道题的逻辑。再比如合并 K 个有序链表做法也是两两合并或者用优先队列。可以说如果你的代码基础里没有这道题的肌肉记忆后面碰到归并排序、多路归并、外排序等概念时总会觉得缺一块。2. 解法一迭代法最稳妥的写法2.1 哑节点的价值省去一堆空指针判断迭代法的核心思路就是刚才说到的“两队人排身高”。但在实现上有一个很经典的小技巧——引入一个哑节点dummy node。哑节点是什么就是创建一个额外的节点它的值随便什么都行比如 0它的作用是作为结果链表的“虚拟头节点”。为什么要这么干因为在合并的过程中结果链表的头节点是不断变化的。如果用head变量直接表示结果链表的头节点那么当头节点第一次被赋值时和后续被赋值时代码的逻辑是有区别的——头节点之前没有节点而后续的节点都是在尾部追加。为了避免这种“头节点特殊处理”我们先把结果链表挂在一个哑节点后面最后返回dummy.next就行了。这样无论结果链表是空还是非空代码逻辑都统一了永远是在tail.next后面接新节点。用一个生活类比就是你先把结果队伍排在一个“虚拟的领队”后面不管队伍最终有没有人你都不用为“第一个人怎么站”而单独写一套规则。很多初学者恰恰是在这个细节上踩坑——不引入哑节点然后在循环里总要判断结果链表是不是空的代码写得又长又容易出错。等你写多了就会发现哑节点几乎成了链表题里的“标准配置”只要涉及到“合并空表”或“头节点不确定”的场景优先想一下能不能用哑节点简化逻辑。2.2 迭代法代码逐行拆解下面给出 Python 的迭代法实现我会尽量把每一步都注释清楚def mergeTwoLists(l1: ListNode, l2: ListNode) - ListNode: # 哑节点简化头节点的处理 dummy ListNode(0) # tail 指向结果链表的尾部 tail dummy # 当两个链表都不为空时才需要比较 while l1 and l2: if l1.val l2.val: tail.next l1 l1 l1.next else: tail.next l2 l2 l2.next # 每接上一个节点tail 就要向后移动一位 tail tail.next # 循环结束时至少有一个链表已经空了 # 直接把另一个链表的剩余部分接到尾部 tail.next l1 if l1 is not None else l2 # 返回哑节点的下一个节点才是真正的头节点 return dummy.next这段代码看着很短但里面有几个细节值得好好琢磨。第一个细节是while l1 and l2而不是while l1 or l2。这个循环条件的含义是“两个链表都还有节点时才进行比较”。如果写成or那循环体内就会碰到l1或l2为None的情况直接访问.val就会抛空指针异常。我们选择and就是为了让循环结束后统一处理“某个链表已经空了”的情况。第二个细节是tail tail.next。每接上一个节点tail都要往后移动一步。你可以把tail理解为结果链表的“光标”它永远指向结果链表的最后一个节点。如果不移动它下一次接节点时就会把新节点接到老位置导致链表断裂。第三个细节是最后一行return dummy.next。很多人刚开始写的时候会写成return dummy然后就会发现自己返回的链表最前面多了一个值。这一点必须警惕dummy只是我们构造出来的临时节点它不是结果链表的一部分真正的头节点是dummy.next。2.3 该选择恢复原链表还是新建链表这道题如果题目没有额外说明默认是允许修改原链表的。也就是说我们直接把l1和l2里的节点重新串起来不创建新节点。这样空间复杂度是 O(1)。但实际工作中我们可能不希望修改输入的链表因为调用方之后可能还要用到原链表。我印象里有些面试官会追问“如果不允许修改原链表你会怎么做”这时候思路其实是一样的只不过每次需要new ListNode(val)显式创建一个新节点再接到tail后面。代价是时间复杂度不变空间复杂度变成 O(n)。这两种方案各有适用场景面试的时候如果能主动说出来会显得你对问题考虑得比较周全。迭代法整体来说是最稳妥的写法它不容易绕晕也不会有递归带来的栈溢出问题。我推荐刚开始学习的人先把迭代法写到闭着眼睛都能默写的程度。3. 解法二递归法更简洁也需要更谨慎3.1 把问题拆成子问题来看递归法在思路上比迭代法更简洁但也更难理解。它的核心逻辑是比较l1和l2当前节点值的大小哪个更小就把它挑出来然后让“它的下一个节点”去和“另一个链表的当前节点”继续做合并。换句话说递归法把问题一层一层缩小。mergeTwoLists(l1, l2)的结果取决于l1.val和l2.val的大小。如果l1.val更小那么结果链表的头节点就是l1后面接的是mergeTwoLists(l1.next, l2)的结果反之亦然。这里有一个非常关键的递归出口终止条件当l1为空时直接返回l2当l2为空时直接返回l1。为什么这个出口是合理的因为如果一个大链表已经空了那么合并的结果就是另一个链表本身——另一个链表已经是有序的不需要任何额外操作。3.2 递归代码与调用过程分析递归法的 Python 实现如下def mergeTwoLists(l1: ListNode, l2: ListNode) - ListNode: # 递归出口 if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next mergeTwoLists(l1.next, l2) return l1 else: l2.next mergeTwoLists(l1, l2.next) return l2为了让你真正搞懂这段代码我拿一个小例子手动走一遍。假设l1: 1 - 3 - 5 l2: 2 - 4调用merge(l1, l2)l1.val1l2.val21 2所以执行l1.next merge(1-3-5 中的 3-5, 2-4)然后返回1这个节点。当前先不急着返回我们需要先算出内层递归的结果。内层调用merge(3-5, 2-4)比较 3 和 22 更小所以执行l2.next merge(3-5, 4)返回2这个节点。继续内层调用merge(3-5, 4)比较 3 和 43 更小执行l1.next merge(5, 4)返回3。继续调用merge(5, 4)比较 5 和 44 更小执行l2.next merge(5, None)返回4。merge(5, None)l2为空直接返回l1也就是5。然后一路往回返回4 - 53 - 4 - 52 - 3 - 4 - 5最后1 - 2 - 3 - 4 - 5。这个过程中每次递归返回的都是当前已经合并好的子链表的头节点上层递归只需要把当前节点接到返回的子链表头节点前面就完成了局部合并。3.3 递归的代价栈深度与面试官想听什么递归写法虽然好看但有两个代价是必须清楚的。第一个是空间复杂度不再是 O(1)而是 O(n)——这里 n 是递归调用的最大深度也就是两个链表中较长那个的长度。极端情况下如果你要合并两个长度都是 10000 的链表递归调用就会深度达到 10000 层Python 默认的递归深度限制是 1000 左右所以很容易触发RecursionError。在实际项目里如果数据量不确定我不会贸然用递归写法除非你能确认链表长度不会超过递归限制。第二个代价是递归确实不好调试。迭代法的状态变化可以用tail指针一步步追踪递归法的调用栈比较抽象初学阶段容易卡在“返回值到底是谁”上面。面试的时候如果面试官让你写这道题可以先用迭代法写完然后再主动说出递归写法顺便分析两者的时间空间复杂度差异。这往往能证明你不是只会背代码而是真的理解了两种编程范式的取舍。4. 边界条件与常见错误清单4.1 四个必须验证的边界场景我见过太多人在 LeetCode 上提交失败原因大多不是主流程写错而是边界条件没处理好。合并两个有序链表这道题至少要把以下四种情况都验证一遍第一种两个链表都为空。此时直接返回None。迭代法里循环不执行dummy.next本身就是None递归法里直接命中两个if not l1或if not l2的出口返回None。第二种一个链表为空另一个非空。此时应该直接返回非空的那个链表。很多人会在这个场景里犯错因为他们可能在循环里写了while l1 or l2然后循环体内试图访问l1.val或l2.val一旦有一个链表为空程序就崩了。正确的做法是用while l1 and l2让“某个链表为空”的情况统一在循环结束后的收尾代码里处理。第三种两个链表长度不一致。比如l1有 5 个节点l2只有 2 个节点。短链表先被遍历完此时另一个链表还剩 3 个节点直接把这一整段剩余部分接到结果链表的尾部即可。为什么可以直接拼接而不需要继续比较因为剩余部分本身就是有序的而且前面所有节点都已经比剩余部分的头节点小或等于所以把整个剩余段接到尾部不会破坏整体的有序性。第四种两个链表有相等的节点值。比如l1的第一个节点值是 2l2的第一个节点值也是 2。我们应该如何处理关键在于合并后两个节点都保留而不是去重。题目要的是“合并两个有序链表”不是“去重合并”所以相等的节点值要同时出现在结果链表里。在代码里if l1.val l2.val这个判断用就保证了相等时优先取l1的节点然后继续处理另一个等值节点会在后续循环中接上不会丢失。4.2 新手最容易踩的五个坑第一个坑返回了哑节点本身。正如前面所说dummy是一个附加的虚拟节点如果你把它作为结果返回链表的每个节点前面就会多出一个多余的节点。这个错误在 LeetCode 上是最常见的它测试用例能跑通很多简单例子但你的答案会多一个额外的0节点导致判题不通过。第二个坑循环体中只移动了当前链表指针忘了移动tail。你可以想象一下如果每接一个节点tail还是停在原地那么下一次接节点时新节点会将原来的后面节点覆盖掉最终结果链表的节点数量会比预期少很多。每接一个节点tail必须同步后移这几乎是所有链表构建类题目的铁律。第三个坑在递归写法里修改了输入链表的结构但自己没意识到。这个不一定是错误但在工程场景中需要明确是否能修改原链表。有些情况里输入链表后续还要被使用一旦在合并时调整了next指针原来的链表结构就彻底变了。遇到这种情况需要创建新节点保留原链表。第四个坑忽略了空链表的拼接。在迭代法里循环结束之后如果你不做tail.next l1 if l1 is not None else l2那么结果链表就会在某个地方断开丢失后半部分。这一步是收尾处理一定不能漏。第五个坑空间复杂度的误判。如果面试官问你“这个算法的空间复杂度是多少”你如果说 O(1)那是在迭代法下成立递归法下显然是 O(n)。所以回答之前想清楚你说的是哪一种写法。4.3 如何快速验证自己的代码正确性对于这道题我写题的一个习惯是在本地用一个非常简单的测试函数跑几组典型用例。比如把[1,2,4]和[1,3,4]合并预期是[1,1,2,3,4,4]。再比如[]和[0]合并预期是[0]。写一个将链表转成列表的辅助函数打印出来对照能快速定位自己的问题def list_to_array(head): res [] while head: res.append(head.val) head head.next return res再写一个根据数组创建链表的辅助函数测试起来就很方便了def array_to_list(arr): dummy ListNode(0) tail dummy for val in arr: tail.next ListNode(val) tail tail.next return dummy.next这种“数组 ↔ 链表”的辅助函数几乎在每一道链表题里都用得上。建议把它们存成自己的代码模板刷题效率会高很多。5. 扩展思考从合并两个链表到更复杂的场景5.1 合并 K 个有序链表这道题稍微变一下难度就上来了给你 K 个有序链表K 可能很大要求把它们全部合并成一个有序链表。常见的做法有两种。第一种是两两合并也就是用“合并两个有序链表”作为原子操作两两配对最终合成一个。这样做的时间复杂度是 O(N log K)N 是所有节点总数。第二种是用优先队列最小堆每次从 K 个链表的当前头节点里选出最小的一个接到结果链表上并把它的下一个节点入堆。最小堆维护 K 个候选节点的复杂度是 O(log K)整体时间复杂度同样是 O(N log K)。在面试中你可以从“合并两个”出发先给出朴素的多轮两两合并方案再优化到优先队列方案。这个过程本身就是一种很好的“思路递进”示范。5.2 链表归并排序另一个高频用法链表归并排序的核心就是把排序问题拆成两步第一步找到链表的中点把链表分成两半用快慢指针第二步递归地对两半分别排序然后合并两个有序链表。你看这里又用到了合并两个有序链表的逻辑。在数组的归并排序里合并阶段由于数组的随机访问特性通常需要额外空间而在链表归并排序里得益于链表指针调整的低成本合并阶段可以做到不需要额外线性空间递归栈除外。这也是链表归并排序的一个优势。如果你是为了面试做准备建议你把这个扩展关联想清楚在解释“为什么要用归并排序处理链表”时能说出“链表不像数组那样支持 O(1) 的随机访问快排的 partition 操作在链表上实现起来比较别扭而归并排序只需要不断分割和合并跟链表的物理结构非常契合”这句话会是一个加分项。5.3 从链表合并到双指针思想往更抽象的层面说合并两个有序链表的代码核心其实是一种“双指针”思想——两个指针各自身处一个有序序列每次比较它们指向的元素把更小的那个取走然后移动指针。这种思想可以迁移到很多其他问题上。经典的“合并两个有序数组”也使用了同样的思路只不过数组版本通常是从后往前填充以避免移动数组中大量元素的开销。“三数之和”“滑动窗口”“快慢指针”等很多常见算法题本质上也都是对指针移动规则的巧妙设计。所以与其说你在刷“合并两个有序链表”不如说你在练一种“用指针操纵数据结构”的基本功。这道题里的哑节点、双指针、递归出口、时间复杂度分析每一样都是后面无数道题的基础。6. 实际应用与面试中的加分细节6.1 工作中哪里会用到合并有序链表说实话现实业务里直接“合并两个有序链表”的频率不高但它的思想无处不在。举几个我能想到的例子第一个是数据库和搜索引擎里的多路归并。外部排序时磁盘里的多个有序归并段需要合并成一个全局有序的结果这个过程就是“合并多个有序序列”只是数据量远超内存。你不可能一次性把所有数据加载进来所以只能用双指针或多指针逐段比较、逐步写出结果。这道题学到的思想在理解外排序流程时非常有帮助。第二个是前端框架或工具库里的数据合并。假设两个接口分别返回了有序的时间序列数据如日志、监控指标需要合并展示到一个时间轴上。如果你写一个“合并两个有序数组”的工具函数思路几乎和这道题一模一样。第三个是分布式系统里的归并阶段。例如 MapReduce 模型里Map 阶段输出的键值对会按 key 排序Reduce 阶段需要把多个 mapper 的输出归并到一起进行聚合。这个归并过程本质上就是多路归并排序。6.2 面试中可以主动说的三个加分点第一个加分点主动提出两种解法并比较优劣。很多人在面试时只写一种解法写完就等下一题。其实这种题更适合展示你的思维广度——你可以在迭代法写完的基础上主动说“这道题还可以用递归来做但递归的空间复杂度更高所以工程上我更倾向迭代法”。这会让面试官觉得你不是只会背模板而是真的理解其中的 trade-off。第二个加分点主动讨论对原链表的修改影响。你可以问面试官“题目允许修改原链表吗如果允许我们可以复用节点达到 O(1) 空间如果不允许我会创建新节点。”这种展开会让面试官觉得你考虑到了真实工程环境里“函数是否有副作用”的问题。第三个加分点把题目和归并排序联系起来。当你写完代码后可以顺带提一句“其实这个合并过程就是链表归并排序里的核心步骤。”这样会显得你对算法体系的整体脉络有把握。6.3 我对这道题的一些经验体会我刷这道题和讲这道题都做过不少次了有一个很深的体会很多人写不出来或者写不对问题不在逻辑而在“不敢改指针”。链表这个结构在大多数语言里不像数组那么好“观察”——数组的每个元素就在那里你看得见摸得着链表则是一根根指针串起来的链条你换一下指针方向整个链条的形状就变了。写链表代码的时候最好的习惯是在纸上把每个节点的next指向画出来每一步修改都用箭头标出来。很多看似复杂的链表题画着画着就通了。另一个体会是这道题虽然简单但最好把迭代法的代码形成肌肉记忆。因为在很多后续题目里你可能没有那么多时间现场推演逻辑比如合并 K 个有序链表你一旦用到“合并两个有序链表”作为子函数就希望它不出错。所谓“基础题”就是要在需要的时候直接从脑子里调出来用。还有一点是关于代码风格的我习惯把while l1 and l2写成显式判断不使用隐式布尔转换。有些同学的代码风格喜欢写成while l1 is not None and l2 is not None这样也是完全没问题的而且对于语言不熟悉的新手来说显式判断更有助于阅读。关键是全项目保持风格统一。最后想分享一个扩展的小技巧如果面试中时间充裕可以顺便提一下“如果两个链表的头节点都不允许被修改我们可以怎么处理”。这时候的解法很直接——新建哑节点然后每次比较后创建ListNode(val)并接到尾部。但要注意这种解法的时间复杂度不变空间复杂度从 O(1) 变成 O(n)。能说出这一层往往会让面试官觉得你不只是一个“刷题机器”而是真的在思考工程问题里的约束条件。合并两个有序链表说难不难说简单也绝不简单。把这道题吃透后面再接触到链表相关的题目你会有一种“地基突然夯实了”的感觉。我个人的建议是先手写迭代法十遍以上再转去理解递归版本最后再用“合并 K 个有序链表”和“链表归并排序”来检验自己是否真的理解了这个核心步骤。这样一轮练下来这道题的内化程度应该就相当扎实了。