合并两个有序链表：链表操作母题，迭代与递归全解析

力扣第21题“合并两个有序链表”，我在带项目组同学刷题时总会把它排在链表专题的第一位。这道题的难度标签只是“简单”，但它几乎是所有链表操作的浓缩模板：指针怎么走、边界怎么判、递归怎么写、头节点怎么处理，全部落在这个只有十几行的解法里。学会它，不只是过一道题，而是把链表这一类题的地基打牢。

这道题适合所有正在刷力扣的人，无论你是刚学数据结构的在校生，还是准备面试的在职工程师，都值得把迭代法和递归法各写一遍。面试里它经常作为热身题出现，但更多时候它是后续难题的子步骤——合并K个有序链表、链表的归并排序、两两交换节点，本质上都能追溯到这道题的思路。下面我从题目拆解开始，把两种主流解法、边界测试、常见坑位以及延伸考点一次讲透。

1. 题目拆解与核心考点分析

1.1 先读懂题目在说什么

原题描述很简洁：给你两个升序排列的链表l1和l2，把它们合并成一个新的升序链表并返回。所谓“新链表”，指的是要拼接出完整的节点序列，而不是简单地把两个链表存进数组再排序。

需要注意题目里的几个隐含信息。第一，输入的两个链表本身就是有序的，这是解题的前提，你的算法必须利用这个有序性，而不是先无脑排序。第二，节点个数范围通常在[0, 50]，所以这两种链表的长度都可能为0，空链表是最容易被忽略的边界情况。第三，这里的链表是单链表，每个节点只有val和next两个字段，无法随机访问，只能一个节点一个节点地走。

我在做这道题时会先在纸上画一个例子，比如l1 = [1,2,4]、l2 = [1,3,4]，手动模拟合并过程。这个过程其实就是在两个链表头部各放一个指针，比较当前值，小的那个接到结果链表尾部，然后指针后移。谁先走完，剩下那条链表的剩余部分直接拼接就行。算法思维就是这么简单，真正的难点全在实现细节上。

1.2 这道题到底在考什么

如果你只把这道题当成“写出来就行”，那收获会小很多。我建议你从四个维度去审视它。

第一是指针操作基本功。在C/C++里，你要熟练使用结构体指针的->运算符，清楚p = p->next这类移动操作的含义；在Python里则是理解对象引用和None的判断。语言不同，但指针移动的逻辑完全一致。

第二是边界条件处理。这是链表题最容易翻车的地方。两个链表都为空、一个为空、其中一个先遍历完，每一种情况都必须正确处理。很多人写出的代码在常规用例下跑得通，一遇到空链表就报空指针异常，就是因为没有在访问val之前先检查当前节点是否为空。

第三是递归思维。这道题可以用递归优雅地解决，而且代码比迭代版更短。但递归不是“背代码”，你需要能够自己推导出递推关系，说清楚每一层递归做了什么、终止条件是什么。很多初学者递归写不好，本质是没有理解“子问题”这个概念。

第四是头节点的动态变化。合并过程中，结果链表的头节点是l1的头还是l2的头，取决于两个首节点哪个更小，这在写代码前是未知的。如何处理这种“头节点可能变化”的场景，就是虚拟头节点要解决的问题，这也是链表面试题里的高频考点。

1.3 为什么说它是一道“母题”

我习惯把这类题目称为母题，因为它能向外延伸出一大串力扣题目。合并两个有序链表是合并K个有序链表的子过程，后者是力扣23题；链表的归并排序需要找到中点、分割链表、再合并两个有序链表，核心步骤就是本题；甚至反转链表、两两交换节点，也需要你对链表指针的移动足够敏感。

延伸一个容易被问到的点：如果不让你新建任何节点，只允许改变next指针指向，能不能完成合并？答案是完全可以。因为合并的本质只是重排节点顺序，不需要复制val。这也解释了为什么这道题的迭代解法空间复杂度能做到O(1)。理解了这一层，你再去看面试官后续追问“能不能原地合并”，就不会慌。

