1. 这道题为什么值得反复刷：合并有序链表的本质与常见误区

如果只让我推荐三道链表入门题，LeetCode 21“合并两个有序链表”一定在其中。它的题干极短：给定两个升序链表list1和list2，把它们合并成一个新的升序链表并返回。别看题目简单，它几乎是所有后续链表操作题的基石——合并K个有序链表、归并排序中的合并步骤、甚至 LRU 缓存里的链表节点搬运，底层都在用同样的指针推进思想。很多人在面试时觉得自己会做，但一追问“你的哨兵节点能不能省掉”“原地合并和新建节点到底差在哪”“两个链表长度极端不均衡时你的代码还对不对”，就答不上来了。这篇文章我想把这题彻底讲透：迭代法、递归法、原地合并法都给出可运行的完整代码，附上每一步的原理说明，再把面试官最常见的几个变形和坑一次性说清楚。

先说结论，方便你心里有个底：这道题的时间复杂度必然是 O(n+m)，因为每个节点至少要“看一眼”才能确定它在最终链表中的位置；额外空间方面，迭代法和原地合并法都是 O(1)，递归法最坏会到 O(n+m) 的栈空间。如果你面试时写了递归，记得主动说明这一点——大多数面试官想听的正是这个权衡。

很多初学者第一次写这题，最大的误区是试图“原地穿插”两个链表的节点，结果绕晕了自己。其实合并链表和合并两个有序数组的逻辑完全一致，只是把数组里的“下标指针”换成了链表里的“节点指针”。数组归并时你会开一个新数组放结果，链表归并时最简单可靠的做法同样是拉一个“哨兵节点”当新链表的头，然后两个指针分别从两个链表头部出发，谁小就把谁接到结果链表的尾部。这个思路直观、不容易出错，是保底方案。

不过只有保底方案是不够的。面试是淘汰制，别人会原地合并，你不会，那差距就出来了。所以这篇文章会花大篇幅讲清楚三种写法的实现细节和适用场景，最后还附上我整理的几组边界测试样例，你可以直接拿去验证自己的代码。

2. 迭代法：哨兵节点与三指针推进的完整走读

2.1 为什么一定要用哨兵节点

先看最经典的迭代写法。核心思路是维护一个dummy哨兵节点作为结果链表的头节点前置，同时维护cur指针指向结果链表的尾部，每次从list1和list2当前指针所指的节点中挑一个值更小的，接到cur后面，然后让对应的链表指针前进一位。最后把还没走完的那条链表的剩余部分直接接上。

代码非常短，但每一行都有讲究：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def mergeTwoLists(list1, list2): dummy = ListNode() # 哨兵节点 cur = dummy # 结果链表尾指针 while list1 and list2: if list1.val <= list2.val: cur.next = list1 list1 = list1.next else: cur.next = list2 list2 = list2.next cur = cur.next # 把剩余部分直接接上去 if list1: cur.next = list1 if list2: cur.next = list2 return dummy.next

为什么非要一个dummy？因为合并结果可能是空链表，也可能是list1或list2中的任意一条。如果不用哨兵节点，你就得单独处理“结果链表为空时头节点怎么赋初值”的问题，代码会多出两三个if分支。哨兵节点的作用本质上和数组归并里“预先分配一块输出数组”一样：先占一个位置，后续无脑往尾指针后面接就行，最后返回dummy.next就拿到了真正的头节点。

这里有个面试细节：if list1.val <= list2.val用<=还是<？两种写法对最终结果没有影响，因为两个链表本身就是有序的，重复值谁先谁后都合法。但用<=可以让代码语义更明确：当两个值相等时优先取list1的节点，这算是一种稳定的归并行为。面试时如果被问到，能答出这个区别会加分。

2.2 尾部拼接与循环不变式的证明

