如果你刷过 LeetCode 的热门 100 题大概率绕不开第 21 题合并两个有序链表。这道题在面试里的出场率非常高几乎成了链表基本功的代名词——它不像动态规划那样需要天马行空的构思考的就是你对指针操作和边界条件的掌控力。我最早刷这道题时花了大半个晚上琢磨递归的返回值后来才发现只要把迭代版吃透后面 23 题的合并 K 个有序链表、148 题的排序链表都会轻松很多。今天这篇就以第 21 题为支点把迭代、递归两种解法掰开揉碎讲清楚再把边界情况、易错点、复杂度分析全部过一遍最后聊聊它和其他链表题的关联。不管你是刚开始刷题的新手还是准备面试想快速过一遍高频题的老手这篇都能给你一些可以直接用的东西。1. 题目到底在考什么先搞清楚考点再动手1.1 题目本身的理解简单说给定两个升序排列的链表 l1 和 l2把它们合并成一个新的升序链表并返回。注意题目里有一句很关键的话新链表应该通过拼接原始两个链表的节点来生成。这句话直接划定了边界不能 new 出一堆新节点、把值复制一份再串起来。你只能在原节点上动手脚通过改变 next 指针的指向把两个链表串成一个新的有序链表。很多人第一次做这题时没注意这个限制下意识地复制节点值结果写出了一个多占用内存的版本。这在 LeetCode 上能通过但在面试里会被面试官追问内存开销的问题。两个输入链表的长度比较随意可能是空链表也可能一个长一个短。题目要求返回合并后链表的头节点而头节点恰恰是链表操作最容易出错的地方之一——因为合并完了你才知道头到底是 l1 的还是 l2 的。1.2 为什么它是热门题LeetCode 热门 100 题里收录这道题不是因为它难而是因为它把链表最核心的几个考点拧在一起了指针的移动和重指向双指针的同步遍历思想边界条件的处理空指针、剩余链表递归思维的入门训练换句话说它就像链表题里的起手式。你要是能把这道题写利索后面很多链表题都有套路可循。我自己的刷题路径里第 21 题是紧接着 206 题反转链表刷的两道题放在一起对比着看能很快建立起链表操作无非就是改 next 指针的感觉。2. 手写迭代解法哨兵节点 双指针一步步拼出结果2.1 哨兵节点到底解决什么问题先想一个朴素的问题如果不用哨兵节点直接拿一个变量 head 来维护合并后的链表头会遇到什么麻烦每次比较 l1 和 l2 的头节点把值小的一方接到结果链表的尾部。但你首先要处理第一个节点谁来当头这个问题。第一个节点可能是 l1 的头也可能是 l2 的头取决于谁的值更小。为了处理这个分支你免不了要写一段当前结果链表是否为空的判断或者给 head 预设一个特殊处理。哨兵节点dummy node就是专门治这种尴尬的。它的思路很简单先随便造一个节点当假头反正它不参与真正的数据比较最后返回它的 next 就完事了。这样整个合并过程中你始终有一个确定的结果链表的尾巴可以接新节点头节点反而从头到尾都不用特别操心。这个技巧不光用于合并链表链表题里几乎所有涉及头节点可能变化的场景都能用上删除节点、翻转链表、分区链表等。很多人用顺手之后会产生路径依赖看到链表题先无脑加一个 dummy这是好事。2.2 迭代实现的完整代码迭代版的思路就是双指针各扫各的。维护一个 tail 指针指向当前合并链表的尾节点。每次比较 l1 和 l2 当前节点的值谁小就把谁摘下挂到 tail 的后面然后相应的指针前移一步。循环结束后最多还剩一个链表没走完直接把剩余部分接上。// C 版 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); // 哨兵节点 ListNode* tail dummy; // tail 始终指向结果链表的尾节点 while (l1 l2) { if (l1-val l2-val) { tail-next l1; l1 l1-next; } else { tail-next l2; l2 l2-next; } tail tail-next; // 记得把 tail 前进 } // 剩余部分直接拼接 tail-next l1 ? l1 : l2; return dummy.next; }# Python 版 def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) - Optional[ListNode]: dummy ListNode(0) # 哨兵节点 tail dummy # 结果链表的尾节点 while l1 and l2: if l1.val l2.val: tail.next l1 l1 l1.next else: tail.next l2 l2 l2.next tail tail.next tail.next l1 if l1 else l2 return dummy.next有个细节值得单独提一下tail tail-next这一步不要漏。很多新手写完 if-else 就忘了把 tail 往后挪结果下一次循环又接到同一个节点上最后链表直接穿成一团。每次挂上一个新节点tail 都必须跟上。2.3 用一个例子走一遍流程拿 LeetCode 自带的示例走一遍l1 [1, 2, 4]l2 [1, 3, 4]。初始化dummy - nulltail 指向 dummy。第一次比较l1.val1, l2.val1取 l1 的 1。tail-next 指向这个节点l1 移到 2tail 移到 l1 的那个节点。此时结果链表dummy - 1。第二次比较l1.val2, l2.val1取 l2 的 1。tail-next 指向它l2 移到 3tail 移到这个节点。结果dummy - 1 - 1。第三次比较2 vs 3取 2。结果1 - 1 - 2。 第四次比较4 vs 3取 3。结果1 - 1 - 2 - 3。 第五次比较4 vs 4取 l1 的 4。l1 变空l2 还剩一个 4。 循环结束tail-next l2直接把 4 接上。最终结果1 - 1 - 2 - 3 - 4 - 4。这个模拟过程说白了就是一句口诀两个链表比大小小的就归队谁先空谁退场。走一遍之后你会明显感觉到迭代版整个过程非常物理——从头到尾就是不断把节点一个个串起来没有任何跳步和取巧。3. 递归解法用返回值得巧思但别被调用栈坑了3.1 递归的终止条件设计递归版和迭代版完全是两种思路。迭代是从前到后地推着走递归则是从后到前地想问题。先想递归的出口如果 l1 为空那合并结果就是 l2如果 l2 为空那合并结果就是 l1。这两个条件必须写在最前面是递归的 base case也是绝大多数递归题最容易漏的地方。接下来是核心逻辑既然 l1 和 l2 都是有序的合并后的头节点一定是二者头节点中值较小的那个。假设 l1.val 更小那么合并后链表应该是l1 作为头节点后面接着 merge(l1.next, l2) 的返回结果。也就是说每一层递归只负责解决一个选头的问题剩下的子问题全部交给下一层。// C 版 ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!l2) return l1; if (l1-val l2-val) { l1-next mergeTwoLists(l1-next, l2); return l1; } else { l2-next mergeTwoLists(l1, l2-next); return l2; } }# Python 版 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很多新手卡在递归版的原因是妄图手动模拟每一层递归的调用与返回。这是一个巨大误区。正确的心态是相信函数一定能完成它该完成的事——你已经写好了 merge 这个函数它返回的就是两个链表合并之后的头节点那 l1.next merge(l1.next, l2) 这句话的含义就非常清晰先合并从 l1 的下一个节点开始的链表和l2 整个链表然后把结果接到 l1 后面。3.2 递归的调用过程怎么走还是拿 [1, 2, 4] 和 [1, 3, 4] 来走。第一层l1.val1 l2.val1所以 l1.next merge([2, 4], [1, 3, 4])return l1。第二层2 1所以 l2.next merge([2, 4], [3, 4])return l2。第三层2 3所以 l1.next merge([4], [3, 4])return l1。第四层4 3所以 l2.next merge([4], [4])return l2。第五层4 4所以 l1.next merge([], [4])return l1。第六层l1 为空return l2也就是 4。然后层层往回组装第五层返回 l1节点 4- 第六层返回的 l2节点 4第四层返回 l2节点 3- 第五层返回来的 4 - 4第三层返回 l1节点 2- 节点 3 - 4 - 4……最终结果和迭代版完全一致。3.3 递归的适用边界递归版代码看起来比迭代版更数学但有一个肉眼可见的问题调用栈深度等于递归层数。最坏情况下两个链表全都交错排列递归深度会达到 O(mn)。如果链表很长比如几万个节点递归版就可能触发栈溢出。竞赛和面试里链表长度一般不会设计到几万级所以递归版能 ACAccepted。但如果是实际工程里处理超长链表的合并迭代版的空间稳定性是明显优于递归版的。这也是为什么我会建议刷题阶段两种写法都要会但面试写代码时优先给迭代版——代码引导性好、不容易犯递归过度嵌套的错。4. 复杂度分析看着简单但别算错4.1 时间复杂度为什么是 O(mn)很多人在纸面上写这道题的复杂度时随手就写 O(n)这不严谨。正确表达是 O(mn)其中 m、n 分别是 l1 和 l2 的长度。推导逻辑很简单每一次循环只会把一个节点固定到最终结果里。两个链表一共 mn 个节点每个节点至多被比较一次、被挂接一次所以总的比较次数不会超过 mn。递归版也一样每一层递归只消耗一个节点总递归次数 mn。复杂度里的 m 和 n 能不能省略掉一个不能因为两个输入链表的规模是相互独立的。只有当题目固定了其中一个链表的长度时才能简化成 O(n)。很多面试官会在这个地方设个小陷阱你答O(mn)并说明理由他会觉得你是有意识地在分析而不是背答案。4.2 空间复杂度迭代与递归的真正差距迭代版只用了两个辅助指针dummy 和 tail不管是 C 还是 Python额外空间都是常数级别空间复杂度 O(1)。这是它最讨喜的地方——不申请任何额外节点纯粹靠改指针完成合并。递归版就不同了。每一层递归调用都会在系统栈里压入一层栈帧最坏情况下栈深度是 O(mn)因此空间复杂度是 O(mn)。虽然 LeetCode 判题不太会卡这个但你心里得清楚递归的优雅不是免费的它拿栈空间做了代价。还有一种写法也值得拿出来对比有些人会写出新建节点、逐个复制值的版本。这种写法时间上同样是 O(mn)但空间上额外申请了 mn 个节点复杂度变成 O(mn)。更关键的是它违背了题目拼接原节点的要求面试时属于典型扣分写法不要图省事去写。5. 边界情况与易错点这些坑我全踩过5.1 空链表与长度不一致两个链表都为空的情况直接返回空就行。一个为空另一个非空合并结果就是那个非空链表本身。这两个极端情况在迭代版里靠 while 条件自然兜住l1 或 l2 任一为空时循环直接结束tail-next l1 ? l1 : l2负责把剩下那一段接上。如果你的代码没有这个剩余拼接步骤遇到一个链表先跑完的情况合并结果会直接丢尾巴。递归版里两个 base case 的书写顺序也值得注意。建议先判断 l1 为空再判断 l2 为空虽然两个都为空时无论先返回谁都一样但保持固定的书写习惯能减少手滑。5.2 值相等时怎么处理两个节点值相等时取 l1 还是 l2 都对。上面的代码用了也就是说相等时偏向取 l1。你可以改成严格效果一样。唯一要注意的是别把两个分支写错。有些新手为了图省事会用if (l1-val l2-val)、else 里直接挂 l2这种写法本身没问题但如果手滑把 l1 和 l2 的指针搞反就会出现跳过一个节点或者链表成环的问题。5.3 C/C 内存陷阱与调试经验C 版里有个非常经典的坑合并时千万不要 free 或 delete 任何节点。合并操作的实质是偷节点——把一个节点从原链表摘下来挂到新链表上。这个节点从头到尾只存在一份如果你提前 delete 了它后面挂上去的就是一个悬空指针轻则崩溃重则产生难以排查的随机错误。同理也不要在合并过程中用new去申请新节点。某些 IDE 的自动补全会诱导你写出ListNode* node new ListNode(val)这样的语句这在语义上就是错的——你要合并的是节点本身不是复制值。调试链表题我最常用的一招是写一个 printList 函数在关键节点打印整个链表。链表的 bug 和数组不同数组越界通常立刻崩链表错乱往往要到访问下一个节点时才暴露所以光靠断点不够直观。画图也好用尤其是指针问题的排查手动画出几个节点的 next 指向改动前后一对比答案通常自己就跳出来了。6. 从这道题延伸出去哪些题和它同宗同源6.1 从合并两链表到合并 K 个链表第 21 题合并两个有序链表而 LeetCode 23 题合并 K 个升序链表基本上就是本题的进阶版。解决 23 题最常见的方法有两种一种是用优先队列最小堆每次选所有链表头节点中最小的那个另一种是分治合并两两一组合并再把结果往上归并。如果你把 21 题写得够熟23 题其实只是多了一层管理多个链表的壳。很多人在刷 23 题时卡住回头看都是因为 21 题里的剩余拼接没写熟练——因为分治法里频繁调用 mergeTwoLists一旦合并函数写错整个分治全是错的。6.2 链表排序、归并思想与真实工程场景第 148 题排序链表核心也是这题的变体先把链表用快慢指针分成两半递归排序然后合并两个有序链表。所以你看第 21 题并不是孤立的一道题它是整条链表归并路线的地基。真实工程里这种合并有序链表的思路也随处可见。比如多个有序日志文件要合并成一个全序文件、多个分片服务返回的有序数据流要归并成单一数据流、甚至多路归并排序的场景核心思路都是两个有序链表的合并放大版。另外链表本身在真实系统里应用很广——操作系统内核的任务队列、内存管理中的空闲块链表、消息队列底层都是链表的影子。对面试来说第 21 题是链表基本功的试金石对工程来说它代表的合并有序数据流思想则是数据处理的常见套路。最后分享一点个人体会。链表题和数组题最大的不同在于数组的操作可以用下标直观想象链表必须靠画图才能想清楚。第 21 题我至少画了十几次图才真正形成肌肉记忆但形成之后后面遇到任何需要保持链表顺序的题目我都会本能地先考虑加一个 dummy 节点。这题看着简单但非常值得多刷几遍隔几天不看能不能闭着眼写出来才是真的过关。