2. 迭代法：用虚拟头节点把边界交给代码

2.1 核心思路与完整代码

迭代法的思路可以用一句话概括：两个指针分别指向两个链表，谁小谁被接入结果链表尾部，然后该指针后移；某一方耗尽后，把另一方剩余部分直接拼接。

这里我会先给出C++、Python、Java三种语言的实现，因为不同语言对链表和指针的表达略有差异，但核心逻辑是同一套。

// C++ ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* dummy = new ListNode(-1); ListNode* cur = dummy; while (l1 != nullptr && l2 != nullptr) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = (l1 != nullptr) ? l1 : l2; return dummy->next; }

# Python class Solution: def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode(-1) 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

// Java public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val < l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = (l1 != null) ? l1 : l2; return dummy.next; }

代码里最容易忽略的是最后一行cur->next = ...，它的作用是处理“其中一个链表先耗尽”的情况。比如l1已经为null，但l2还剩三个节点，由于l2本身是有序的，直接把这剩余部分接在结果链表尾部即可，不需要再逐个比较。

2.2 为什么这里需要一个虚拟头节点

很多初学者第一次写这道题时，会选择先处理l1和l2首节点中较小者作为结果的head，然后循环拼接。这样做不是不行，但会让代码多出大量分支判断。

虚拟头节点（dummy head）的妙处在于：无论合并后的头节点是哪个，我们都先创造一个占位节点，让cur从它开始往后拼接。循环结束后直接返回dummy->next就是真正的头节点。这样一来，“头节点未知”的问题被彻底绕开，代码结构也更统一。

这里要区分两个概念：题目给我们的两个链表是“不带头结点的单链表”，即第一个节点就是数据节点；而我说的虚拟头节点是为了简化合并逻辑而临时创建的哨兵节点，它并不属于结果链表的一部分。搞清楚这个区别，等你学到“带头结点的单链表”相关题目时就不会混淆。

2.3 复杂度分析：时间和空间的取舍

迭代法的时间复杂度是O(m + n)，其中m和n分别是两个链表的长度。因为每轮循环只移动一个指针，合并过程中每个节点恰好被访问一次，这是合并有序序列在比较模型下的理论下界，没有更快的可能。

空间复杂度是O(1)，但这里的O(1)有一个前提：我们只创建了一个dummy节点，合并过程中没有复制任何链表节点，所有的next修改都是原地进行的。如果你在循环里new了新节点并拷贝val，空间复杂度就会变成O(m + n)，那就完全没必要了。

这一点在面试时值得主动提。面试官问你复杂度，你答“时间是O(m+n)，空间是O(1)”，顺便补充一句“因为我们只是重排指针，没有创建新节点”，这比干巴巴报一个复杂度要好得多。

3. 递归解法：两行代码背后的递归模型

3.1 把问题看作可递归的子结构

递归解法看起来简洁，但理解门槛比迭代法更高。核心思路是：两个链表的合并结果，可以描述为“取较小的头节点，然后把这个头节点的next指向剩余部分的合并结果”。

这句话用递归的语言翻译一下：定义一个函数merge(l1, l2)，它返回合并后的链表头节点。如果l1->val < l2->val，那么结果的头节点就是l1，而l1->next应该是merge(l1->next, l2)的返回值。反过来，如果l2更小，同理。

这里最关键的一步是相信递归能解决子问题。你不需要手动跟踪每一层递归的细节，只需要确认：递归函数能返回正确的子链表，并且终止条件写对了。这就是递归思维的“信任跳跃”。

3.2 递归版代码与逐行解读

# Python 递归版 class Solution: def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]: if not l1: return l2 if not l2: return l1 if l1.val < l2.val: l1.next = self.mergeTwoLists(l1.next, l2) return l1 else: l2.next = self.mergeTwoLists(l1, l2.next) return l2

