合并两个有序链表：迭代、递归到K路归并的完整拆解

1. 从一道经典题说起：为什么所有面试官都爱考"合并"

前阵子帮团队做技术面试，十场里至少七场我会让人写这道题：合并两个有序链表。有意思的是，不少候选人觉得这题太基础，随手五分钟写完就以为过关了，结果我一追问"为什么用哑节点""递归写法背后的栈开销你算过吗""如果是K个链表呢"，立刻就卡壳了。

这道题在LeetCode上编号是21，原题描述极其简短：给你两个升序排列的链表，把它们合并成一条新的升序链表并返回。很多初学者把它当成一道"会写就完事"的水题，但我一直认为它是链表类题目里最值得反复咀嚼的一题。原因有三：第一，它包含了链表操作的几乎所有基本功——指针移动、边界处理、虚拟头节点；第二，它是归并排序、合并K个有序链表、甚至外部排序的基石；第三，它表面上只有迭代和递归两种写法，但两种写法背后涉及的思维模型完全不同。

这篇文章不打算只贴答案。我会从迭代和递归两条路线分别拆解，把每一步为什么这样做、边界条件为什么不能漏讲清楚，然后延伸到合并K个链表、归并排序这些变体和工程场景。最后分享几个我在实际面试和代码审查里经常看到的错误。无论你是准备校招面试的在校生，还是写业务代码多年、想把基本功补齐的工程师，这篇应该都能给你一点新东西。

2. 迭代解法：哑节点是你必须养成的肌肉记忆

2.1 先想清楚数据结构和终止条件

链表题的麻烦之处在于，它不像数组那样可以直接通过下标访问，你必须顺着指针一个一个走。合并两个有序链表，直观想法是：维护两个指针l1和l2，每次比较它们所指节点的值，谁小就把谁接到结果链表的尾部，然后对应指针往后移一步，直到其中一个链表走完。剩下的部分因为本身有序，直接拼接。

思路三句话能说完，但实现细节里藏着五个坑。第一个坑就是返回值。很多人会写一个cur指针从第一个节点开始接，最后返回cur——这是典型的错误，因为cur是结果链表的尾部节点，不是头节点。你需要在遍历之前先用一个变量把头节点记下来，但链表初始为空，"头节点"根本不存在。这时就该哑节点登场了。

2.2 哑节点的本质是"占位"

哑节点（dummy node）是链表题里最常见的技巧：在真正链表头之前额外创建一个节点dummy，它不存储任何有效数据，它存在的唯一意义是让你有一个"总是在头部之前的锚点"。

