合并两个有序链表：哑节点与递归写法详解

开头LeetCode HOT 100 第21题合并两个有序链表这道题可以说是链表类题目里的“第一课”。很多公司面试的第一道算法题就是它热度和使用频率在题库里常年排在前列。凡是系统刷过LeetCode的人基本都绕不过这道题。它的代码量很短短到只有十几行但里面包含的东西一点都不少哑节点、双指针、递归、边界条件处理……几乎每个话题拿出来都够面试官追问十分钟。适合准备算法面试的求职者也适合刚入门数据结构、想通过一道题打通链表基本功的学习者。这篇文章我会把这道题的两种主流解法、背后的原理、刷题时容易踩的坑以及面试中的常见追问一次说清楚。1. 题目拆解先搞清楚“合并有序链表”到底在考什么1.1 题目到底在问什么题目本身描述非常简洁给定两个升序排列的单链表按顺序把两个链表合并成一个新的升序链表然后返回新链表的头节点。听起来很简单但这背后有几个隐含约束值得细说。第一链表是“引用的集合”和数组不同我们不能随机访问某个位置的节点必须从头开始一个个走。第二题目没有说“不能修改原链表”所以一个合法的解法完全可以在原链表节点上做指针调整不需要分配新的节点来存数据这正是迭代法的核心思路。第三两个链表可能是空的也可能长度差异很大边界条件处理必须完整覆盖所有输入情况。面试里我见过不少人一上来就写得很顺结果把合并后的链表输出出来发现少了节点或者末尾指针没有断开直接串到原链表的中间位置。这些问题的根源都是没有在动手前把“指针从哪来、到哪里去、谁连着谁”想清楚。1.2 这道题为什么值得反复做从面试角度说这道题是“保底送分题”也是“深挖追问题”。它短所以作为开场题不会给候选人太大压力但它又覆盖了链表操作中最核心的几个技巧所以面试官很容易从中延伸出更复杂的变体比如“合并k个有序链表”“链表归并排序”“判断两个链表是否相交”等。从学习角度说这道题是理解链表“引用语义”最好的载体。数组里我们交换两个元素只是交换位置上的值链表里调整顺序本质是改变节点的 next 指向。很多人学链表总是迷迷糊糊就是因为脑子里还停留在“数组思维”没有建立“指针思维”。把这道题的迭代写法彻底吃透你对“指针到底指向什么”会有一个质的提升。2. 迭代法哑节点与穿针引线2.1 为什么不直接用一个新链表的头节点作为起点先思考一个问题合并后的链表头节点到底应该是 list1 的头还是 list2 的头这取决于两个头节点的值谁更小。如果单独写一个 if 分支去判断“谁做新头”代码会多一条分支而且后续每做一步都要维护“当前节点是谁”的状态非常啰嗦。更优雅的做法是引入一个哑节点dummy node也叫虚拟头节点。这个节点不保存任何有意义的数据它的唯一作用是给新链表一个统一的起点。后续不管是 list1 的节点还是 list2 的节点接入都通过同一个游标指针 cur 来操作最后返回 dummy-next 就是真正合并后的头节点。这样在逻辑上就彻底消除了“第一个节点要单独处理”的尴尬。我个人的体会是哑节点的本质是一种“哨兵模式”。它不参与业务逻辑却能把边界情况化成普通情况。这个技巧在链表题里几乎无处不在删除倒数第k个节点、翻转链表的一部分、环形链表找入口……凡是头节点可能变化的题目你都可以尝试用哑节点来简化逻辑。2.2 迭代写法的完整实现与逐行剖析先看完整的 C 实现我习惯用 C 写算法面试题因为它对指针的暴露最直白最容易看出一个人是否真正理解链表ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* dummy new ListNode(0); ListNode* cur dummy; while (list1 ! nullptr list2 ! nullptr) { if (list1-val list2-val) { cur-next list1; list1 list1-next; } else { cur-next list2; list2 list2-next; } cur cur-next; } if (list1 ! nullptr) { cur-next list1; } if (list2 ! nullptr) { cur-next list2; } return dummy-next; }这块代码的逻辑顺序非常重要。第一比较的是 list1-val 和 list2-val取较小者接入第二接入操作是 cur-next list1然后立刻让 list1 指向它的下一个节点再让 cur 也往前移动一步。这两步“先接再移”的顺序一旦写反就会出现当前节点还没接上游标却已经跑到下一个位置的问题。很多人第一次写的时候会问为什么最后两个 if 可以直接把剩下的链表整段接上不需要循环因为剩下的那段链表本身已经是有序的它内部的结构无需任何改动只需要让新链表的尾节点指向它的头节点即可。这是链表合并和数组合并的一个显著区别。2.3 复杂度分析和空间占用说明迭代法的时间复杂度是 O(m n)其中 m 和 n 分别是两个链表的长度。因为每轮循环都会让 list1 或 list2 前进一步最终最多走完两个链表的所有节点。空间复杂度是 O(1)。这里有个容易误解的点dummy 节点不是需要额外分配的吗严格来说dummy 节点占用的空间是常量级的不随链表长度增长所以算 O(1)。还有一种更“抠门”的写法直接复用其中一个链表的头节点作为结果链表的头不需要 new 哑节点但那种写法要单独处理“第一个节点选谁”的分支代码可读性会下降。我建议刷题阶段用哑节点面试手写时也优先用哑节点清晰比省一个节点的空间更重要。3. 递归法把大象装进冰箱的三句话3.1 递归的本质是什么递归解法的代码比迭代法更短但是理解门槛更高。核心思路可以概括为每次只解决“当前两个节点的比较”剩下的部分交给递归函数自己去处理。具体来说如果 list1 的头节点值更小那么这个节点就应该是合并结果的头节点它的 next 应该是“list1 的下一个节点 和 list2 合并后的结果”。同理如果 list2 的头节点值更小就反过来。递归的出口是有一个链表为空那么直接返回另一个链表。你可以把递归理解成一个“延迟承诺”。当前节点先确定“我该接谁”至于“我的后面怎么排”我不直接算而是把问题缩小一点再交给同样的函数。这个缩小问题的过程就是递归的精髓。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; } }这段代码的关键在于理解每一层递归的返回值。返回值永远是“那两个链表合并后的头节点”。所以当 list1-val 更小时list1 的 next 就指向“list1-next 和 list2 合并后的结果”然后整个函数返回 list1。这个逻辑其实和迭代法是完全一致的只是换了一种表达方式。很多初学者盯着这段代码看半天感觉“好像看懂了但想不出来”。我的建议是把递归调用展开成树状结构手动写几次。比如 list1 [1, 3, 5]list2 [2, 4, 6]递归执行时每一层的返回值是什么、谁接了谁拿笔画一遍就通了。3.3 递归的空间代价到底是多少递归法的空间复杂度不是 O(1)而是 O(m n)。因为每次递归调用都会在系统栈上占一层空间最坏情况下递归深度等于两个链表的总长度。在面试中这是一个常见的追问点有些人会把递归的空间复杂度答成 O(1)这就是没搞清楚。那递归法是不是就一定比迭代法差也不是。递归代码简洁展示的是对问题结构的理解迭代代码显式可控展示的是对指针的掌握。两者在面试中都是合格解。不过在实际系统中如果链表特别长递归深度过大可能导致栈溢出所以生产环境我一般优先写迭代。4. 边界条件与常见问题排查实录4.1 极易踩空的边界条件作为一道简单题绝大多数提交出错的场景都集中在几个特殊的输入情况上。我整理了一份测试用例清单建议写完代码后第一时间跑这些用例场景输入预期输出两个链表都为空[] 和 [][]一个为空另一个非空[] 和 [1,2,3][1,2,3]两个链表等长且交替小[1,3,5] 和 [2,4,6][1,2,3,4,5,6]一个链表完全小于另一个[1,2] 和 [3,4,5][1,2,3,4,5]两个链表存在相等值[1,2,4] 和 [1,3,4][1,1,2,3,4,4]特别是“一个链表为空”的情况很多人不是不会处理而是忘记处理。我在模拟面试中见过不少候选人一开始把 while 循环写对了但循环结束后没有把剩余链表接上导致输出缺了一截。4.2 链表操作中的经典指针陷阱第一个经典陷阱是“指针丢失”。比如你写 cur-next list1 之后必须先 list1 list1-next否则下次循环你还在用同一个 list1 节点最后合并结果里会出现重复节点。顺序颠倒的直接后果就是死循环或者结果链表结构错乱。第二个经典陷阱是“忘记移动 cur”。每次接完一个节点cur 必须跟着往前挪一步否则后面的节点会把前面的节点覆盖掉结果链表只保留最后一个节点。我在审代码的时候遇到过几次这种问题表现形式五花八门但根因都一样游标没有前进。第三个经典陷阱是“提前返回 dummy”。正确写法是 return dummy-next但总有新手写成 return dummy。这相当于多返回了一个值为 0 的哨兵节点最后结果链表开头多出一个不存在的节点。这个错误特别隐蔽因为在本地测试时可能因为打印逻辑没注意而被忽略。4.3 常见问题速查表错误现象可能原因解决方式输出结果第一个节点多了一个0返回了 dummy 而不是 dummy-next检查 return 语句合并结果中间有重复节点接节点后没有让对应链表指针前进检查 list1/list2 是否在 cur-next 赋值后立即更新程序运行超时cur 没有移动导致死循环检查 cur cur-next 是否存在输出缺少最后一个节点循环结束后没有拼接剩余链表检查两个 if 判断剩余链表递归栈溢出递归基线条件不完整或递归深度过大先确认空链表返回逻辑再评估空间复杂度5. 面试延伸这道题还能引出什么考法5.1 合并 k 个有序链表这道题的进阶版是 LeetCode 23合并 k 个有序链表。表面上是把两个链表换成 k 个难度却直接跨了一个量级。最常见的解法有两种。第一种是“两两合并”把第 1 个和第 2 个合并结果再和第 3 个合并依次类推。这种方法实现简单但总时间复杂度的推导有点意思。假设每个链表长度为 n做 k-1 次合并每次合并都能达到 O(kn) 的量级整体就退化成 O(k²n)。面试时你需要能分析出这个复杂度。第二种是用优先队列堆来维护 k 个链表的当前头节点每次取出最小的节点接入结果然后推入该节点的下一个节点。复杂度是 O(nk logk)在 k 比较大的时候优势非常明显。这里需要你熟练使用堆这种数据结构很多人卡在“优先队列里存放的是节点比较器要按节点值排序”这个细节上。5.2 与归并排序的关联链表的归并排序核心就是“找中点、递归排序、然后合并”。其中“合并”这一步用的就是这道题的 merge 逻辑。所以如果你把 21 题吃透了链表归并排序其实已经完成了一半。我建议把这两道题放在同一天刷。先写 21 题的迭代版本再尝试写链表的归并排序你会发现“排序”中最关键的一步你早就掌握了。而且链表的归并排序不需要额外开辟数组来存数据空间复杂度可以做到 O(logn)只靠递归栈的空间这是它相对于数组归并排序的一个优势。5.3 原地合并与内存优化这道题还存在一个“不 new 任何节点”的变体要求。意思是你不能创建哑节点也不能复制节点值只能在原链表上调整 next 指针。解法依然清晰先比较两个链表头节点选较小者作为结果头然后迭代合并后面的节点。这种写法的意义在于展示你对“链表就是引用操作”的深度理解。但它的代码分支处理会稍微多一点因为第一个节点必须单独选。我在实际手写时还是推荐带哑节点的版本至少在白板上更容易讲清楚思路。面试中主动说一句“我也可以用哑节点来减少边界分支”比憋半天写一个没有哑节点的版本要好得多。6. 刷题之外的复盘笔记6.1 这道题最优的刷法顺序根据刷题经验拿到这道题不要急着抄答案而是按四个阶段来推进。第一阶段用笔在纸上画出两个链表模拟一遍指针移动过程不看任何代码。第二阶段自己写出第一个能通过的迭代版本跑几个边界用例。第三阶段尝试写递归版本并分析两种写法的空间复杂度。第四阶段打开编辑器的调试工具在每个循环入口打印当前节点的值和指针位置观察“接”“移”两个动作的执行顺序。这四个阶段做完你会发现自己对链表的“引用思维”有了很大的变化。以后再碰到“反转链表”“删除倒数第n个节点”这类题至少不会在“指针到底指向哪”这个问题上卡壳。6.2 个人一点实操建议刷题这件事最怕的就是“看懂了但写不出”。我自己的做法是每道题看完答案后一定要把代码关掉从头自己写一遍。如果写到一半卡住就回顾一下卡住的那个点而不是马上再看答案。这道题我前前后后带着不少人过过大多数卡住的地方都很一致“合并结束后剩余链表怎么接”“递归时返回的到底是谁”。想清楚这两个问题这道题就是真正拿下了。如果现在你准备面试建议把这道题的迭代版本练到闭着眼睛能默写然后把递归版本练到能流畅解释每一步的返回值和作用。你这道题的掌握程度基本就代表了你在链表基本功这一块的下限。6.3 后续还可以怎么扩展这道题做完可以马上接三道关联题反转链表、删除链表的倒数第N个节点、环形链表。这三道题加上本题就构成了链表最核心的五个操作合并、反转、删除、判环、找中间点。把这五类操作都吃透链表面试就基本不虚了。另外还有一个思维扩展点就是你把合并两个有序链表理解为“双指针归并”这个概念会反复出现在数组的合并有序数组、字符串的交替拼接等场景里。所以这道题的本质并不只在链表本身它是“归并思想”的缩影。有了这层理解下次遇到任何“两个有序结构合并成一个有序结构”的问题哪怕它长得再奇怪你的第一反应都会是双指针。