对照执行一条用例就能看清它的逻辑。比如l1 = [1,3]，l2 = [2]。第一层：1 < 2，所以取l1的头节点1，问题变成合并[3]和[2]；第二层：3 > 2，取l2的头节点2，问题变成合并[3]和[]；第三层：l2为空，返回[3]。于是第二层得到2 -> [3]，第一层得到1 -> [2,3]，合并完成。

注意递归版里没有新增节点，它也是原地修改next指针。l1.next = self.mergeTwoLists(l1.next, l2)这行代码做的事情，是把较小节点的next指向一个“已经被正确合并好的子链表”，这是整个递归的精髓。

3.3 递归的代价：栈空间与长链表

递归解法虽然代码短，但有一个不可忽视的代价：递归深度等于两个链表的总长度。每一次函数调用都要在系统栈上分配栈帧，调用链最长会达到m + n层。

对于本题的数据范围，节点最多50个，递归几十层完全没问题。但面试追问时，你一定要能说出这个隐患：如果链表长度达到几万甚至几十万，递归解法可能触发栈溢出，而迭代解法完全不受影响。在C++中，默认栈空间有限，这种问题更现实；Python的递归调用深度也有默认上限（通常是1000左右），超过就会报RecursionError。

所以在生产环境或面对超长链表时，迭代法永远是更稳妥的选择。这也提醒我们：代码简洁不等于实现更优，空间复杂度同样是评判算法的硬指标。

3.4 面试时两种写法怎么选

如果你在面试中被问到这道题，我建议这样处理：先写迭代法，边写边解释思路，因为它稳定高效、没有栈溢出风险；写完以后再补充一句“如果让我用递归实现也可以，代码更短”，然后把递归版说一遍。这样既展示了你的工程思维，又展示了递归建模能力，是加分项。

反过来，如果面试官明确要求用递归，你再写递归版，同时主动说明递归的深度代价和适用场景。面试官问“两种方案你选哪个”，正确答案没有唯一标准，重点是你能把自己的取舍讲清楚。我个人偏好迭代法，因为实际工作里面对的链表可能非常长，稳定性优先。

4. 边界条件与测试用例设计

4.1 一个都不能少的测试用例清单

刷题不能只求“提交通过”，你还需要设计一套完整的测试用例来覆盖所有场景。下面这些用例我在本地调试时必测，建议你也照这个清单过一遍。

很多人只测1和4，漏掉负数用例和全相同值用例。负数不重要吗？链表节点值范围是[-100, 100]，忽略负数值会导致比较逻辑的直觉判断失效。全相同值用例则能检验你的比较符写法是否会导致节点丢失。

4.2 本地怎么搭一个链表测试脚手架

力扣的在线编辑器已经帮你处理好了链表构造和输出，但如果你想在本地跑代码、做更多实验，需要自己写两个小工具函数：一个用数组构造链表，一个把链表打印成数组格式。以Python为例：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def build_linked_list(arr): dummy = ListNode(0) cur = dummy for val in arr: cur.next = ListNode(val) cur = cur.next return dummy.next def linked_list_to_list(head): res = [] while head: res.append(head.val) head = head.next return res # 使用示例 l1 = build_linked_list([1, 2, 4]) l2 = build_linked_list([1, 3, 4]) merged = Solution().mergeTwoLists(l1, l2) assert linked_list_to_list(merged) == [1, 1, 2, 3, 4, 4] print("test passed")

注意build_linked_list函数里的dummy节点仅仅用于构建过程的方便，它和题目中的虚拟头节点是同一个套路——当你需要一个指针从头开始逐个往后接节点时，虚拟头节点能省掉大量“当前是否为空”的判断。把这个辅助工具存成模板，之后所有链表题都能复用。

4.3 相等节点怎么处理：稳定性的细节

当l1->val == l2->val时，迭代版代码中走的是else分支，也就是取l2的节点；递归版同样在相等时取l2。这完全符合题目要求，因为题目不关心相等节点的先后顺序，合并结果只要有序就算正确。

