合并两个有序链表这道题，算得上是链表入门里最经典的一道了。很多人在 LeetCode 上刷题，第一道链表题往往就是它。我当年刚开始学数据结构的时候，也被这道题卡过一阵子——不是看不懂思路，而是写代码的时候总是控制不好指针，要么是空指针异常，要么是链表断掉了。后来练多了，才发现这道题其实是在考两件事：第一，你懂不懂链表在内存里到底是怎么串起来的；第二，你会不会把“合并两个有序数组”的思路灵活迁移到链表结构上来。这两点搞明白了，这道题基本就没什么难度了。
这篇博文我就从题目本身出发，把这道题涉及的思路、两种主流写法（迭代和递归）、边界条件的处理、常见的坑以及它在实际场景中的价值，全部拆开揉碎讲清楚。无论你是刚开始刷题的新手，还是准备面试的开发者，这篇文章应该都能给你一些参考。
1. 题目拆解与核心思路
1.1 题目到底在考什么
先简单回顾一下题目本身：给你两个有序链表的头节点l1和l2，要求把它们合并成一个新的有序链表并返回。这里的“有序”一般默认是升序，而且题目要求合并后的链表依然是升序的。链表节点的定义通常长这样：
class ListNode: def __init__(self, val=0, next=None): 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.val=1，l2.val=2，1 <= 2，所以执行l1.next = merge(1->3->5 中的 3->5, 2->4)，然后返回1这个节点。当前先不急着返回，我们需要先算出内层递归的结果。- 内层调用
merge(3->5, 2->4)：比较 3 和 2，2 更小，所以执行l2.next = merge(3->5, 4)，返回2这个节点。 - 继续内层调用
merge(3->5, 4)：比较 3 和 4，3 更小，执行l1.next = merge(5, 4)，返回3。 - 继续调用
merge(5, 4)：比较 5 和 4，4 更小，执行l2.next = merge(5, None)，返回4。 merge(5, None)：l2为空，直接返回l1，也就是5。- 然后一路往回返回：
4 -> 5，3 -> 4 -> 5，2 -> 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的第一个节点值是 2，l2的第一个节点值也是 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 个有序链表”和“链表归并排序”来检验自己是否真的理解了这个核心步骤。这样一轮练下来，这道题的内化程度应该就相当扎实了。
