LeetCode 21合并两个有序链表：迭代与递归的链表基本功修炼

做了这么多年算法题如果要我挑一道最能检验链表基本功的题目LeetCode 21“合并两个有序链表”绝对排在前三。这道题在面试里出现的频率极高——字节、微软、亚马逊都把它当基础题来考而它之所以经典是因为它同时考察了你对链表节点操作、指针移动、边界条件处理这三项核心能力的掌握程度。很多新手在刷这道题时会觉得“思路很简单”但一写代码就各种报错要么是空指针异常要么是链表成环归根结底是对链表的操作细节没有形成肌肉记忆。这篇文章我会把这道题拆开揉碎了讲清楚从最直观的迭代解法到进阶的递归写法从边界条件的处理到本地调试技巧再延伸到合并K个有序链表、链表排序等一整个系列的相关题目帮你把链表这个知识模块一次性打通。不管你是刚接触算法的在校学生还是准备跳槽的工程师这篇文章都值得你收藏细读。1. 这道题到底在考什么——问题拆解与链表基本功1.1 题目描述还原与输入输出分析先还原一下题目本身。LeetCode 21的原题描述是将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。输入是两个已排序的单链表头节点list1和list2输出是合并后的链表头节点。举例来说输入1 - 2 - 41 - 3 - 4输出1 - 1 - 2 - 3 - 4 - 4有些版本的题目会给出多组测试用例包括空链表的情况比如输入[]和[0]输出应该是[0]。这个“空链表”的测试用例恰恰是很多新手第一次提交时挂掉的地方。这道题本身的数据结构定义通常如下以C为例struct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };注意看这个构造函数的重载第一个是默认构造第二个是只给值的构造第三个是值和下一个节点一起给的构造。在本地写测试代码时ListNode(0)和ListNode(0, nullptr)的区别你要心里有数前者是标准用法。1.2 为什么说这道题是链表操作的基础模型链表和数组最大的区别在于数组是连续内存空间通过下标可以O(1)随机访问链表是离散内存空间每个节点里存着一个指向下一个节点的指针或引用只能从头节点开始逐个遍历。这个区别意味着两件事第一链表不支持随机访问你无法像数组那样通过arr[mid]直接跳到中间节点第二链表的插入和删除操作不需要搬动其他元素只需要修改指针指向时间复杂度是O(1)——前提是你已经拿到了目标位置的前驱节点。合并两个有序链表本质上就是一个“反复比较、不断拼接”的过程每次从两个链表的当前节点中挑出较小的那个接到结果链表的尾部然后移动对应链表的指针继续比较。这个过程同时考验了你的指针操作能力和循环终止条件的把控能力是后续做链表排序、链表相交等复杂题目的基础模型。1.3 核心概念节点、指针、遍历在动手写代码之前有三个核心概念必须彻底搞清楚节点链表的基本单元包含数据域val和指针域next。节点本身是一个对象在堆上分配内存。头节点链表的入口。这里要区分两个概念一个是真正的第一个数据节点题目给的list1、list2另一个是“虚拟头节点”dummy node后者是我们自己创建的辅助节点目的是简化边界处理。这个技巧后面会重点讲。遍历通过cur cur-next不断移动工作指针直到cur nullptr为止。尤其要注意的是在C里ListNode*是指针类型指针变量存的是内存地址。当你执行p p-next时你做的是“让p指向下一个节点的内存地址”而不是在修改链表结构。很多初学者的困惑就出在这里分不清“移动指针”和“修改节点的next字段”是两件完全不同的事。提示区分“移动工作指针”和“修改节点链接关系”是理解链表操作的关键。前者是cur cur-next后者是cur-next newNode一个是改变指针变量自身的指向一个是改变当前节点的next字段。2. 先从最直观的思路说起——迭代法的完整推导2.1 双指针合并的核心逻辑最直觉的做法就是双指针迭代。维护两个指针p1和p2分别指向list1和list2的当前节点再维护一个结果链表的尾指针tail。每次比较p1-val和p2-val把较小的那个节点接到结果链表尾部并让对应指针前进一步。这个过程用生活中的例子类比就很形象想象你在整理两摞已经按身高排好队的扑克牌每次从两摞牌的顶部各抽一张比较大小把较小的那张放进第三摞。重复这个动作直到某一摞空了再把另一摞剩下的牌全部倒进第三摞。关键问题来了结果链表最初是空的你如何优雅地处理“第一个节点”的插入如果你单独判断tail nullptr代码会变得啰嗦。这时候虚拟头节点就派上用场了。2.2 虚拟头节点的妙用虚拟头节点dummy node是一个不存储有效数据的辅助节点它作为结果链表的前置占位符存在。有了它你就不需要特判“结果链表是否为空”的情况统一用tail-next 较小节点; tail tail-next;这种操作即可。ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy(0); // 虚拟头节点栈上创建即可 ListNode* tail dummy; // 尾指针指向虚拟头节点 ListNode* p1 list1; ListNode* p2 list2; while (p1 ! nullptr p2 ! nullptr) { if (p1-val p2-val) { tail-next p1; p1 p1-next; } else { tail-next p2; p2 p2-next; } tail tail-next; } // 处理剩余部分 if (p1 ! nullptr) { tail-next p1; } if (p2 ! nullptr) { tail-next p2; } return dummy.next; // 跳过虚拟头节点返回真正的头节点 }有两点需要特别说明。第一ListNode dummy(0)是在栈上创建了一个有名字的节点对象dummy取它的地址这样就不需要new避免了手动内存管理。第二合并过程中我们直接使用了原链表的节点没有创建任何新节点这保证了空间复杂度是O(1)。2.3 循环结束后的收尾处理循环结束后最多还有一条链表没有遍历完。此时不需要再逐个比较了直接把剩余链表的头节点接到结果链表尾部即可。这也是链表操作里一个非常实用的技巧当某条链表为空时另一条链表剩余的部分天然有序直接整体拼接。为什么可以这样因为链表本身就是通过指针串联的把整段剩余链表接上去就相当于把这一段的所有节点一次性纳入结果链表。这一个操作替代了剩余所有节点的遍历工作时间效率上非常划算。在C代码里我上面用的是两个独立的if来判断哪条链表还有剩余。更简洁的写法是用三目运算符tail-next (p1 ! nullptr) ? p1 : p2;两种写法效果完全一样看个人喜好。不过我个人习惯用两个if因为这样逻辑更直观面试时也更容易解释清楚。2.4 代码实现与复杂度分析时间复杂度是O(m n)其中m和n分别是两条链表的长度。本质上每个节点最多被比较一次、被拼接一次整体是线性的。空间复杂度是O(1)因为我们只用了几个指针变量没有申请额外的内存空间栈上dummy所占的内存可以忽略不计。这里要回应很多人的一个疑问既然没有创建新节点为什么返回值是dummy.next而不是dummy本身因为dummy是我们自己造的辅助节点不是原始链表的一部分。返回它的next才能跳过这个占位符得到真正合并后的链表头节点。如果使用Python代码结构几乎一致只是语法不同def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0) tail dummy p1, p2 list1, list2 while p1 and p2: if p1.val p2.val: tail.next p1 p1 p1.next else: tail.next p2 p2 p2.next tail tail.next tail.next p1 if p1 else p2 return dummy.nextPython版本需要注意的一点是ListNode(0)是在堆上创建对象dummy本身就是一个对象引用与C的指针在语义上有所差别但用法完全对应。3. 换个角度再看一遍——递归解法的本质3.1 递归思路的形成过程迭代法写完后不妨再想一想这个问题能不能用递归解决答案是肯定的而且递归写法代码极短。递归解法的核心思路是比较两个头节点的值较小的那个节点作为新链表的头节点然后递归地合并它剩余的链表和另一个链表。说白了就是“把当前最小的节点摘出来剩下的交给递归去处理”。这个思路的形成过程其实很自然。你手上有两个链表的头节点你一定能确定合并后链表的头节点是两者中较小的那个。确定头节点之后问题就变成了“合并两个链表其中一个链表的头节点已经确定了位置需要合并的是它后面的部分和另一个完整链表”——这不就是原问题的缩小版吗3.2 递归代码与调用过程解析ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if (list1 nullptr) return list2; if (list2 nullptr) return list1; if (list1-val list2-val) { list1-next mergeTwoLists(list1-next, list2); return list1; } else { list2-next mergeTwoLists(list1, list2-next); return list2; } }如果使用Pythondef 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为空返回list2list2为空返回list1。这两个条件必须写在最前面否则递归会无限进行下去。理解递归调用的关键是要记住“递归是自顶向下分解、自底向上构建”的过程。拿[1,2,4]和[1,3,4]举例第一层比较1和1list1-val list2-val成立所以链表1的头节点成为合并链表头节点接着递归处理[2,4]和[1,3,4]第二层比较2和1链表2的头节点成为次节点接着递归处理[2,4]和[3,4]依次类推直到某个链表为空递归开始回溯层层返回结果最终完成整个链表的拼接值得注意的是递归解法也在原地修改链表节点的next指针空间复杂度O(1)但时间复杂度上递归调用栈的开销使得空间复杂度实际为O(m n)——因为递归深度最多是两条链表的总长度。这是递归解法唯一的短板。3.3 递归 vs 迭代该选哪个维度迭代法递归法代码长度略长极短空间复杂度O(1)O(mn)递归栈理解难度直观需要对递归有理解面试建议推荐首选可以作为进阶展示以我的实际面试经验来说如果面试官没有特别要求建议先说迭代法因为思路清晰、不容易出错。如果面试官追问“还能怎么优化”或者“有没有其他思路”再补上递归解法展示你对问题的多角度理解。两个都能答上来绝对是加分项。注意在面试过程中不要在开场就写递归解法。虽然代码很短但如果面试官突然问你“递归的最坏空间复杂度是多少”而你没答上来会给面试结果减分。先讲迭代法再补充递归解法是稳中求胜的策略。4. 刷题中常见的坑和调试技巧4.1 空链表处理的正确姿势空链表是这道题最容易踩的坑没有之一。很多人写完代码满心欢喜地提交结果在[]和[0]这样的测试用例上栽了跟头。错误示例ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy(0); ListNode* tail dummy; while (list1 || list2) { // 错误两个链表都可能为空 if (list1-val list2-val) { // 如果list2为空这里越界访问 // ... } } }这段代码的问题在于循环条件用了||但循环体里没有判断单个链表是否为空。当list1不为空而list2为空时list2-val就会访问空指针导致运行时错误。正确做法是在循环开始前处理好空链表的情况或者把循环条件写成while (list1 ! nullptr list2 ! nullptr)循环结束后再处理剩余的链表。这两种方式本质上是一样的核心思路是“谁空了就处理谁”。4.2 指针移动的常见错误这个题还有一个高频错误就是“先改链接再移动指针”的顺序搞反了。看一下这个错误版本while (p1 p2) { if (p1-val p2-val) { tail-next p1; tail tail-next; p1 p1-next; // 正确顺序先接链再移动p1 } // ... }有些新手会把tail-next p1;和p1 p1-next;的顺序写成tail-next p1; p1 p1-next; // 如果先执行这一步p1已经指向下一个节点了 tail tail-next;这种写法会导致什么后果如果先执行p1 p1-next再执行tail tail-next那么tail会移动到原来p1指向的位置但此时p1已经指向了下一个节点。看起来好像没问题实际上tail指向的节点仍然被正确链接到了结果链表。但是这里有个隐患如果你在p1 p1-next之后又做了tail-next p1就会把链表搞乱。正确的操作顺序是先建立链接关系tail-next p1再移动工作指针p1 p1-nexttail tail-next。这里有个通用的经验法则先修改链接再移动指针。除非是删除操作否则“断开”和“移动”的顺序一定要心里有数。4.3 本地调试链表题的方法力扣题库内置的执行和提交测试非常方便但它不会告诉你详细的运行时信息。如果你在本地IDE调试链表题有几个小技巧能帮你快速定位问题。第一建议为链表写一个辅助的打印函数void printList(ListNode* head) { while (head ! nullptr) { std::cout head-val - ; head head-next; } std::cout nullptr std::endl; }每次操作后调用这个函数你就能直观地看到链表结构的变化。第二建议把测试用例写成一个数组到链表的转换函数ListNode* createList(std::initializer_listint vals) { ListNode dummy(0); ListNode* tail dummy; for (int val : vals) { tail-next new ListNode(val); tail tail-next; } return dummy.next; }有了这两个辅助函数你就能在本地快速搭建测试环境不用每改一次代码就跑到力扣上提交一次。第三如果你常写C链表题建议在调试运行时加上地址输出std::cout node std::endl确认节点地址是否符合预期。这个技巧在处理“链表成环”类问题时尤其有效。5. 从这一题出发的扩展玩法5.1 进阶挑战合并K个有序链表严格来说LeetCode 23“合并K个有序链表”是21题的直接升级版本考察点是“如何高效地合并多条有序链表”。如果只是简单地两两合并时间复杂度是O(kn)其中k是链表数量n是每条链表的平均长度。更高效的做法是使用优先队列最小堆把时间复杂度降到O(nlog(k))。核心思路是这样的维护一个小顶堆把所有链表的头节点放进去。每次从堆里弹出最小的节点把它接到结果链表尾部然后把这个节点的下一个节点如果存在压入堆中。重复这个过程直到堆为空。很多刷题指南都把这两道题放在一起练习因为21题练的是“合并两个”23题练的是“合并多个”一个循序渐进的过程。如果你21题做得熟练23题就只需要学会用堆来优化多路归并即可。5.2 链表排序、链表相交等衍生问题合并两个有序链表还有几个经典的衍生问题排序链表LeetCode 148在O(n*log(n))时间内排序链表。标准解法是利用归并排序的思想——先把链表从中间拆成两半分别排序再调用合并两个有序链表的逻辑。链表相交LeetCode 160 / 3898判断两个链表是否相交并找到相交节点。这个题目表面上是双指针问题但如果你把“相交”理解为“从某个节点开始后续完全一致”你甚至可以用合并的思路来验证这一点。回文链表LeetCode 234判断链表是否为回文结构。解法是先找到中点把后半段翻转然后比较前后两段——又用上了“拆分比较”的思想。可以说合并两个有序链表所涉及的“取较小节点、拼接、移动指针”的操作模式几乎是所有链表题的基础操作模板。你把它练熟了后面一系列看似花哨的题目其实都是换汤不换药。5.3 在刷题路线里的位置在大多数经典的刷题路线里链表模块的顺序都是“反转链表 → 合并有序链表 → 链表环检测 → 链表相交 → 排序链表”。21题正好处在“反转链表”LeetCode 206之后因为它要求你已经掌握基本的指针移动和节点拼接但不需要太多高级技巧。所以你会看到无论哪个刷题清单包括LeetCode热门100题21题都是链表模块的开篇之作或准开篇之作。这道题还会作为其他题目的子步骤出现。比如在某些版本的“两数相加”LeetCode 2题解里会先把两个加数链表对齐再逐位相加又比如在“排序链表”里归并的核心子过程就是合并两个有序链表。也就是说你每牢固掌握一道基础题后面潜在需要它的题目至少有4到5道。从我个人的经验来说这道题我已经在不同场合写了很多遍——从最早刚学数据结构时的课堂作业到面试现场的手撕代码再到后来给团队新人做Code Review时讲解。每一次重写我都觉得链表这个数据结构通过这道题被诠释得特别透彻。它不像动态规划那样需要天马行空的想象力也不像一些偏门技巧那样脱离日常开发它就是把链表最核心的操作——比较、拼接、移动、收尾——揉在一起用最直接的方式考验你的基础扎实度。如果你正在准备面试我的建议是先把这个题目的迭代法和递归法都写到条件反射的程度闭着眼睛都能写对然后动手实现合并K个有序链表最后刷到排序链表时回头看看这道题你会发现自己对整个链表模块的理解已经不在一个层次了。刷题这件事没有太多捷径但把每一道有代表性的题目真正吃透就是最踏实的路。