1. 这题为什么值得反复看从面试价值到算法内核力扣第21题合并两个有序链表是我见过出现频率最高的链表类题目没有之一。无论你是刚开始刷题准备校招还是社招跳槽想热热身这道题几乎出现在每一份面试题库里。说句实在话我自己面试别人时也会出这道题因为它在短短十几行代码里浓缩了链表操作中最核心的几个考点指针移动、边界处理、递归思想以及一个容易被忽略但极其重要的技巧——虚拟头节点。合并两个有序链表的题目本身很简单给你两个升序排列的单链表让你把它们合并成一个新的升序链表并返回。不能用额外的数组存储节点必须通过调整节点之间的指针来完成。这意味着你只能在原链表上动手脚不能新建节点。这道题之所以经典恰恰因为它简单不意味着容易写对。很多基础不错的人第一次写能想到思路但一落到代码上就漏洞百出空指针没判、循环边界写错、最后剩下的链表节点没接上。这些错误不是能力问题而是对链表这种数据结构的操作套路还不够熟。把这道题吃透你收获的不只是这一道题的AC而是一整套链表操作的肌肉记忆。我建议你把这道题当作链表系列的第一个里程碑。做懂了它后面再遇到合并K个升序链表力扣23、排序链表力扣148、两两交换链表中的节点力扣24你会明显感觉到基础打得比别人扎实。这篇文章我直接用C来讲从题目分析、迭代解法、递归解法到调试中的坑和拓展思路一次给你讲透。2. 题目精读输入输出的隐藏信息与边界条件2.1 链表结构定义与题目约定先看C里链表节点的标准定义力扣的题目模板已经给你写好了/** * Definition for singly-linked list. * 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) {} * }; */这个结构体有三个构造函数分别对应不传参只传值传值和后继指针三种初始化方式。在合并链表的过程中我们用得最多的是第三个构造函数不过更常见的做法是直接用new ListNode(x)创建节点。注意next指针默认初始化为nullptr在C11及以后的标准里官方推荐用nullptr而不是NULL因为nullptr有明确的指针类型不会跟整型的0产生歧义。题目给的函数签名是class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { } };两个入参list1和list2分别指向两个链表的头节点。注意这里说的是升序链表但力扣的测试数据里其实允许存在相等值的节点比如[1, 3, 5]和[1, 2, 4]合并后得到[1, 1, 2, 3, 4, 5]。判断条件是还是直接影响合并后相等元素的排列但题目不要求保证稳定性所以两种写法都能AC。2.2 边界条件的完整清单很多人在这个题上翻车不是因为合并逻辑不对而是边界条件没处理干净。我把所有可能出现的边界情况列一遍你在写代码之前先在脑子里过一遍两个链表都为空list1 nullptr list2 nullptr这种情况直接返回nullptr。其中一个链表为空另一个非空比如list1 nullptr, list2 ! nullptr那么结果就是list2本身。这一点很多第一次写的人容易忘记合并到最后如果有一条链没走完需要把剩余部分直接接上。一个链表只有一个节点另一个链表很长考察的是循环退出后是否会丢失剩余的节点。两个链表长度悬殊比如list1有100个节点list2只有1个节点前100次比较都在处理list2的节点之后要快速把list1剩余部分全部接上。所有节点的值都相同比如[1, 1, 1]和[1, 1]考验的是和的区别。你可以把上面这些情况当成一组测试用例写完代码后逐一核对。我在面试别人时很多候选人能写出主逻辑但漏了一个链表为空另一个非空的场景。这个边界条件在力扣的判题系统里几乎是必测的漏了就是WA。3. 迭代解法虚拟头节点为什么是这道题的灵魂3.1 不引入虚拟头节点的痛苦需要单独处理头节点先聊聊最朴素的想法。合并两个有序链表的直观做法是用两个指针l1和l2分别指向两个链表的当前节点比较它们的大小把较小者接到新链表的末尾。这个思路人人能想到但落笔时会面临一个麻烦——新链表的头节点是谁如果不引入虚拟头节点你需要在循环之前先比较一次list1-val和list2-val把较小者作为新链表的头节点然后才能进入统一的循环逻辑。这段前置判断代码虽然不难写但它破坏了循环结构的统一性还会带来额外的出错风险万一两个链表都为空你连头节点都没法确定。更麻烦的是后续每一次把节点接到新链表末尾都需要维护一个指向链表尾部的指针tail。当头节点已经确定后tail的初始值是头节点然后随着循环不断往后移。这个逻辑没什么问题但就是写起来啰嗦而且要单独写一个分支。我自己早期刷题时就因为这种写法踩过坑在返回时搞混了head和tail调试了半天才发现。3.2 虚拟头节点的引入与循环不变式虚拟头节点dummy node的出现就是为了消除上面这些麻烦。它的核心思想很简单先new一个不参与结果的哨兵节点让tail一开始就指向这个节点然后在循环里把较小的节点逐个串到tail后面。循环结束后返回dummy-next即可。为什么这个技巧能生效因为虚拟头节点让空链表这个边界情况变得不再特殊即使list1和list2都为空dummy-next也只是nullptr逻辑依然成立。你不再需要前置判断去确定头节点是谁所有的插入操作都在同一个循环里完成。用C写出来是这样的class Solution { public: ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy(0); // 在栈上创建虚拟头节点避免手动释放 ListNode* tail dummy; // tail 始终指向结果链表的最后一个节点 while (list1 ! nullptr list2 ! nullptr) { if (list1-val list2-val) { tail-next list1; list1 list1-next; } else { tail-next list2; list2 list2-next; } tail tail-next; // tail 往后移动一位 } // 循环结束后最多还剩一条链表未走完直接拼接 tail-next (list1 ! nullptr) ? list1 : list2; return dummy.next; } };这里我直接在栈上创建了一个ListNode对象ListNode dummy(0);。这样做的优势是不需要手动delete函数结束时自动销毁不会有内存泄漏。有些资料里会写ListNode* dummy new ListNode(0);这种方式在力扣的判题环境里也能通过但如果你在自己的工程代码里这么写而忘了delete dummy就是一次内存泄漏。更推荐栈上创建的方式。循环里的逻辑用一个专业一点的词叫循环不变式每次循环开始时tail指向结果链表的最后一个节点list1和list2分别指向两个输入链表中还未合并的第一个节点。这个不变式在每一轮迭代后依然成立所以循环结束后所有节点都已经按非递减顺序挂到了tail后面。理解了这个不变式你就能解释为什么循环条件是while (list1 list2)而不是别的写法一旦某条链为空说明它已经没有节点可以参与了剩下的工作只是把另一条链的剩余部分整体接上。3.3 迭代解法的时间与空间复杂度时间复杂度是O(mn)其中m和n分别是两个链表的长度。因为这本质上是一次归并过程的比较次数每轮循环比较一次、移动一次指针循环次数最多是mn。空间复杂度是O(1)因为你只用了固定的几个指针变量没有使用与链表长度相关的额外空间。虚拟头节点虽然在栈上占了一个ListNode的空间但它是一个常量大小的空间不随输入规模增长所以不计入线性空间复杂度。这里有一个值得反复体会的细节合并过程中所有节点都是从原链表上拆下来再挂到新链表上没有创建任何新节点。这就是题面里那句必须调整指针的含义。如果你面试时脑子一热用while遍历两个链表、把值存到数组里再排序、最后用new ListNode重新建链表虽然结果一样但时间复杂度会变成O((mn)log(mn))空间也多了O(mn)完全跑偏了。4. 递归解法三行代码背后的执行逻辑4.1 递归解法的核心写法如果你觉得迭代解法已经够简洁了那递归解法会让你眼前一亮。完整的代码如下class Solution { public: 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; } } };你看主体逻辑只有三行。这段代码的运行过程可以这样理解不断比较两个链表头节点的值把较小者选出来让它指向剩余部分合并后的结果。这个剩余部分的求解就是一次递归调用。4.2 递归的每一步发生了什么我用一个具体的例子走一遍。假设list1 [1, 3, 5]list2 [2, 4, 6]。第一次调用1 2所以选择节点1递归调用mergeTwoLists([3, 5], [2, 4, 6])然后把返回的链头接在节点1后面最终返回节点1。第二次调用3 2所以选择节点2递归调用mergeTwoLists([3, 5], [4, 6])接在节点2后面返回节点2。第三次调用3 4选择节点3递归调用mergeTwoLists([5], [4, 6])返回节点3。第四次调用5 4选择节点4递归调用mergeTwoLists([5], [6])返回节点4。第五次调用5 6选择节点5递归调用mergeTwoLists([], [6])返回节点5。第六次调用list1为空直接返回[6]。然后递归开始逐层返回节点5接到节点4后面节点4接到节点3后面节点3接到节点2后面节点2接到节点1后面。最终得到[1, 2, 3, 4, 5, 6]。注意这里的关键点在于递归调用返回的是剩余部分合并后的头节点而当前层只需要把选中的节点接上去并返回自己。这其实是一种从后往前构建链表的过程跟迭代的从前往后方向相反但结果完全一致。4.3 递归解法的适用边界与栈溢出风险递归解法代码简洁面试时写出来会显得思路很清晰但它有一个不可忽视的问题递归深度等于两个链表的总长度。当链表长度是几百、几千时毫无压力但如果链表长度达到几万甚至几十万函数调用栈可能会溢出。力扣的测试数据通常不会让链表长到触发栈溢出所以这道题用递归解法在力扣上完全没问题。但在真实的工程场景里如果你要合并的链表可能来自外部数据源长度不受控制递归就不一定是最稳妥的选择。我的建议是面试或刷题时优先写出迭代解法递归解法可以作为补充展示你对递归思想的掌握。两者都值得会写因为面试官可能会追问还能怎么写这时候把两种解法都讲一遍会是很加分的表现。关于递归解法的空间复杂度要特别说明一下虽然你没有显式创建任何节点但递归调用本身会占用函数调用栈空间所以空间复杂度是O(mn)而不是O(1)。这一点如果面试官问到你需要答得出来否则会显得对递归的理解不够深入。5. 实际调试中的常见坑空指针、悬空节点与边界条件5.1 漏掉剩余链表直接拼接的后果我在文章开头提到过合并逻辑本身不难难的是把边界条件写全。最常见的错误就是循环结束后没有把剩余链表接上。假设你写的是while (list1 ! nullptr list2 ! nullptr) { // ... } // return dummy.next;循环结束后如果list1还有剩余节点而你没有执行tail-next list1那么结果链表的末尾就是循环中最后一次接上的节点剩余的所有节点全部丢失。这在力扣上会表现为合并后的链表比预期短或者输出结果缺失了一部分。为什么这个错误特别容易犯因为很多人在写循环时脑子里只想着比较大小、选择较小者根本没有意识到循环退出时还有一条链没走完。解决办法就是形成条件反射任何合并类的问题写完后都要检查剩余部分的拼接这一行。5.2 判断条件用还是的差别如果两个链表里存在相等的值比如list1 [1, 2, 4]list2 [1, 3, 4]判断条件用和用都能得到正确结果[1, 1, 2, 3, 4, 4]。区别在于相等时选哪边的节点。用相等时走else分支选list2的节点用相等时走if分支选list1的节点。因为题目不要求稳定排序所以两者都能AC。但从语义的清晰度来说用更自然一些较小的或等于的先接入。不过偶尔会遇到比较严苛的面试官问你相等时你先取哪个链表的节点为什么这时候你只要解释清楚就没事了。我个人的建议是坚持用一种写法养成肌肉记忆。我自己习惯用因为这样逻辑上更偏向list1优先在合并K个有序链表的进阶题里这种偏向有时候能省一点比较次数虽然影响微乎其微。5.3 指针推进顺序先改tail-next还是先移动list1另一个容易踩的坑是循环里移动指针的顺序。正确的顺序是tail-next list1; // 先把 list1 接到结果链表上 list1 list1-next; // 再让 list1 向后移动 tail tail-next; // tail 也向后移动这里最关键的是第二步list1 list1-next必须在tail-next list1之后执行。因为一旦执行了tail-next list1tail-next和list1指向的是同一个节点如果先执行list1 list1-next并没有任何问题因为list1移动后指向的就是下一个待比较节点。真正的问题出现在另一种写法里list1 list1-next; tail-next list1; // 这样就把原来的 list1 跳过了如果你先移动list1再把它接到tail后面那你实际上把原来的第一个节点跳过了合并结果会平白无故少一个节点。这种错误在代码审查时特别容易被忽略因为逻辑上看起来只是换了个顺序但结果完全不对。我的习惯是把这三步写成一行连招用注释标注清楚这样自己过后看也一目了然。5.4 内存管理谁负责释放节点力扣的判题环境会对你的代码运行结果做检查但它不负责帮你释放new出来的节点。这道题的代码里如果你用ListNode dummy(0)在栈上创建虚拟头节点就不存在这个问题但如果你用了new创建虚拟头节点那么函数结束前需要delete掉否则就是内存泄漏。不过力扣的判题系统不会因为内存泄漏而报错它更关注算法输出的正确性。所以很多人刷题时完全不在乎释放内存这种做法在力扣上可行但如果你把代码搬到本地工程里运行或者参加一些对内存有要求的比赛就需要重视起来。另一个值得注意的点是合并过程中没有创建任何新的链表节点所有节点都来自输入链表。这意味着函数返回后调用者不需要担心这串节点被重复释放的问题。但如果输入的两个链表本身是调用者动态分配的调用者需要在用完后遍历整个合并链表逐个释放。这些都是工程化的考虑刷题时不用写但心里要清楚。5.5 一个完整的调试案例为什么返回结果总是丢尾巴我拿一个真实调试场景来说明。假设你的代码长这样ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy(0); ListNode* tail dummy; while (list1 list2) { if (list1-val list2-val) { tail-next list1; list1 list1-next; } else { tail-next list2; list2 list2-next; } tail tail-next; } // 这里忘了写剩余拼接 return dummy.next; }输入list1 [1, 2, 4]list2 [1, 3, 4]。循环会依次选择节点1来自list1、节点1来自list2、节点2、节点3此时list1指向节点4list2指向节点4。然后list1不为空、list2也不为空循环继续选择节点4来自list1此时list1变为nullptrlist2仍然指向节点4。循环退出。但你没有拼接剩余链表所以最后那个节点4就丢了。通过这种逐步推演你能清晰地看到丢尾巴发生在哪个环节。调试这类问题最有效的方式就是在关键位置打印当前指针指向的值或者你直接在纸上画出每一步的节点连接关系。链表类题目尤其适合画图画清楚了你很难写错。6. 从这题出发合并K个有序链表与归并排序的延伸6.1 力扣23题合并K个升序链表的思路演进做透了第21题你会自然遇到它的进阶版——力扣23题合并K个升序链表。题目给你一个包含K个有序链表的数组要求把它们合并成一个有序链表。这个题最笨的做法是用一个循环每次把当前结果链表和下一个链表用mergeTwoLists合并。时间复杂度是O(k*n)其中n是平均每条链的长度k是链表数量。这样虽然能过但不够优雅。更优的做法有两种。一种是分支合并两两合并逐层向上。第一轮把k条链合并成k/2条第二轮合并成k/4条直到只剩一条链。这样每一层合并的总代价是O(kn)层数是O(log k)所以总时间复杂度是O(kn*log k)。另一种做法是用优先队列最小堆把K个链表的头节点全部放进堆里每次从堆顶弹出最小节点接到结果链表末尾然后从这条链上取下它的下一个节点入堆。重复这个过程直到堆为空。时间复杂度同样是O(knlog k)但空间复杂度是O(k)只存堆里的节点。第21题是这两种进阶做法的基础。如果你连两个链表怎么合并都没练熟那写分支合并或堆解法时会更加吃力。所以我的建议是先把第21题的迭代和递归都写熟再去做第23题你会觉得思路顺滑很多。6.2 归并排序在链表上的应用顺带说一个高频考点链表排序。数组排序可以用快排、堆排但链表因为不支持随机访问很多数组排序算法不好直接套。最合适的算法是归并排序。链表归并排序的思路是用快慢指针找到链表中点把链表分成两半分别递归排序然后用第21题的mergeTwoLists合并两个有序链表。所以你会发现第21题其实是链表归并排序里最核心的合并步骤。你完全可以把合并两个有序链表的实现直接从力扣21的代码里搬过来放到自己的归并排序函数里用。这个延伸路径也解释了为什么面试官特别喜欢考第21题因为它不是一道孤立的题它和链表排序、合并K个链表、甚至某些外部排序问题都有关联。能把这一题讲透面试官有理由相信你的链表基础很扎实。6.3 原地合并与新建链表的取舍还有一个变体值得聊有些题目要求不能改变原链表节点的next指针这时你就得新建链表而不是原地合并。第21题没有这个要求所以原地合并是正确的做法。但在真实的工程场景里你可能会遇到需要保留原始链表的情况。这时候有两种选择一种是先深拷贝一份链表再对拷贝做原地合并另一种是直接新建节点把值拷贝过去。前者节省内存后者代码更简单。没有绝对的对错取决于你的约束条件。如果你在面试中遇到这种变体比较好的回答方式是先说这道题的常规解法是原地合并再补充一句如果面试官要求不修改原链表我会选择新建节点的方式代价是额外的空间复杂度。这样能展示你不仅会写题还能考虑工程约束。7. 力扣刷题视角这道题在进大厂路线图里的位置7.1 为什么很多大厂面试会从链表类题目开始我这些年看过的面试记录里链表题是出现频率极高的开场题。原因有几个一是链表题代码量适中面试官能在短时间内考察候选人的代码能力二是链表涉及指针操作能够区分出只会背题和真正理解数据结构的人三是链表题的变体很多从合并、反转、找环到排序围绕链表可以展开一系列追问。力扣21这道题恰好处在这一系列追问的起点。面试官让你写这题不是指望你写出来就完了而是会顺着你的解法继续问你用的是迭代还是递归为什么空间复杂度分别是多少如果链表很长递归会不会溢出如果改成合并K个链表你的思路是什么这些问题背后的逻辑就是我在前面几节里展开的内容。所以刷题时不要只满足于AC了要把每个细节都吃透这才是刷题攻略里说的高质量刷题。7.2 刷题顺序建议链表专题怎么安排在力扣的刷题路线图里链表专题是一个独立的模块。我建议的刷题顺序是先做力扣206反转链表掌握最基本的指针操作。再做力扣21合并两个有序链表掌握链表合并和虚拟头节点的使用。然后做力扣83删除排序链表中的重复元素进一步练习链表的遍历和删除。接着做力扣141环形链表学习快慢指针技巧。最后挑战力扣23合并K个升序链表和力扣148排序链表把前面的知识点串联起来。这个顺序是循序渐进的每一题都在前几题的基础上增加新的技巧。特别是从21到23的过渡会让你明显感到原来合并两个链表的解法可以复用到合并K个链表上。这种旧解法在新场景里复用的体验是刷题过程中最有成就感的部分之一。7.3 面试时怎么写这题最容易拿高分面试场景和力扣刷题场景有一些区别。在力扣上你只需要把代码提交上去通过所有测试用例就行。但在面试里面试官会观察你的思路展开、边界考虑、代码风格和沟通表达。我建议面试时按这个节奏来先说思路用两个指针分别遍历两条链表比较当前节点值把较小的接入结果链表。用一个虚拟头节点来避免单独处理第一个节点。然后主动说明复杂度时间复杂度O(mn)空间复杂度O(1)。如果你要写递归解法要额外说明递归的空间复杂度是O(mn)因为系统栈会占用空间。写代码时提到边界条件当其中一条链表遍历完直接把另一条链表的剩余部分接上。写完代码后主动走一遍简单的测试用例比如list1 [1,2,4]、list2 [1,3,4]。这会向面试官传递一个信号你写的代码不是凭感觉而是经过验证的。如果面试官追问递归怎么写你再给出递归版本。如果面试官追问能不能优化你可以说在时间复杂度上已经是最优了因为至少需要比较一次每个节点。这一套下来面试官基本没有理由不给好评。这题实在太经典了能讲出深度的人说明平时是真刷过题的。8. 从力扣到工程实战合并有序链表的现实应用8.1 大数据归并排序里的合并有序链很多人刷题时会有一个疑问链表这种数据结构在真实工程里真的用得到吗答案是肯定的但可能不是以链表这个名称出现。在大数据领域外部排序是一个经典问题当待排序的数据量远超内存容量时需要把数据切分成多个有序的临时文件然后进行多路归并。归并的过程本质上就是合并多条有序序列。虽然工程上用的大多是数组、文件或迭代器但核心逻辑跟合并两个有序链表完全一致不断比较各路的当前最小值把最小的取出来。比如在数据库的归并连接Merge Join算法里两个已经按连接键排序的表进行连接时用的就是类似的双指针归并思想左表一个指针、右表一个指针比较大小决定是否输出连接结果然后移动相应指针。这个算法逻辑跟力扣21几乎一模一样只是把指针换成了游标或迭代器。所以你在刷力扣21时学的不是链表怎么连而是一种更高层的思维模式如何高效地把两条有序序列合并成一条。这个思维会以各种形式出现在后续的工作里。8.2 C工程中的指针安全习惯从C工程的角度看这题还给了我们一个很好的指针操作的练习场景。nullptr判断、指针推进顺序、虚拟头节点的创建与释放这些都是工程里最常见的操作。把这些基础打牢对后续学习更复杂的C特性比如智能指针、移动语义都会有帮助。有些初学者在本地用Visual Studio或VS Code写C时会遇到debug assertion failed或access violation之类的报错这通常就是空指针解引用或者访问了已释放内存。通过反复练习链表题你会逐渐养成操作指针前先判断是否为空的习惯。这种习惯在工程里价值巨大。顺便提一句VSCode配置C/C环境时记得把调试器比如gdb或lldb配置好单步调试链表题能在几分钟内定位到问题。我自己调试链表代码时最喜欢用的就是查看指针指向节点的val值这一招比打印整个链表的值高效得多。8.3 从这题延伸出去有序合并思想的多领域应用有序合并的思想远不止链表和数组。在文本处理领域合并两个有序单词列表、合并两个有序时间戳列表思路都相通。在音视频处理领域合并多个有序的音视频片段也需要考虑顺序和衔接问题。如果你把合并两个有序链表抽象一下它其实是一个归并操作输入两个有序序列输出一个有序序列。归并操作是很多复杂算法的基础构件比如归并排序、求两个有序数组的交集与并集、在有序矩阵中查找元素等。所以我不建议你把这题当成刷完就忘的题目。它的价值不在于合并链表本身而在于它把归并这个基础操作以最直观、最简洁的形式展示了出来。你在这个基础上建立的思维模型会在以后遇到各种合并有序数据的问题时反复被激活。9. 动手验证本地C环境下的完整测试代码9.1 本地环境准备与测试代码如果你不想只在力扣网页上做题想把代码拿到本地跑一跑、调试一下我推荐你配置一个简单的C环境。Windows上可以用Visual Studio CommunitymacOS和Linux上可以用VS Code加g配置过程不复杂网上有很多教程。下面是一套完整的本地测试代码包含了链表构建、合并函数、遍历打印和内存释放可以直接复制到本地运行#include iostream 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* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode dummy(0); ListNode* tail dummy; while (list1 ! nullptr list2 ! nullptr) { if (list1-val list2-val) { tail-next list1; list1 list1-next; } else { tail-next list2; list2 list2-next; } tail tail-next; } tail-next (list1 ! nullptr) ? list1 : list2; return dummy.next; } // 根据数组构建链表 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; } // 打印链表 void printList(ListNode* head) { while (head ! nullptr) { std::cout head-val ; head head-next; } std::cout std::endl; } // 释放链表内存 void deleteList(ListNode* head) { while (head ! nullptr) { ListNode* next head-next; delete head; head next; } } int main() { ListNode* l1 createList({1, 2, 4}); ListNode* l2 createList({1, 3, 4}); ListNode* merged mergeTwoLists(l1, l2); printList(merged); deleteList(merged); return 0; }运行这段代码输出应该是1 1 2 3 4 4。注意这里有一个细节合并后merged链表的头节点要么来自l1要么来自l2所以释放内存时只需要deleteList(merged)一次不能分别释放l1和l2否则会出现重复释放导致未定义行为。9.2 对比测试迭代与递归的代码风格差异如果你想在本地验证递归版本可以把mergeTwoLists替换成递归版本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; } }测试结果应该和迭代版本完全一致。我建议你运行一次并打断点观察调用栈的变化这会让你对递归本身会消耗栈空间有更直观的感受。9.3 性能测试与验证如果你对性能有好奇心可以生成两条长度分别为100万的有序链表然后测试迭代版和递归版的运行时间。以我的实测经验来看当链表长度达到10万时递归版会明显变慢甚至可能在主线程默认栈空间macOS约8MB、Linux约8MBWindows约1MB下崩溃。这个实验结果能帮你深刻理解为什么工程代码里要慎用递归。对这个测试感兴趣的读者可以在本地写一个循环生成100万个递增节点的函数然后用std::chrono计时。你会看到迭代版稳定运行在毫秒级而递归版可能会直接报栈溢出。这个对比比背十遍递归空间复杂度是O(n)都管用。10. 写在最后我的刷题体会与下一步建议这道题我刷过不止一遍每次都有新的理解。第一次是在力扣上按部就班写了迭代版AC了就翻篇了。第二次是为了准备面试开始琢磨递归版怎么写把两者比较着看了很久。第三次是在研究归并排序时突然发现原来链表归并排序的合并且过程就是这道题才真正体会到基础题不基础这句话的含义。如果你刚开始刷力扣我给你的建议是不要只追求AC数量要把每一道题的多种解法和边界条件都弄明白。力扣21就是这样一道一题多吃的经典题——迭代、递归、虚拟头节点、时间复杂度分析、工程化思考全都能从这一题里学到。刷题顺序上完成后记得去看力扣23合并K个升序链表和力扣148排序链表你会发现今天学的这个合并函数可以直接复用这种成就感特别爽。最后再分享一个小技巧每做完一道题都用自己的话写一段我学到了什么。哪怕只有几句话积累起来就是你自己的刷题攻略。等刷到几百题再回头看时你会惊讶于自己走过的路。