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

力扣第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(mn)空间是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 一个都不能少的测试用例清单刷题不能只求“提交通过”你还需要设计一套完整的测试用例来覆盖所有场景。下面这些用例我在本地调试时必测建议你也照这个清单过一遍。用例编号输入l1输入l2期望输出验证点1[][][]两个空链表2[][1,2,3][1,2,3]其中一个为空3[1,2][1,2][1,1,2,2]值完全相同4[1,5,9][2,3,10][1,2,3,5,9,10]常规交错合并5[2,3,4][1][1,2,3,4]短链表先耗尽6[-5,0,3][-10,-1,4][-10,-5,-1,0,3,4]负数节点值7[1,1,1][1][1,1,1,1]大量重复值很多人只测1和4漏掉负数用例和全相同值用例。负数不重要吗链表节点值范围是[-100, 100]忽略负数值会导致比较逻辑的直觉判断失效。全相同值用例则能检验你的比较符写法是否会导致节点丢失。4.2 本地怎么搭一个链表测试脚手架力扣的在线编辑器已经帮你处理好了链表构造和输出但如果你想在本地跑代码、做更多实验需要自己写两个小工具函数一个用数组构造链表一个把链表打印成数组格式。以Python为例class ListNode: def __init__(self, val0, nextNone): 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(mn)。这是一个典型的“时间与空间权衡”问题答案本身不重要关键是你能意识到原链表被修改这个副作用。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题的影子。