但如果你后续用这个合并逻辑实现“链表的归并排序”，稳定性就变得重要了。归并排序要求相同值的元素保持原有相对顺序，此时你应该在相等时取前一个链表的节点。具体来说，把比较条件从l1->val < l2->val改成l1->val <= l2->val，相等时优先取l1的节点。这是一个很容易被忽略的细节，面试官很喜欢在这里挖坑。

我在实际练习中的习惯是：先按题目要求写“取哪个都行”的版本，再思考“如果要求稳定排序应该怎么改”。这样一来，一道题就吃出了两道题的价值。

5. 常见错误与调试经验实录

5.1 三个最典型的报错现场

这道题的错误类型非常集中，我整理了自己和身边同学踩过最多的三个坑。

错误一：空指针解引用。典型写法是在while循环里直接访问l1->val，但没判断l1是否已经为null。当两个链表长度不等时，较短的链表先走完，下一轮循环l1已经为空，再访问l1->val就崩溃了。解决办法是循环条件写成while (l1 && l2)，保证循环体内两个指针都非空。

错误二：忘记移动cur指针。有些初学者把cur->next = l1; l1 = l1->next;写完后，忘了cur = cur->next;这一行。结果就是每次循环都把新节点接到了同一个固定的cur后面，逻辑完全错乱，输出链表严重变形。链表题里“指针移动”和“指针连接”是两件事，缺一不可。

错误三：返回了虚拟头节点。前面说过，结果链表的真正头节点是dummy->next，但总有人写return dummy;。虚拟头节点的值是初始化的-1，它是我们虚构的占位节点，不属于结果。这个问题在输出时特别隐蔽，因为你看到的结果数组开头总是多出一个-1，容易让新手误以为是自己排序出了问题。

5.2 链表调试三板斧

链表题的调试和其他算法题不太一样，你没法像数组那样直接打印下标。我总结了三个实用技巧。

第一，写一个链表的打印函数。每次操作后打印一遍当前链表，能非常直观地看到指针连接是否符合预期。上面给出的linked_list_to_list就是干这个用的。

第二，把长链表用例换成最短用例来跑。比如用[1]和[2]测试，手动在纸上画出每一步的指针变化，对照代码走一遍，几乎所有逻辑错误都能暴露出来。我调试链表问题时从来不在大用例上死磕，都是先缩到最简。

第三，给关键步骤加注释。在cur = cur->next、cur->next = l1这些行旁边写清楚“当前节点移到新链表的尾巴”“把l1当前节点接到新链表尾”，代码写完回头排查时效率会高很多。

5.3 C++内存管理的额外注意点

如果使用C++，还有两个内存相关细节值得注意。第一，new出来的dummy节点在本地练习时需要delete，否则会内存泄漏。力扣在线环境通常不检查这个，但本地调试会有工具提示。

第二，递归版在C++中修改的是原链表的next指针，这意味着输入链表会被破坏。如果面试官问“合并后还想保留原链表怎么办”，你就需要新建节点、复制数据，代价是空间复杂度变成O(m+n)。这是一个典型的“时间与空间权衡”问题，答案本身不重要，关键是你能意识到原链表被修改这个副作用。

6. 一道题串起的链表知识网

6.1 从这道题直接延伸的面试题

会做这道题只是起点，面试官更爱的是在它基础上层层加码。最常见的延伸是力扣23题“合并K个升序链表”。直接套用两两合并，每合并一次都要遍历一遍当前结果链表，总复杂度偏高；更优的做法是利用优先队列，每次从K个头节点中取出最小值，复杂度是O(n log k)，其中n是总节点数。

另一个直接相关的题目是“排序链表”，也就是链表的归并排序。它的核心步骤就是找到链表中间节点并断开，然后递归排序两个子链表，最后调用你写的mergeTwoLists把两个有序链表合并。可以说如果你把这道21题写得滚瓜烂熟，归并排序的合并部分完全不用重新思考。