很多人的代码毛病出在循环结束后的处理。循环退出只有两种可能：list1走完了，或者list2走完了。此时另一个链表剩余的部分必然都是大于等于已合并部分所有值的有序序列，所以直接把cur.next指向它即可，不需要再逐个节点比较。这也是归并算法“懒处理”的精髓：剩余部分天然有序，整体顺序不会被破坏。

如果从“循环不变式”的角度严谨证明这个写法的正确性，过程是这样的：

• 初始状态：dummy是哨兵，cur指向dummy，此时结果链表为空。两个待合并链表的所有节点都未被改动，显然成立。
• 循环中假设某次迭代开始时，cur指向结果链表的尾部，结果链表中的节点严格按从小到大排列，且结果链表中的所有节点值都小于等于list1和list2当前头节点的值。此时比较两个头节点，把较小的那个接过来，新结果链表的末尾变成了这个节点，依然有序，且新末尾节点的值一定小于等于剩下两个链表头节点的值，所以下一次迭代前不变式依然成立。
• 循环结束后，直接把剩余链表接上，不变式覆盖到全部节点。

把这套证明逻辑在脑子里过一遍，比背代码有效得多。面试官如果追问“你怎么保证这个算法是对的”，你能说出上面三句话，基本就过关了。

2.3 时间复杂度与空间复杂度：为什么是 O(n+m) 和 O(1)

时间复杂度是 O(n+m)，这个结论几乎不用解释：每轮循环只处理一个节点，两个链表合计有 n+m 个节点，最多循环 n+m 次。空间复杂度 O(1) 是很多人容易怀疑的点：明明新建了一个dummy节点，为什么不算 O(n)？

原因在于dummy是单个固定节点，不随输入规模变大而变多。链表的绝大多数节点都是直接复用原链表的，我们没有为它们申请新的内存。这与递归法不同，递归每层调用都要占用一块栈帧，最坏情况下递归深度等于两个链表的节点总数，所以递归的空间复杂度是 O(n+m)。这个差异在链表很长时非常明显，也是我在工程中更推荐迭代法的核心理由。

提示：有些语言里你不需要真的new一个哨兵节点，比如 C++ 里可以直接在栈上声明一个ListNode dummy;，取地址&dummy作为头。但 Python 里所有对象都在堆上，写dummy = ListNode()是最直接的等价方式。

3. 递归法的精巧与代价：什么场景才值得用

3.1 递归写法的代码与直觉理解

递归解法在 LeetCode 题解区永远有一席之地，因为它真的太短了：

def mergeTwoLists(list1, list2): if not list1: return list2 if not list2: return list1 if list1.val <= list2.val: list1.next = mergeTwoLists(list1.next, list2) return list1 else: list2.next = mergeTwoLists(list1, list2.next) return list2

怎么理解这段代码？可以把mergeTwoLists(list1, list2)读作“返回一个以较小节点为头、内部已经完成合并排序的链表”。每次递归只解决一件事：确定当前的头节点是谁。如果list1.val更小，那么结果链表的头节点就是list1当前的节点，它的next应该指向什么？指向“合并list1.next和list2后的结果链表的头节点”。于是递归调用自己，把规模缩小了一步。

递归的终止条件是有一个链表为空，这时直接返回另一个链表，不需要做任何合并。这个思路优雅，但不是零成本：每层递归都要消耗栈空间，且函数调用本身有开销。对于这道题，n+m 等于几千甚至几万时可能感觉不到差异，但如果链表长度达到十万级，递归深度过深可能导致栈溢出。这也是为什么《算法导论》里讲归并排序时强调：递归版本适合教学，实际大规模排序要用迭代版本。

3.2 递归尾调用优化：别被“尾巴递归”这两个字骗了

有同学看到这个写法是“尾递归”，就以为编译器会自动优化成循环，空间复杂度会变成 O(1)。这里要泼盆冷水：合并两个有序链表的递归写法虽然在逻辑上是尾调用——递归调用返回值直接被当前函数return——但在普通 Python 解释器里并不做尾调用优化。Python 官方在设计时就明确说过，不打算支持尾递归消除，因为这会牺牲栈回溯的调试能力。所以递归法在 Python 里的空间复杂度就是 O(n+m)，不是 O(1)。

