合并两个有序链表：迭代与递归解法及边界全解析

1. 问题拆解与链表前置知识

1.1 为什么这道题是链表操作的必修课

先说结论：力扣热题100里的第21题“合并两个有序链表”，是几乎所有刷题路线图都会放在链表专题早期的一道题。如果你刚开始刷力扣，或者链表题总是写不顺，这道题值得认真过三遍以上。

这道题的核心需求很简单：给定两个升序排列的链表，把它们合并成一个新的升序链表并返回。这里有个关键约束，题目要求我们直接操作原链表节点，而不是新建节点复制值。这意味着你没法偷懒写一个“把两个链表的值都取出来排序再重建”的方案，必须从指针层面去理解节点的拼接。

我见过太多人一开始就卡在“用迭代法写出来了但边界处理不对”“递归解法看着优雅但自己写不出来”这两种状态上。说到底，都是因为对链表这个数据结构缺乏“指针视角”的直觉。链表跟数组最大的不同在于，数组你可以用下标随意访问任意位置，链表你只能顺着next一个一个走。这种“只能往前走，不能回头”的特性，决定了链表的操作思路和数组完全不同。

这道题让我想到生活中的一个场景：你手里有两副已经按大小排好的扑克牌，现在要合成一副依然有序的牌。最自然的做法就是每次比较两副牌最上面那张，小的那张先放进新牌堆，然后继续比较。链表的合并思路跟这个一模一样，只是“牌堆顶部”换成了“当前指针指向的节点”。

作为一个常年在算法题里摸爬滚打的人，我的建议是：不要急着背解题代码，先强迫自己用手在纸上画链表。画三到五个节点的链表，模拟指针一步步移动的过程，把每一轮比较、每一次指针改动的结果都画出来。这个“画图驱动理解”的方法，比看十遍题解都管用。

1.2 读懂题目隐含的三个信息

很多初学者拿到这道题之后，第一反应是“这不就是把两个链表串起来吗”，但真正写起来才发现处处是坑。这里我把题目里没有明说、但直接影响代码正确性的隐含信息拆开讲一讲。

第一个隐含信息：两个链表可能为空。题目描述里通常会说“如果两个链表都为空，返回空链表；如果一个为空，返回另一个”。但很多人在写代码的时候会忘记这个前提，上来就访问head1.val，直接抛空指针异常。所以我的习惯是：任何链表题，第一行就处理空指针判断，不给边界留机会。

第二个隐含信息：两个链表本身有序，但并不知道哪个链表的当前节点更小。有的题目会明确说L1和L2都是升序，但并不会告诉你哪个链表的头节点更小。所以你必须每走一步都比较两个链表的当前节点值，而不是“先串完一个链表，再串另一个”。

第三个隐含信息：合并后的链表要保持稳定性，不能破坏原有的大小关系。虽然这道题没有明确说“相等元素谁先谁后”，但面试官普遍默认期望稳定合并，也就是当两个节点值相等时，优先取L1的节点。这个细节在面试中容易被追问，记住了会显得你考虑问题更全面。

以上三个信息，其实对应了三种常见的错误写法：忘记判空、错误地先串完一条链、相等时随意选择。把这三个坑提前记住，你写的代码会比大多数人的更稳。

2. 核心方法详解与实操要点

2.1 迭代解法：从头到尾的指针接力

迭代法应该是大多数人最先掌握的写法。思路很直白：用两个指针分别指向L1和L2的当前节点，用一个哨兵节点dummy作为新链表的前置头节点，然后不断比较两个指针指向的值，把较小的节点接到tail后面，同时让对应指针前进一步。

这里哨兵节点的使用非常关键。为什么需要一个dummy节点？因为合并后的链表头节点是不确定的——可能是L1的头节点，也可能是L2的头节点。如果你不借助哨兵节点，就得单独处理“新链表为空时的首次插入”这种特殊逻辑。有了dummy节点，所有节点都是“在tail后面追加”，代码结构一下就统一了。