链表类的面试题其实高度套路化，常见的几个方向不外乎：反转链表、找中间节点、判断是否有环、合并两个有序链表、找两个链表的交点。每个方向都有模板解法，而本题恰好是“合并”方向的基石模板。

6.2 单链表基本操作速查：插入、删除、反转、遍历

链表题的底层能力是单链表的基本操作。以C++结构体链表为例，你需要形成肌肉记忆。

插入节点：在节点p之后插入新节点node的操作是node->next = p->next; p->next = node;。注意这两行的顺序不能反，如果先写p->next = node，原本的后继节点就找不到了。

删除节点：删除p的后继节点，操作是p->next = p->next->next;。如果被删节点是动态申请的，别忘了释放内存。这里同样要先保留待删节点的指针，否则你没法delete它。

反转链表：迭代法是三指针滑动，pre、cur、next；递归法则先反转后继部分，再处理当前节点。这道题虽然不考反转，但它和合并都属于“指针重排”类操作，理解了一个，另一个上手很快。

遍历：while (p != nullptr) { visit(p); p = p->next; }，这是所有链表算法的基础动作。本题的合并循环本质上就是两个链表交替遍历的过程。

这些操作单独看都很简单，但组合到一起就容易绕晕。我的建议是专门用一个小时把插入、删除、反转、遍历都手写一遍，直到不假思索就能写对，再开始刷链表题。

6.3 带头结点与不带头结点的区别，以及虚拟头节点的妙用

力扣上的链表题，绝大多数给的都是“不带头结点的单链表”，也就是链表第一个节点直接存储数据，没有额外的哨兵节点。这种设计让输入输出更直观，但处理头节点变化的问题时会麻烦一些。

与之相对的是“带头结点的单链表”，它有一个恒为空的头节点，真正的数据从头节点的next开始。有了这个空头节点，插入和删除操作就不用特判“是否为第一个节点”，代码更统一，有的教科书和嵌入式系统特别偏爱这种设计。

本题中我们使用的虚拟头节点，思路和带头结点的链表异曲同工：用一个占位节点吸收所有特判。区别在于带头结点的头节点属于链表结构的一部分，而虚拟头节点只是算法过程中临时存在的辅助设施。理解这两个概念后，很多链表题的实现你都会豁然开朗。

6.4 关于力扣刷题方式的一点心得

结合这道题聊聊怎么刷题更高效。我不建议按题目编号顺序硬刷，而是按专题刷。链表专题就集中做二十道链表题，做完你自然会归纳出虚拟头节点、双指针、快慢指针等套路，这些套路在下一类题里还能复用。

每一道题做完后，问自己三个问题：能不能用另一种思路解？能不能把输入条件改一下（比如两个链表变成K个）？解法的时间空间复杂度还能优化吗？这三个问题就是“力扣刷题攻略”里最核心的理念，比单纯堆题量有用得多。第二遍做这道题时，直接尝试手写递归版并解释递归模型，能写清楚才算真会。

顺带一提，本题严格来说不涉及循环链表的操作，但循环单链表是链表知识网中绕不开的一部分。它的特点是尾节点的next指向头节点，遍历结束条件从“判断是否为null”变成“判断是否回到头节点”。理解了普通单链表，再去看循环链表就会觉得它只是把尾巴接回了头而已。

最后再分享一点个人的使用体会

这道题我前前后后写过很多遍，迭代版已经变成肌肉记忆。每次带新同学刷题，我都建议他们把这段代码拆成三步来记忆：先建虚拟头节点，然后双指针比较拼接，最后接上剩余链表。三步对应三个容易出错的关键点，想清楚再动手，基本一次就能写对。

如果你刚开始刷链表题，不妨把这道题当成一块试金石：先不看答案写迭代版，写完后对照本文检查边界处理；再不看答案写递归版，写完后用自己的话说清楚递归的子问题是什么。两道代码、一套用例、一段总结，做完这些，链表的基础就站稳了一大半。后续再遇到合并K个链表、链表排序、两两交换节点，你会发现它们都带着这道21题的影子。