不过这个写法在某些函数式语言里确实可以被优化。如果你用 Haskell、Elixir 这类语言刷题，尾递归优化后空间复杂度会和迭代法一样。但面试场景下如果你用 Python 或 Java，选递归法就要做好“背 O(n+m) 空间”的觉悟，并主动向面试官说明。你主动说，那是你清楚代价；你不说等面试官追问，那就是基础不扎实。

3.3 递归与迭代：到底该选谁

我个人给出的选择建议是这样的：如果只是为了解题拿最快速度写出来，递归法确实省事，因为不需要维护指针状态，逻辑更接近人类的“分而治之”直觉。如果链表规模可能很大，或者这是工程代码的一部分，迭代法更稳妥，因为空间占用确定是常数级，而且不会因为数据量增长触发栈溢出。

额外提醒一点：LeetCode 的默认测试用例规模一般比较温和，所以递归法在平台上跑也能过。但真实业务里，谁也不敢保证线上数据不会突然变成一条十个节点的链表——不，反过来，谁也不敢保证它不会变成一条一千万节点的链表。工程上我会默认选迭代法。

4. 原地合并法：不申请新节点也能完成合并的指针艺术

4.1 “原地”到底意味着什么：重新理解指针复用的边界

前面提到的迭代法虽然只新建了一个哨兵节点，时间复杂度也是 O(1) 额外空间，但它毕竟动用了dummy这个“新”节点。原地合并法要求更高：连哨兵节点都不新建，直接在两个输入链表上通过调整next指针完成合并，最后返回两条链表中头节点值更小的那一个作为结果头节点。

实现方式并不复杂，核心是维护三个指针：l1、l2和cur。l1和l2分别指向两条链表中尚未合并的第一个节点，cur指向已经合并好的结果链表的尾部。每次比较l1.val和l2.val，把较小者接到cur.next，然后对应的指针前进。最后同样是把剩余部分链接上。区别在于：初始时cur不指向哨兵，而是指向None，我们需要特殊处理结果链表的头节点。

代码可以这么写：

def mergeTwoListsInPlace(list1, list2): if not list1: return list2 if not list2: return list1 # 确定结果链表的头节点 if list1.val <= list2.val: head = list1 list1 = list1.next else: head = list2 list2 = list2.next cur = head while list1 and list2: if list1.val <= list2.val: cur.next = list1 list1 = list1.next else: cur.next = list2 list2 = list2.next cur = cur.next if list1: cur.next = list1 if list2: cur.next = list2 return head

你有没有发现，这个代码和带哨兵节点的迭代法几乎一模一样，只是把“哨兵节点”换成了“先手动确定头节点”的几步。所以有些面试官会问：原地合并和带哨兵的迭代法本质区别是什么？答案其实很微妙——两者都不创建额外链表，都复用了原有节点，唯一区别是哨兵节点方案多了一个临时节点，而原地方案用一次判断替代了哨兵。从空间复杂度看它们都是 O(1)，从代码风格看哨兵方案更统一，从“抠门”程度看原地方案更能体现对指针的掌控力。

4.2 三种解法的对比：从工程、面试、扩展性三个维度看

这里我整理了一张表，建议你收藏起来，面试前快速扫一眼：

工程上我更推荐迭代法，原因很简单：哨兵节点让代码无需单独处理头节点为空的情况，逻辑分支更少，后期维护起来不容易漏边界。面试时如果你想展示自己对链表的控制力，可以在迭代法讲完以后主动说：“如果要求不使用额外节点，我可以改写成原地版本，只是需要先处理一下头节点的确定逻辑。”这比一上来就写原地版本更稳妥——万一你在处理头节点的几个分支里写漏了，面试官会直接看到。