def mergeTwoLists(l1, l2): dummy = ListNode(-1) 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.next tail.next = l1 if l1 is not None else l2 return dummy.next

注意最后一行的处理逻辑：循环退出时，说明至少有一个链表走到了尽头。这时不需要再逐个比较了，直接把另一个链表剩余的部分整体接上即可。因为两个链表本身有序，剩余的节点天然都是有序的，整体接上不会破坏整个链表的顺序。

这段代码我建议你亲手写至少三遍。第一遍对着题解抄写，第二遍盖住代码自己写，第三遍在纸上画出dummy、tail、l1、l2四个指针的变化过程。等你能把四个指针的位置都画清楚，迭代法这一关就算过了。

2.2 递归解法：把问题“缩小”的智慧

递归解法在思路上更优雅，但也是很多人第一次接触时觉得“懂了但写不出来”的典型。递归的核心逻辑其实只有一句话：当前哪个头节点更小，就选它作为结果链表的头，然后让它指向“剩余两个链表合并的结果”。

这句话听起来有点绕，我换个方式讲。假设你拿到两个链表，你要做的第一件事是确定合并后链表的头节点是谁。比较L1的头和L2的头，小的那个就是整个合并结果的头。假设L1的头更小，那么合并结果的头就是L1当前这个节点。这个节点后面应该接什么呢？应该接“L1.next和L2合并后的结果”。所以你把原问题转化成了一个规模更小的问题：合并L1.next和L2。这就是递归的神奇之处，你在解决大问题时，已经默认小问题可以以相同的方式解决。

def mergeTwoLists(l1, l2): 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为空，直接返回L2；L2为空，直接返回L1。这跟迭代法里最后一行“把剩余链表整体接上”的思想完全一致，只是表达方式不同。

我要特别提醒一个初学者容易犯的错：递归函数内部千万不能新建节点，而是直接在原链表节点上修改next指针。有些学生担心“递归会不会把原链表弄丢”，其实不会，因为每次递归只修改一个节点的next指向，而且修改之前已经把剩下的部分通过递归调用解决了。这种“先处理子问题，再拼接当前节点”的顺序，保证了不会丢失后续节点。

2.3 两张解法对比：到底该用哪一种

很多人刷题时会有个执念：总想找到“最优写法”。但实际上面试和笔试场景里，两种写法都能被接受，关键看你能否把逻辑讲清楚。我直接给个对比表，方便你对照着理解。

如果从纯工程角度说，迭代法明显更优，因为递归在极端情况下的调用栈空间不可忽视。比如两个链表各有5000个节点，递归深度会达到10000层，在部分默认栈较小的运行环境里甚至可能直接栈溢出（RecursionError）。而迭代法完全不担心这个问题，这也是我在项目里绝不使用递归去遍历链表的根本原因。

但在面试场景里，我会建议你两种都熟练掌握。面试官如果已经看过你写了迭代法，往往会在追问环节换个口吻问一句：“能用递归实现一下吗？”这时候你要是支支吾吾写不出来，前面展示的好印象就得打折扣。反过来，如果你先用递归写，面试官追问迭代法，那就是送分题。所以我给你的建议是：以迭代法作为兜底方案，递归法作为加分技能，两个都要练。

3. 边界条件与复杂度推导

3.1 四种边界情况的现场模拟

链表题最抓狂的地方永远在边界。我第一次写这道题时，自以为逻辑天衣无缝，结果Run的瞬间就被空链表用例教做人了。这四种边界情况，我不希望你再用一次提交去试错。

第一种：两个链表都为空。返回None即可，这是最简单的边界。

第二种：L1为空，L2非空。正确返回值是L2，而不是新建一个链表。因为题目要求合并，如果其中一个为空，另一个本身就是合并结果，直接返回即可。

第三种：L1非空，L2为空。同理，返回L1。