def merge_two_lists(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

注意最后一行return dummy.next，它指向的就是结果链表的第一个有效节点。没有哑节点的话，你不得不用一个if head is None的分支单独处理头节点，代码丑不说，还容易漏。我见过太多候选人一上来不写哑节点，写了几行之后自己把自己绕晕。实际上，只要看到"构造新链表"的题，第一反应就应该是：先建个哑节点。这个习惯养成之后，刷题速度能快不少。

2.3 指针移动的节奏感

这题另一个常见错误是cur忘了后移。cur每次接收一个新节点之后，必须cur = cur.next，否则下一次赋值会覆盖掉上一次的连接，最终链表只有一个节点。这个错误我自己当年也犯过，调试了半天才发现是"接了头没往后走"。

至于为什么选<=而不是<：两种写法都能通过，但用<=会让代码在面对相等元素时优先选择l1链表的节点，结果链表的元素相对顺序稳定。虽然在题目里两个链表的值一样时合并结果完全相同，但从保持稳定性的角度，<=更严谨——特别是你将来实现归并排序时，"稳定"是有实际意义的。

2.4 处理剩余链表的两种姿势

主循环结束后，最多只有一个链表非空。很多人会再写一个while l1: ...加一个while l2: ...的循环逐个搬运剩余节点。能穿但冗余。因为剩余链表的节点本来就是按序排列的，你只需要把当前cur.next指向剩余链表的头节点即可，一行搞定：

cur.next = l1 if l1 else l2

这里有个容易忽视的点：l1或l2可能还有很长一串节点没遍历完，但这无所谓，因为它们本身是合法链表，直接把尾部接过去不会破坏任何结构。我在代码审查里看到不少人在这里写循环，其实是可以优化的。

3. 递归解法：链表题里"递"的思维模型

3.1 递归不是炫技，是另一种建模角度

迭代写法是"模拟人工合并过程"，递归写法的思路不同：合并l1和l2这两个链表，本质上是"比较头节点 + 合并剩下的链表"。两个有序链表合并这个问题，天然具有递归结构——每次只需要处理当前最小的一个节点，然后把更小规模的问题交给函数自己。

def merge_two_lists_recursive(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 = merge_two_lists_recursive(l1.next, l2) return l1 else: l2.next = merge_two_lists_recursive(l1, l2.next) return l2

递归三要素在这里非常清晰：终止条件是某个链表为空；返回值是合并后链表的头节点；本级递归要做的只是"选出当前最小节点，并让它指向剩余部分的合并结果"。这和你写f(n) = n * f(n-1)的阶乘递归在结构上是完全一样的。

3.2 递归为什么"看起来绕"，但又很优雅

我第一次写递归版本时，总觉得它在偷懒：明明没看到完整的合并过程，怎么就返回了正确结果？后来我换了个方式理解：想象函数已经帮你把l1.next和l2合并好了，你只需要把l1接到最前面；再想象函数已经帮你把l1和l2.next合并好了，你只需要把l2接到最前面。也就是"假设子问题已经解决，只处理当前层"。这个思维模型对理解几乎所有链表递归题都通用——反转链表、两两交换节点、合并K个链表，都是一样的套路。

3.3 递归的代价：栈帧和链表长度的关系

递归写法让人犹豫的点是压栈。每次递归调用都会在调用栈上分配一个栈帧，保存局部变量和返回地址。假设两个链表长度分别是 n 和 m，最坏情况下递归深度是 n + m——也就是每次只选一个节点，栈一路压到底。对于常见的百万级节点链表，递归版本是有栈溢出风险的。

Python 默认递归深度限制在 1000 左右，所以如果链表长度超过几百，直接崩给你看。这一点在实际工程里尤其致命。不过话说回来，算法题里链表长度通常不会很大，面试现场用递归写是可以接受的，而且作为工程讨论点，能主动说出来"我们知道最坏情况下递归深度是 O(n+m)，所以工程实现更推荐迭代版本"，反而是加分的表现。

迭代版本额外空间是 O(1)，递归版本空间是 O(n+m)（栈开销）。这个对比我在面试中几乎必问，建议大家都记牢。

4. 复杂度分析和边界测试用例：别让"简单"骗了你

4.1 时间复杂度的直觉证明

两个链表各遍历一遍，最坏情况就是交错合并——比如1,3,5和2,4,6，每次比较都各进一步，每个节点都被访问恰好一次，所以时间开销是 O(n+m)。最好情况呢？一个链表只有一个节点且特别小，另一个链表有十万个节点，主循环只跑一次就进入拼接逻辑，但严格说拼接阶段不涉及节点遍历，整体仍为 O(n+m)——实际运行时间接近 O(1)，但大O记号下跑不掉 O(n+m)，因为最坏情况决定上界。

4.2 必须覆盖的边界用例

这道题的测试用例看你能不能写出一个"教科书级"的测试集合。我在面试时考察过很多人，他们写完能过样例，但一问边界就把自己绕进去了。下面这几组用例我都建议自己跑一遍：

空链表用例放置在最前，是因为终止条件里if not l1: return l2直接返回了非空链表，根本不会走进后续逻辑。这正好对应了递归解法里"空链表是最基础的子问题"——只要这个分支是对的，整个递归的正确性就有了地基。

4.3 如何验证你的合并结果没破坏原链表

这里有个容易踩的坑：题目通常要求合并后返回新链表，但使用迭代方法时，你实际上是把两个原链表的节点重新串了起来，并没有创建任何新节点。这意味着合并操作会"消耗"原链表——原链表结构被改变，所有节点都被归入新链表。如果面试官额外要求"不能修改原链表"，你就需要复制节点后再合并，复杂度不变但空间开销变为 O(n+m)。实际业务中，比如两个有序订单列表合并展示，通常不希望破坏原数据，这个扩展点值得想一想。

5. 变体：从两个链表到合并K个有序链表

5.1 先别急着上堆，顺序思考最重要

题目刷完，很多人的第一反应是"那 K 个有序链表怎么合并？"LeetCode 23题，合并K个升序链表。这里有个天然的思路递进：合并两个链表是固定操作，那是不是可以两两合并，最终归并成一个？比如 4 个链表，先 1 和 2 合并，3 和 4 合并，得到两个新链表，再合并这两个新链表。这种"两两配对、逐轮合并"的做法就是归并的思维，每轮每个节点被访问一次，共 logK 轮，时间复杂度 O(NlogK)，N 是节点总数。代码上可以用一个辅助函数递归分治，本质上就是数组归并排序的链表版。

更常见的进阶解法是用优先队列（最小堆）：维护 K 个链表的当前头节点，每次从堆里弹出最小值节点接到结果链表尾部，然后从被弹出节点的链表里再取下一个节点入堆。时间复杂度同样是 O(NlogK)，但实现起来不需要分治递归，更适合工程化处理。

import heapq def merge_k_lists(lists): dummy = ListNode(-1) cur = dummy heap = [] for i, head in enumerate(lists): if head: heapq.heappush(heap, (head.val, i, head)) while heap: val, i, node = heapq.heappop(heap) cur.next = node cur = cur.next if node.next: heapq.heappush(heap, (node.next.val, i, node.next)) return dummy.next

注意到元组里塞了一个i，这个细节其实是为了避免当两个节点的值相同时，堆在比较元组时去比较链表节点对象——Python 里如果元组前两个元素相同，会比较第三个元素，而 ListNode 对象默认不支持比较，会抛 TypeError。所以这里加上索引 i 作为 tie-breaker，保证任意两个元组都可以被比较。这个细节估计很多人写的时候根本不知道，报错了才意识到。

5.2 从题到模板：归并排序的灵魂

从两个有序链表到 K 个有序链表，再往前一步就是"归并排序"。数组归并排序的核心是"分治 + 合并两个有序数组"，链表版归并排序的核心就是"快慢指针找中点 + 递归排序两半 + 合并两个有序链表"。因为这个合并逻辑你已经写熟了，链表归并排序的编码难度会直线下降。

也就是说，本题不是孤立的一个小题，它是整个"归并"体系的地基。你可以顺着这条线把 88题合并两个有序数组、21题合并两个有序链表、23题合并K个有序链表、148题链表归并排序串起来做，做完这几题，你的"归并"认知会非常结实。

6. 我在面试和代码审查中的几个真实观察

6.1 最常见的错误清单

一道这么简单的题，代码审查里依然能挑出很多问题，可见基本功这东西确实需要专门练。我整理了高频错误：

• 忘记让cur后移，导致链表断链，最终只保留一个节点。这类错误几乎全是手速快、脑子慢造成的，建议写完立刻检查一遍指针移动。
• 返回值返回了dummy而不是dummy.next，结果链表头多了一个值 -1 的脏节点。
• 边界分支只有l1 is None没有l2 is None，或者反向漏掉。其实这道题只要有一个链表为空，直接返回另一个链表就是正确答案，但写的时候很多人非要走主循环，然后空指针异常。
• 循环条件写成while l1 or l2，然后在循环体内分别处理之一为空的情况。虽然可运行，但代码又长又容易出错。标准的写法应该用while l1 and l2，把"某一方为空"留给循环之后的拼接逻辑处理。
• 递归版本里忘记写终止条件。这会导致无限递归直接栈溢出，而且这道题的递归结构特别容易漏掉，因为直觉上"两个链表怎么会有终止？"——有的，只要有一个为空，就返回另一个。

6.2 现场面试的踩分点

如果你正在准备面试，这道题的"满分答案"不是直接把代码背下来，而是展示出完整的问题解决链条：先说清楚思路和时间复杂度，提一句"可以用哑节点简化头节点处理"，代码写完后主动补充"如果数据量非常大，递归会面临栈溢出风险，所以工程上更推荐迭代实现"，最后再追问一句"需要处理原链表不被破坏吗"。这四步走下来，面试官很难不给你高分。

6.3 工程场景里的真实身影

你可能会想：这种链表合并，业务代码里真的用得上吗？答案是：直接用到不多，但"合并两个有序流"的思想无处不在。比如消息系统合并两个按时间排序的推送队列，K 线数据服务合并多路行情流，甚至数据库里归并排序的底层实现就是两两合并有序段——在真实系统里，数据很少是手动建链表，但数据流、迭代器、文件块这些本质上都是"有序序列"，合并有序序列就是合并有序链表的抽象升级。

我做过一个有意思的实践：公司内部有一个日志聚合系统，多个服务实例各自产出按时间排序的日志文件，需要汇总成一份全局有序的日志流。当时有人提议把所有日志读进内存排一次序，我直接说不用——每个文件本来就有序，用 K 路归并就能以 O(NlogK) 的代价扫完，配合优先队列做增量排序，内存占用极低。实现完那一刻，我意识到链表合并这道题刷了十几年，终于从课堂走进了生产环境。

7. 一道题，两种写法，三个延伸点

聊聊最终我自己的感受：合并两个有序链表这道题，"会写"和"理解透"之间有相当长的距离。迭代版本强化的是哑节点和指针操作基本功，递归版本强化的是递归建模思维，延伸版本则是归并排序的整体观。这三层都打通之后，你在链表操作、分治思想、堆处理海量数据方面都会有质的提升。

最后分享一个关于刷题的小技巧：不要满足于 AC（通过所有测试用例）。每做完一道题，花十分钟做三件事——看看别人用不同语言或者不同思路的高票答案；把这道题和原题做一个小改动（比如合并时去重、返回反转结果等）再写一遍；把核心代码默写一遍。这个方法我用了很多年，对付"理解不透"最有效。尤其是本题这种看似简单、实则可挖空间巨大的题目，值得你多花这一个十分钟。