1. 题目到底在说什么，以及为什么它这么重要
“合并两个有序链表”这题，力扣编号21，难度标注是“简单”。但如果你在面试前只把简单题当热身题刷一遍就翻篇，那可能会错过一个非常重要的信号——这道题是链表类问题里为数不多的“母题”之一，很多中等甚至困难级别的链表题，最后都绕不开合并有序链表这个核心动作。
先说题目本身，它要求我们把两个已经按非递减顺序排列的链表合并成一个新的有序链表，并且新链表也要保持非递减。这里的“非递减”意味着允许相等值存在，比如[1,2,4]和[1,3,4]合并后是[1,1,2,3,4,4]。
在仔细拆分之前，先确认几个关键问题，这些都是刷题时最容易踩坑的点：
- 链表结构：力扣的链表是单向链表，每个节点只有一个
next指针。这是前提，不要混淆成双向链表。 - 是否允许修改原链表：题目没说不让改，常规解法中，迭代法会复用原有节点来拼接新链表，而不是新建节点。除非题目明确要求“返回新链表”，一般面试中复用原节点是允许且高效的。
- 空链表情况：如果其中一个链表为空，直接返回另一个链表。这个边界很多人第一次写容易漏掉。
这题的重要性在于：它考察的“双指针不断挑选较小值”的思路，在后续很多题目里都会用到，比如“合并K个升序链表”“合并两个有序数组”“寻找两个有序数组的中位数”等。把这些基础解法吃透，后面遇到变体就不会慌。
2. 合并有序链表的完整思路拆解
2.1 迭代法：双指针 + 哑节点，最容易上手的方案
迭代法是这题的主流解法，也是面试中最推荐的写法。核心思路很朴素：两个链表各用一个指针（节点引用）从头部开始遍历，每次比较两个指针指向的节点值，把较小的节点接到结果链表的尾部，然后移动该指针向后一位，直到其中一个链表走完，剩下的直接拼接。
听上去很简单，但实际写代码时有一个非常关键的设计——哑节点（dummy node）。
为什么要用哑节点？因为新链表的头节点在开始遍历之前是不确定的。如果你直接声明一个head = None，那每次拼接节点时，你需要额外判断“当前结果链表是否为空”，为空则赋值给头节点，不为空则接在尾部。这个判断本身不复杂，但它会让代码分支变多，容易出错，也影响可读性。
哑节点的做法是：先创建一个不存储实际数据的节点dummy，让tail指针从它开始，后续所有新节点都接在tail后面，最后返回dummy.next作为真正的头节点。这样整个拼接过程不需要任何“是否首次拼接”的判断，代码更干净，也更符合工程上的“哨兵节点”思想。
2.2 递归法：代码极短，但需要想清楚递归关系
递归解法代码非常简短，很多题解会把递归放在第二种方案里，我个人的看法是：面试时优先写迭代，但递归也要能讲清楚。因为有时候面试官会刻意让你用递归再写一遍，考察你对递归终止条件和递推关系的理解程度。
递归的思路是：比较当前两个链表头节点的值，较小的那个作为合并结果的当前节点，然后它的next指向“剩下部分合并后的结果”。
用伪代码表达就是：
if l1.val < l2.val: l1.next = merge(l1.next, l2) return l1 else: l2.next = merge(l1, l2.next) return l2递归终止条件就是两个链表中有一个为空，此时返回另一个链表。
这个解法的优点是代码篇幅极短，逻辑直观；缺点是递归调用会占用系统栈空间，链表很长时可能导致栈溢出，力扣的实际测试数据范围内问题不大，但如果你在工程环境中合并超长链表，递归不是首选。
2.3 对比：迭代还是递归，面试现场怎么选
如果是日常刷题，我建议两种都写一遍，因为它们的思维方式完全不同，都能加深对链表的理解。但在面试现场，我的建议是先写迭代法，原因有三个：
- 迭代法空间复杂度为
O(1)，递归法为O(n)，虽然力扣上两种写法的空间复杂度标注不同，但面试官通常会追问空间消耗的原因； - 迭代法更贴近实际工程中操作链表的习惯，不容易因为递归深度问题被质疑；
- 迭代法的可控性强，即使面试官后续提出“合并K个有序链表”之类的变体，迭代思路也能平滑过渡到最小堆或分治法。
当然，如果你递归掌握得特别熟，先讲递归再补迭代也可以，关键是逻辑清晰，代码不能有语法错误或边界遗漏。
3. 核心代码实现与逐行精讲
3.1 Python实现：迭代法
先看完整代码，再逐行解释：
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: dummy = ListNode() tail = dummy while list1 and list2: if list1.val <= list2.val: tail.next = list1 list1 = list1.next else: tail.next = list2 list2 = list2.next tail = tail.next tail.next = list1 if list1 else list2 return dummy.next各关键行的用意：
dummy = ListNode()：创建哑节点，它的值我们不在意，只是为了有一个确定的起始点，方便后续不断拼接。tail = dummy：尾指针，始终指向当前结果链表的最后一个节点，新的节点都接在tail.next。while list1 and list2：两个链表都不为空才进入循环。一旦某个链表为空，循环退出。- 比较逻辑：
<=和<在这个题里不影响最终结果，因为两个有序链表合并时，相等情况下取哪一个在值上等价，但保持<=更稳定。 - 移动指针：把较小节点接走后，对应的链表指针向后移动一位，
tail也移动到新节点。 - 尾部拼接：循环结束后，剩下未遍历完的链表整体接到
tail.next，因为剩下的节点已经有序，直接拼接即可。 - 返回
dummy.next：因为dummy是哨兵节点，真正的结果头节点是它的下一个。
3.2 Python实现：递归法
递归写法：
class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: if not list1: return list2 if not list2: return list1 if list1.val <= list2.val: list1.next = self.mergeTwoLists(list1.next, list2) return list1 else: list2.next = self.mergeTwoLists(list1, list2.next) return list2这里注意一个细节：递归函数内部不断修改list1.next或list2.next，本质上是把原链表的节点重新组织成新链表，并不会创建新节点，所以在空间复杂度上，递归栈空间才是主要开销。
3.3 复杂度分析，为什么迭代法是 O(1) 空间
先说时间复杂度：无论是迭代还是递归，每个节点最多被比较一次、被拼接一次，所以时间复杂度是O(m + n)，其中m和n分别是两条链表的长度。
空间复杂度方面：
- 迭代法只使用了
dummy和tail两个额外指针，不随链表长度增长，是O(1)。 - 递归法在每一层递归调用时，会把当前状态压入系统栈，递归深度等于两条链表的总长度，所以空间复杂度是
O(m + n)。
这个差异是面试中比较容易追问的点。面试官可能会问你：“为什么递归解法空间复杂度不是 O(1)？”你只需回答：因为每次递归调用都会占用栈帧，链表有多个节点，就会有多层调用栈。
4. 刷题过程中的常见错误与排查技巧
4.1 边缘条件漏处理：空链表直接返回另一个
最经典的错误：没有处理list1或list2为空的情况。虽然大多数测试用例中都有非空链表，但力扣的测试用例一定会包含空输入。如果漏掉这个判断，代码在遇到空链表时可能报AttributeError: 'NoneType' object has no attribute 'val'。
这类错误很容易排除：在代码开头显式处理空链表情况，或者在写while循环时确保条件覆盖到了指针为空的场景。建议每次写链表题，开头先花三秒钟问自己：输入为空时我的代码跑得通吗？
4.2 返回了 dummy 而不是 dummy.next
另一个常见的低级错误，是最后return dummy。这样会把哑节点本身也返回出去，导致结果链表头部多了一个值为0（或默认值）的节点，判题结果一定不对。
解决办法：最后务必return dummy.next。如果你看到输出结果最前面多了一个奇怪的值，基本就是这个问题。
4.3 循环结束后忘记拼接剩余链表
遍历完其中一条链表后，另一条链表可能还有剩余节点，此时需要直接把剩余链表整体接到tail.next。如果漏掉这一步，合并结果会丢失后半部分数据。
这类错误在力扣上通常表现为：执行结果比预期输出短一大截。排查方法也很简单，检查while循环退出后是否处理了两条链表的剩余部分。
4.4 递归时忘记设置终止条件
递归写法虽然简洁，但终止条件如果不完整，容易死循环或栈溢出。比如只写if not list1: return list2，却漏了if not list2: return list1，在极端输入下就可能出现无限递归。
这类问题不太容易直接肉眼看出来，建议写完递归后，自己手动拿两个短链表在纸上走一遍，或者直接跑力扣测试用例，用报错信息来定位。
4.5 一个经验技巧：先画图，再动手
链表类问题特别适合画图理解。哪怕只是画两个指针的移动方向，也会比直接在脑子里空想要可靠得多。我推荐的流程是：先画出链表的初始状态，标注list1、list2、dummy、tail四个指针的位置，然后模拟三五步移动，最后再落笔写代码。这样写出来的代码，边界情况基本一次通过。
5. 这题的三种进阶变体，以及它们与本题的关系
合并两个有序链表是很多后续问题的基石。我在这里补充几个常见的变体，它们不仅出现在面试中，也经常作为力扣的进阶题出现。理解了本题，下面这几类题会更容易上手。
5.1 合并K个升序链表
力扣第23题“合并K个升序链表”，本质上就是本题的多次推广。如果你只有两个链表，用上面的方法就够了；但如果K很大，两两合并会导致大量重复遍历。常见的优化思路有两个：
- 最小堆法：把每个链表的当前头节点放入最小堆，每次弹出最小值，然后把这个节点的
next放入堆中，循环直到堆为空。时间复杂度是O(N log K)，其中N是所有节点总数，K是链表个数。 - 分治法：把
K个链表两两合并，进行log K轮，每轮都调用本题的mergeTwoLists，总时间复杂度同样是O(N log K)。
如果你把本题的迭代法掌握熟练，分治法的代码实现只是多一层递归或循环，难度并不大。
5.2 合并两个有序数组
力扣第88题“合并两个有序数组”，题目要求把两个有序数组合并到第一个数组中，且不能额外使用太多辅助空间。它的核心思路和链表版很像，只不过数组需要从后往前填，避免覆盖未处理的元素。为什么从后往前？因为题目要求原地修改nums1，如果从前往后，nums1的前面元素可能会被覆盖掉，导致数据丢失。这也是链表和数组在物理结构上的差异带来的实现区别。
5.3 单向链表排序
链表排序的常见方案是归并排序的链表版本，其中就会用到“合并两个有序链表”这一步。力扣第148题“排序链表”是典型代表。它的过程是：先用快慢指针找到链表中点，分割成左右两半，递归排序，最后用mergeTwoLists合并。所以如果你能把本题的合并逻辑写顺，链表归并排序的“合并环节”对你来说就没有任何障碍。
这些变体都指向同一个训练目标：识别“把两个有序序列合并成一个有序序列”这个子问题，并快速把它解出来。这也是为什么我强调，不要把21题当成一道孤立题目来刷，而是把它当成一组相关题目的基础模块。
6. 刷题顺序建议：21题该放在什么位置刷
如果你正在按照“力扣刷题顺序”来规划，这里我给一个实际操作中的建议：链表类的入门顺序，第21题排在很前面，但它不是第一题，也不是最后一题。
我比较推荐的一个链条顺序是：
- 第206题 反转链表：先理解链表指针怎么改变方向；
- 第21题 合并两个有序链表：理解双指针遍历和哑节点；
- 第876题 链表的中间结点：理解快慢指针；
- 第19题 删除链表的倒数第N个结点：理解哨兵节点和双指针的配合；
- 第148题 排序链表：综合运用找中点、递归、合并。
这样排的好处是：每一步都在前一步的基础上增加一个新的概念。第21题承接了“双指针”“哑节点”两个核心概念，又为后面的归并排序第148题做铺垫，不会上来就搞太复杂。
在刷题时间安排上，如果你每天只能抽出一小时刷题，不要把一小时全部用来磨一道难题。更高效的做法是：10分钟审题+想思路，30分钟写代码和调试，20分钟看最优题解并写总结笔记。对于第21题这个难度等级，第一遍大概20到30分钟就能完成，第二遍复习时5到10分钟就能写出来。
7. 面试中的答题节奏与追问应对
如果你是在面试准备阶段，直接刷这题时，除了把代码写对，还要有一套“答题节奏”。我根据自己的实际面试经验，分享一个比较稳妥的分步节奏。
7.1 先确认输入与边界，再动笔
面试时不要一上来就写代码，先向面试官确认几个问题：
- “链表节点定义是单链表吗？”（虽然题目通常会说明，但确认一下没有坏处）；
- “原链表节点可以被修改吗？”（大多数情况允许，但确认可以避免事后返工）；
- “如果两个链表都有相同值的节点，选择哪一个先拼接都可以吗？”
这一步不是多余，而是在给面试官传达“我习惯先厘清需求再动手”的工程素养。大多数面试官不会觉得烦，反而会对你印象加一点分。
7.2 讲清楚思路，再写迭代法
确认完需求后，用一两句话讲清楚思路：“我用一个哑节点作为结果链表的哨兵，tail 指向结果链表的尾部，然后双指针遍历两个链表，每次把值较小的节点接到 tail 后面，最后把剩余部分整体接上，时间复杂度 O(m+n)，空间复杂度 O(1)。”
然后直接开始写迭代法的代码。写的时候注意变量命名清晰，临时指针命名建议用p1、p2或list1、list2这种直观名字，不要用a、b、cur这种含义不清的名称。
7.3 写完后主动测试用例，不要等面试官来追问
代码写完并不是结束。主动说：“我跑几个测试用例验证一下。”然后可以选下面几组：
list1 = [1,2,4]，list2 = [1,3,4]，合并后为[1,1,2,3,4,4]；list1 = []，list2 = [0]，合并后为[0]；- 两个链表都为空，合并后为空。
这比面试官追问“边界情况考虑了吗”要好得多，是展示你测试意识的好机会。
7.4 如果被追问递归写法，怎么答
面试官如果抛出“你能用递归写一下吗”，你可以简短说明：递归的核心是把当前节点和剩余子问题的合并结果连接起来。然后当面写出递归版，再对比分析一下空间复杂度的差异。这种追问一般是想看你能不能从不同角度理解同一个问题，能答出来的话这一项分数基本就到手了。
8. 实操中我踩过的一些坑和心得
聊一些比较贴近真实刷题感受的东西。
第一，哑节点命名不要写head。我第一次写这题时，把dummy命名成了head，结果后面逻辑越写越绕，因为“结果链表的头”和“当前拼接的位置”在语义上混淆了。后来我改成dummy + tail的命名，整个逻辑一下子清晰很多。命名对理解代码的影响，在实际写题时比想象中更大。
第二，别忽略 Python 类型注解。在力扣的代码模板里，函数签名的参数类型和返回值类型已经标注好了。建议保留这些类型注解，不要删掉，这样在本地编辑器写代码时也能借助静态检查提前发现类型错误。
第三，递归法虽然短，但最好不要在没画图的情况下直接写。我在给朋友讲这题时发现，很多新手看递归代码觉得“很神奇”，但自己写时很难一次写对。我的建议是：先用迭代法过一遍，再对照递归法在纸上画两个链表三五个节点的合并过程，能画出来，递归代码自然就能写出来了。
第四，多写一版不利用哑节点的迭代法，对比一下差别。这不是必须写的，但如果你做一次这种对比，你会真正理解哑节点为什么能简化代码。不利用哑节点时，你可能需要这样写：
class Solution: def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]: 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 tail = head while list1 and list2: if list1.val <= list2.val: tail.next = list1 list1 = list1.next else: tail.next = list2 list2 = list2.next tail = tail.next tail.next = list1 if list1 else list2 return head对比可以发现，不使用哑节点时，开头必须先处理“谁当新链表的头”的问题，逻辑多了一个分支。使用哑节点后，这个分支被统一到循环里的拼接逻辑中，不需要额外处理。这种对比做得多了，你对“哨兵节点”这种设计模式的认识会更加深入。
第五，最后一个心得，关于“写题解笔记”。如果你在力扣刷题后有整理笔记的习惯，不要只贴一份提交通过的代码。更好的笔记格式是：题目链接、自己的第一版解法、哪里有 bug、优化后的最终解法、时间空间复杂度、能联想到的相似题目。这样一份笔记，过一个月你再回看时，价值远超一份代码本身。本文的核心代码和排查清单，你也可以直接用这种方式整理进自己的刷题笔记里。