第四种：两个链表都不为空，但所有L1节点值都小于L2节点值。这种情况下，代码会先把L1全部串完，然后L1变成None，循环退出，最后把整个L2整体接到tail后面。这要求“最后整体拼接剩余部分”的逻辑必须正确，很多人在这个分支上写错，比如把tail.next指向了None。

我在教学中总结了一个检验边界是否想清楚的小技巧：写完代码后，不要急着提交，先在注释里写下这四行：

• 空链表 + 空链表
• 空链表 + 非空链表
• 非空链表 + 空链表
• 某条链表全部节点都更小

每一条都问自己一个问题：现在我的代码走的是哪个分支？返回值是什么？如果四个分支都答得出来，这题就稳了。

3.2 时间复杂度和空间复杂度到底怎么算

这道题的复杂度推导其实很有意思，也非常适合面试口述。先说时间复杂度。假设L1有n个节点，L2有m个节点。合并过程中，每轮比较只处理一个节点，要么把L1的当前节点接入新链表，要么把L2的当前节点接入新链表。所以循环最多执行n+m次，时间复杂度就是O(n+m)。

这里有个容易混淆的点：当一条链表先走到尽头时，剩余的另一条链表会整体接入，不再额外比较。这部分的操作是O(1)级别的指针赋值，不是逐节点复制。所以整体时间复杂度不会超过O(n+m)，更准确地说，当其中一个链表为空时可以做到O(min(n,m))，但通常在大O表示法里直接说O(n+m)就可以了。

再看空间复杂度，这是两种解法的分水岭。迭代法全程只用了dummy、tail、l1、l2这几个指针，额外空间是O(1)。递归法不一样，每层递归都会占用一块栈空间，最大递归深度取决于两条链表的长度总和n+m，所以空间复杂度是O(n+m)。在力扣的题解区，你会看到很多人强调“迭代法的空间复杂度优于递归”，这个结论的理论依据就在这里。

当然，在实际面试过程中，口述复杂度不需要背公式，你只要说清楚“每个节点最多被访问一次，所以时间O(n+m)；迭代只用了固定指针，空间O(1)；递归调用栈会随链表长度增长，空间O(n+m)”就足够了。能够用自己的语言把复杂度的来龙去脉讲清楚，比背诵标准答案有价值得多。

3.3 不创建新节点的意义在哪里

题目明确要求不创建新节点，这个限制值得展开几句。细想一下，如果允许新创建链表，这道题就会变得非常“数组化”：新建一个链表，遍历两个原链表，每次都new一个节点并赋值。代码写起来也挺顺，但完全没有链表操作的感觉。

这道题刻意加了这个限制，就是想逼你学会“改变指向”。链表的核心操作从来不是“创建”，而是“断开和连接”。你要理解节点之间的next关系是灵活可变的，就像调整链条的扣环一样。把一个节点从原链表中取下、接续到新链表的尾部，是通过修改指针完成的，不需要复制任何值。

从工程角度看，这也是链表的实际价值所在。在内存敏感的场景里，如果每次合并都要创建新节点，意味着额外申请了一大块内存。而原地合并只改指针，不申请新内存，效率高得多。这种“改指针而不是新建数据”的思路，在操作系统内核、内存池设计、垃圾回收算法等底层系统里尤其常见。

4. 实操过程记录与表述优化

4.1 从暴力思路到最优解的心路变迁

很多人在刚接触这道题时，先想到的是最暴力的解法：遍历两个链表，把值全部取出来放进数组，排序，再创建新链表。我承认，这个思路毫无逻辑错误，甚至时间复杂度都是O((n+m)log(n+m))，放在小规模数据上完全能跑。

但为什么我们不推荐这种写法？第一，它破坏了题目的“原地合并”约束，如果是在面试中写出来，面试官多半会直接追问“能不能用O(1)空间完成”。第二，它让你完全错失了链表操作最有价值的部分——指针修改。第三，从拓展性来说，暴力解法没有任何可以迁移到其他链表题上的skills，而迭代法和递归法是后续很多中等难度链表题的基础。