4.3 原地合并法的潜在陷阱：头节点处理与空链表

原地合并法的第一个潜在陷阱是两个输入链表都为空，这时直接返回None。上面的代码开头已经用两个if处理了空链表，所以后面可以放心比较list1.val和list2.val。第二个陷阱是在确定head时，有些初学者会把head和cur混在一起写，结果头节点没接上，返回了一个子链表。这里的关键是：一旦确定了head，就要立即让对应的l1或l2指针前进一位，否则头节点会被重复接入，形成环。

第三个陷阱是循环结束后忘记接尾部。比如list1提前走完，此时list2还剩一大截，如果你不把cur.next = list2加上，结果链表就断了。很多人在白板上写代码时容易漏掉这两行，因为觉得“循环结束了不就行了吗”——不是的，剩余节点是整个链表的组成部分，必须显式接上。我习惯在写完循环后立刻补上两个if，把它当成固定动作，就像写文件时一定记得close()一样。

注意：合并时如果直接修改了list1和list2的节点next指针，原链表的结构就被破坏了。如果调用方后续还要使用原始链表，这种写法会导致数据丢失。面试时一定要确认题意是否允许修改原链表。

5. 面试变形题与深度追问：从合并两个到合并K个

5.1 合并K个有序链表：分治合并与优先队列的两条路线

LeetCode 21 最常见的变形是 LeetCode 23“合并K个有序链表”。刚把两个链表的合并练熟，你会怎么处理 K 个？最朴素的做法是每次拿一个链表和结果链表做两两合并，总共做 K-1 次，时间复杂度是 O(K × N)，其中 N 是所有链表节点的总数——因为第一轮要比较 K 个链表的头节点，第二轮变成 K-1 个，平均复杂度偏高。更优的做法有两种：分治合并和优先队列。

分治合并的思路是：把 K 个链表两两配对，每对用“合并两个有序链表”的方法合并成一条，然后继续两两配对，直到剩一条。这样每一轮需要合并的链表数量减半，总共进行 logK 轮，复杂度降为 O(N log K)。写成代码时，基本的两个链表合并函数就是 LeetCode 21 的解法，直接复用。

优先队列的思路更直接：把所有链表的头节点放进一个小顶堆，每次从堆顶弹出最小的节点，接到结果链表的尾部，然后把该节点的next推入堆中。堆的大小为 K，所以每次操作是 O(log K)，总共 N 次操作，总复杂度同样是 O(N log K)。面试官通常希望你说出这两种方案并比较优劣：优先队列代码更简洁，但需要额外的堆空间；分治合并空间取决于递归深度。这道变形题可以算是检验你对 LeetCode 21 是否真正理解的试金石，因为它的核心操作仍然是“比较两个节点值并推进指针”。

5.2 链表中判断有序性、去重、反转与合并的组合拳

刷题圈里特别爱把链表题组合起来考。比如面试官给你一个乱序链表，让你先排序再去重，最后反转输出——本质上就在考归并排序的合并步骤加链表反转。归并排序在链表上的实现，正是递归地把链表拆成两半，分别排序，然后用“合并两个有序链表”的方法把两个有序子链表合起来。所以 LeetCode 21 不只是解题，它是归并排序在链表上能跑起来的关键一环。

再举个例子：LeetCode 148“排序链表”要求 O(n log n) 时间复杂度和 O(1) 空间复杂度。你如果用归并排序递归实现，栈空间会是 O(log n)，严格来说是 O(log n) 而不是 O(1)。要实现真正的 O(1) 空间，需要改成自底向上的迭代归并，先从长度为1的子链表开始两两合并，再合并长度为2的……每一轮合并子链表时用的正是“合并两个有序链表”。很多人做这题卡住，不是不会归并排序的思想，而是不会在链表上正确写“找到一个子链表的结尾并切开”这步操作。LeetCode 21 掌握得越熟练，写 LeetCode 148 时就越顺手。