我记得自己刚开始刷题时也干过这种傻事，取出来排序确实省事，但刷到后面发现完全不行。比如“K个升序链表合并”这道困难题，用“取出来排序”的思路去套，你会发现自己压根不知道该怎么高效地处理K个链表的中途变化。而如果你从一开始就用“两两合并”的思路，后面这道困难题就能自然迁移了。

这里给个实操建议：刷题时给自己立个规矩——如果一道题要求原地操作（比如原地合并、原地反转），就算你能用额外空间写出正确答案，也要尝试写一个不使用额外空间的版本。长期下来，你的指针操作思维能力会有质的提升。

4.2 测试用例设计与本地验证流程

在力扣上提交代码前，我强烈建议你先在本地跑一遍自己的测试用例。很多人在线提交失败后才开始找bug，既浪费时间又打击信心。这里我分享一套适合链表的自测流程。

第一步，准备测试数据。我通常写三个测试函数：构造链表、打印链表、释放链表（如果是C/C++）。构造链表的代码很简单，从一个数组创建单向链表。打印链表则是把每个节点的值打印出来，方便肉眼核对。这些辅助函数虽然不起眼，却是所有链表题的公共基础设施，建议直接做成模板。

第二步，跑基础用例。至少要包括：普通有序链表合并、空链表与非空链表的合并、两个等长链表合并、一个链表长度远大于另一个、两个链表完全相等的情况。

第三步，跑随机测试。Python里可以生成大量随机数组，排序后构造链表，再调用你的merge函数，最后断言合并后的链表确实有序。这个随机测试的思路不只适用于这道题，几乎所有链表题都能用。以下是我常用的随机测试模板：

import random def random_list(length): arr = sorted(random.randint(0, 100) for _ in range(length)) dummy = ListNode(-1) tail = dummy for v in arr: tail.next = ListNode(v) tail = tail.next return dummy.next for _ in range(1000): l1 = random_list(random.randint(0, 20)) l2 = random_list(random.randint(0, 20)) merged = mergeTwoLists(l1, l2) values = [] while merged: values.append(merged.val) merged = merged.next assert values == sorted(values), f"Failed: {values}"

跑完1000组随机测试还没出错，你的代码正确性基本就板上钉钉了。这个习惯可能看起来有些繁琐，但对刷题效率的提升非常明显——你在线提交前就消除了大量低级bug，留下的时间可以去琢磨更难的题目。

4.3 力扣在线编辑器的小技巧

力扣的在线编辑器上手很简单，但还是有几个细节值得一提。第一，默认的语言模板里会给出ListNode的类定义，你不需要重复定义，直接在Solution类里写方法即可。第二，如果要在本地调试，记得自己把ListNode类补充上，否则会报NameError。

第二点经常被忽略：力扣的测试用例是自动构造链表的，你不需要关心如何从输入数组构造。但本地调试不同，你得自己写构造函数。我建议把以下几段代码存成自己的工具片段，随用随取：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def build_list(values): dummy = ListNode(-1) tail = dummy for v in values: tail.next = ListNode(v) tail = tail.next return dummy.next def print_list(head): res = [] while head: res.append(head.val) head = head.next print(res)

另外，力扣的定位日志（或者调试控制台）适合用来输出中间变量的值。如果你实在找不到bug，可以在循环里print一下l1.val、l2.val和tail.val，看看指针的移动是否符合预期。不少题目，代码逻辑很绕，靠眼睛找不出bug，但一打印马上就能定位问题。

5. 面试现场的高频追问与做题心态

5.1 面试官最爱追问的五个问题

这道题在面试中出现的概率极高，稀奇的是很多人只会刷题，却答不好面试官追加的追问。这里我把最常见的五个追问整理出来，每个都给出参考思路。

追问一：“如果一个链表为空，你的代码会怎么样？”这是考你对边界条件的理解。参考回答是：如果L1为空返回L2，如果L2为空返回L1，两个都为空返回None。

追问二：“你的递归解法会爆栈吗？”这是考空间复杂度的理解。参考回答：递归深度取决于较长链表的节点数，在数据量极大的情况下，递归调用栈可能溢出；论工程稳健性，迭代法更好。

追问三：“能不能不用递归，也不用dummy哨兵节点写一版？”别慌，这道题的迭代写法如果不借助dummy会比较麻烦，但也不是不能写。你需要单独处理“链表头是L1还是L2”的问题。这个追问主要看你是否能从不同角度拆解问题。建议平时把这个无dummy的版本也练习一遍，以防面试官突然要求。

追问四：“如果这个题要求保证稳定性，相等元素怎么处理？”参考回答：当l1.val == l2.val时，优先取L1的节点。这样从原链表视角看，相等元素的相对顺序不会改变，满足稳定合并的要求。

追问五：“两个链表已经有序，为什么不能直接把A链表的尾部接到B链表的头部？”这是最常见的误区，因为L1和L2是“各自有序”，不代表把L1的所有节点都放在L2所有节点之前仍然整体有序。比如L1最大值可能是100，L2最小值可能是1，直接相接得到1,2,3,…,100,200,…,但开头却可能是100之后接1，序列就乱套了。

把这些追问提前准备到位，面试时如果你能对答如流，对整体评价绝对加分。

5.2 编码现场最容易出现的三个手误

我做了几年技术面试官，见过无数候选人在白板上写这道题。说实话，真正会写的人不需要想太久，反而是那些“知道思路但手跟不上”的人容易犯三种低级错误。

第一种手误：把tail.next和tail搞混。很多人写着写着，把“更新l1指针”和“更新tail指针”混在一起，导致某个节点被跳过去了。解决办法是在写的时候盯着三个变量看：当前比较的l1、当前比较的l2、新链表的尾节点tail。每一步都问自己一句：哪个指针要前进？是不是该更新tail了？

第二种手误：循环条件写错。最常见的错误是写成while l1.next and l2.next，这样会导致最后一个节点不被处理，合并结果少一个节点。正确写法是while l1 and l2，只要两个链表的当前节点都存在，就要继续比较。

第三种手误：返回值写错。要么是return tail，要么是return dummy，这两种都是错的。应该返回dummy.next，因为dummy是哨兵节点，dummy.next才是合并后链表的真正头节点。我在教学生时经常说一句话：哨兵节点就是“虚拟头”，你在最后一定要绕过它。

5.3 刷题路上的心态建设

最后我想聊一点形而上的东西。很多人刷力扣热题100，总想一口气刷完，遇到这道题觉得简单，就直接跳过，觉得“我会了”。但实际上，链表题只看不练，是非常容易眼高手低的。我见过太多人面试时“我知道思路，但写不出来”，根因就是练得太少。

我自己的习惯是，一道简单题至少有三种做法时才算出关：一种是标准解法，另一种是带着限制条件的解法（比如不用递归、不用dummy），第三种是能够扩展到相似题的通用解法。比如这道题，标准解法是迭代+递归，扩展情形就是“合并K个有序链表”。平时做一道简单题，我会顺手把它的中等、困难扩展题搜出来看一眼，不求马上做出来，但至少知道它们之间的联系。

说到底，刷leetcode不能只追求AC率。AC只是起点，理解背后的数据结构本质和边界处理思想才是关键。合并两个有序链表这道题，虽然是力扣热题100里最简单的一档，但它渗透出来的指针操作、递归划分、边界控制、复杂度推导这些能力，会陪伴你一直到后面几十道链表题。

我个人在实际项目里最常用到的，反而是这道题里“哨兵节点”的思想。无论是实现一个双向链表缓存淘汰算法，还是在系统代码里拼接日志链，dummy节点这个技巧都能帮你省掉大量判空的重复代码。也正因为这样，每次我带着新人刷题，都会要求他们把这道题放在链表专题的第一位。扎实过一遍，后面会少走很多弯路。