5.3 面试追问清单：这些问题你都能接住吗

我把这几年在面试中遇到过的追问整理成了一份清单，你可以用来自查：

1. 如果两个链表中存在大量重复值，你的比较操作还能不能保持稳定？
2. 如果其中一个链表已经为空，你的代码是否正确返回另一个链表，而不产生额外的空节点？
3. 如果用迭代法合并后原链表结构被破坏了，你是否清楚哪些节点被移动、哪些节点仍属于原链表？
4. 如果你的合并函数需要支持“不修改原链表”的语义，你会怎么调整实现？

第4个问题最阴险。很多人的第一反应是“那就重新拷贝每个节点呗”，但完整答案是：新建一个哨兵节点和一个tail指针，每次比较时新建一个值为较小者值的节点接到tail后面，而不是把原节点接过去。这样原链表完全不受影响，时间复杂度依然是 O(n+m)，空间复杂度变成 O(n+m)。拷贝节点和移动节点是两种完全不同的合并语义，面试官通过这一问就能看出你对链表内存模型的理解深度。

6. 测试样例与调试心得：用极端输入验证你的代码

6.1 必跑的六组测试用例

写完了三种解法，怎么验证它们是对的？我整理了几组必跑的测试样例，你可以直接当作回归测试用例用：

第4个用例里的两个1和第5、6个用例重点验证循环结束后尾部拼接是否正确。很多人在第6组用例上翻车：list2的头节点比list1的头节点小，结果链表头节点来自list2，如果你的原地合并版本头节点初始化写错了，这一组用例立刻暴露问题。

6.2 白板调试法：画指针，不画链表

一个我强烈推荐的调试技巧：不要画整条链表，只画三个指针。在白板或草稿纸上把l1、l2、cur分别标在对应节点上，每执行一行代码就更新一次指针位置。这样执行到循环体内部时，你很容易发现某个指针没有前进、或者cur.next接错了节点。

我自己刷这道题时养成的一个习惯是：每次写完后，用第4组用例走一遍完整流程，数一数合并后的链表节点个数是否等于两个链表节点个数之和。如果数量对不上，说明要么漏接节点，要么形成了环。长度校验是链表题最重要的“金标准”，比看十万个中间打印都管用。

6.3 常见报错与解决速查表

最后给你整理一张排查速查表，覆盖我自己和身边同事刷题时遇到的高频问题：

这些坑我在带新人时见过无数次，几乎每个人都至少踩过其中两个。提前把这张表贴在你刷题笔记本的首页，能节省你大把的调试时间。

7. 写在最后：从“会写代码”到“讲清楚代码”

刷 LeetCode 21 很容易陷入一种错觉：代码跑通了，这题就会了。但面试时真正拉开差距的，是你能不能讲清楚“为什么”。为什么用哨兵节点？为什么循环条件是while list1 and list2？为什么最后可以直接拼接剩余链表？这三个问题能答得流畅，你对链表的理解就已经超过大多数只背题解的人。

我个人的习惯是刷这道题时同时写三个版本，然后对比它们的空间复杂度和代码可读性。在工程里，我会选迭代法，因为它的 O(1) 空间和清晰的循环结构最适合放进生产代码；在面试里，我会先讲迭代法，再拿递归法展示思路的简洁，如果面试官追问，再补充原地合并版的改动点。这套“由稳到巧”的展示节奏，几乎百试百灵。

如果你现在正在准备面试，建议你把这道题当成一个起点，顺着它去刷 LeetCode 23（合并K个有序链表）、LeetCode 148（排序链表）、LeetCode 86（分隔链表）和 LeetCode 143（重排链表）。你会发现它们都在反复使用同一个动作：比较两个节点、接指针、移动指针。把 LeetCode 21 吃透，后面这些题的核心逻辑你就已经会了一半。