1. 这道题为什么值得反复刷合并有序链表的本质与常见误区如果只让我推荐三道链表入门题LeetCode 21“合并两个有序链表”一定在其中。它的题干极短给定两个升序链表list1和list2把它们合并成一个新的升序链表并返回。别看题目简单它几乎是所有后续链表操作题的基石——合并K个有序链表、归并排序中的合并步骤、甚至 LRU 缓存里的链表节点搬运底层都在用同样的指针推进思想。很多人在面试时觉得自己会做但一追问“你的哨兵节点能不能省掉”“原地合并和新建节点到底差在哪”“两个链表长度极端不均衡时你的代码还对不对”就答不上来了。这篇文章我想把这题彻底讲透迭代法、递归法、原地合并法都给出可运行的完整代码附上每一步的原理说明再把面试官最常见的几个变形和坑一次性说清楚。先说结论方便你心里有个底这道题的时间复杂度必然是 O(nm)因为每个节点至少要“看一眼”才能确定它在最终链表中的位置额外空间方面迭代法和原地合并法都是 O(1)递归法最坏会到 O(nm) 的栈空间。如果你面试时写了递归记得主动说明这一点——大多数面试官想听的正是这个权衡。很多初学者第一次写这题最大的误区是试图“原地穿插”两个链表的节点结果绕晕了自己。其实合并链表和合并两个有序数组的逻辑完全一致只是把数组里的“下标指针”换成了链表里的“节点指针”。数组归并时你会开一个新数组放结果链表归并时最简单可靠的做法同样是拉一个“哨兵节点”当新链表的头然后两个指针分别从两个链表头部出发谁小就把谁接到结果链表的尾部。这个思路直观、不容易出错是保底方案。不过只有保底方案是不够的。面试是淘汰制别人会原地合并你不会那差距就出来了。所以这篇文章会花大篇幅讲清楚三种写法的实现细节和适用场景最后还附上我整理的几组边界测试样例你可以直接拿去验证自己的代码。2. 迭代法哨兵节点与三指针推进的完整走读2.1 为什么一定要用哨兵节点先看最经典的迭代写法。核心思路是维护一个dummy哨兵节点作为结果链表的头节点前置同时维护cur指针指向结果链表的尾部每次从list1和list2当前指针所指的节点中挑一个值更小的接到cur后面然后让对应的链表指针前进一位。最后把还没走完的那条链表的剩余部分直接接上。代码非常短但每一行都有讲究class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def mergeTwoLists(list1, list2): dummy ListNode() # 哨兵节点 cur dummy # 结果链表尾指针 while list1 and list2: if list1.val list2.val: cur.next list1 list1 list1.next else: cur.next list2 list2 list2.next cur cur.next # 把剩余部分直接接上去 if list1: cur.next list1 if list2: cur.next list2 return dummy.next为什么非要一个dummy因为合并结果可能是空链表也可能是list1或list2中的任意一条。如果不用哨兵节点你就得单独处理“结果链表为空时头节点怎么赋初值”的问题代码会多出两三个if分支。哨兵节点的作用本质上和数组归并里“预先分配一块输出数组”一样先占一个位置后续无脑往尾指针后面接就行最后返回dummy.next就拿到了真正的头节点。这里有个面试细节if list1.val list2.val用还是两种写法对最终结果没有影响因为两个链表本身就是有序的重复值谁先谁后都合法。但用可以让代码语义更明确当两个值相等时优先取list1的节点这算是一种稳定的归并行为。面试时如果被问到能答出这个区别会加分。2.2 尾部拼接与循环不变式的证明很多人的代码毛病出在循环结束后的处理。循环退出只有两种可能list1走完了或者list2走完了。此时另一个链表剩余的部分必然都是大于等于已合并部分所有值的有序序列所以直接把cur.next指向它即可不需要再逐个节点比较。这也是归并算法“懒处理”的精髓剩余部分天然有序整体顺序不会被破坏。如果从“循环不变式”的角度严谨证明这个写法的正确性过程是这样的初始状态dummy是哨兵cur指向dummy此时结果链表为空。两个待合并链表的所有节点都未被改动显然成立。循环中假设某次迭代开始时cur指向结果链表的尾部结果链表中的节点严格按从小到大排列且结果链表中的所有节点值都小于等于list1和list2当前头节点的值。此时比较两个头节点把较小的那个接过来新结果链表的末尾变成了这个节点依然有序且新末尾节点的值一定小于等于剩下两个链表头节点的值所以下一次迭代前不变式依然成立。循环结束后直接把剩余链表接上不变式覆盖到全部节点。把这套证明逻辑在脑子里过一遍比背代码有效得多。面试官如果追问“你怎么保证这个算法是对的”你能说出上面三句话基本就过关了。2.3 时间复杂度与空间复杂度为什么是 O(nm) 和 O(1)时间复杂度是 O(nm)这个结论几乎不用解释每轮循环只处理一个节点两个链表合计有 nm 个节点最多循环 nm 次。空间复杂度 O(1) 是很多人容易怀疑的点明明新建了一个dummy节点为什么不算 O(n)原因在于dummy是单个固定节点不随输入规模变大而变多。链表的绝大多数节点都是直接复用原链表的我们没有为它们申请新的内存。这与递归法不同递归每层调用都要占用一块栈帧最坏情况下递归深度等于两个链表的节点总数所以递归的空间复杂度是 O(nm)。这个差异在链表很长时非常明显也是我在工程中更推荐迭代法的核心理由。提示有些语言里你不需要真的new一个哨兵节点比如 C 里可以直接在栈上声明一个ListNode dummy;取地址dummy作为头。但 Python 里所有对象都在堆上写dummy ListNode()是最直接的等价方式。3. 递归法的精巧与代价什么场景才值得用3.1 递归写法的代码与直觉理解递归解法在 LeetCode 题解区永远有一席之地因为它真的太短了def mergeTwoLists(list1, list2): if not list1: return list2 if not list2: return list1 if list1.val list2.val: list1.next mergeTwoLists(list1.next, list2) return list1 else: list2.next mergeTwoLists(list1, list2.next) return list2怎么理解这段代码可以把mergeTwoLists(list1, list2)读作“返回一个以较小节点为头、内部已经完成合并排序的链表”。每次递归只解决一件事确定当前的头节点是谁。如果list1.val更小那么结果链表的头节点就是list1当前的节点它的next应该指向什么指向“合并list1.next和list2后的结果链表的头节点”。于是递归调用自己把规模缩小了一步。递归的终止条件是有一个链表为空这时直接返回另一个链表不需要做任何合并。这个思路优雅但不是零成本每层递归都要消耗栈空间且函数调用本身有开销。对于这道题nm 等于几千甚至几万时可能感觉不到差异但如果链表长度达到十万级递归深度过深可能导致栈溢出。这也是为什么《算法导论》里讲归并排序时强调递归版本适合教学实际大规模排序要用迭代版本。3.2 递归尾调用优化别被“尾巴递归”这两个字骗了有同学看到这个写法是“尾递归”就以为编译器会自动优化成循环空间复杂度会变成 O(1)。这里要泼盆冷水合并两个有序链表的递归写法虽然在逻辑上是尾调用——递归调用返回值直接被当前函数return——但在普通 Python 解释器里并不做尾调用优化。Python 官方在设计时就明确说过不打算支持尾递归消除因为这会牺牲栈回溯的调试能力。所以递归法在 Python 里的空间复杂度就是 O(nm)不是 O(1)。不过这个写法在某些函数式语言里确实可以被优化。如果你用 Haskell、Elixir 这类语言刷题尾递归优化后空间复杂度会和迭代法一样。但面试场景下如果你用 Python 或 Java选递归法就要做好“背 O(nm) 空间”的觉悟并主动向面试官说明。你主动说那是你清楚代价你不说等面试官追问那就是基础不扎实。3.3 递归与迭代到底该选谁我个人给出的选择建议是这样的如果只是为了解题拿最快速度写出来递归法确实省事因为不需要维护指针状态逻辑更接近人类的“分而治之”直觉。如果链表规模可能很大或者这是工程代码的一部分迭代法更稳妥因为空间占用确定是常数级而且不会因为数据量增长触发栈溢出。额外提醒一点LeetCode 的默认测试用例规模一般比较温和所以递归法在平台上跑也能过。但真实业务里谁也不敢保证线上数据不会突然变成一条十个节点的链表——不反过来谁也不敢保证它不会变成一条一千万节点的链表。工程上我会默认选迭代法。4. 原地合并法不申请新节点也能完成合并的指针艺术4.1 “原地”到底意味着什么重新理解指针复用的边界前面提到的迭代法虽然只新建了一个哨兵节点时间复杂度也是 O(1) 额外空间但它毕竟动用了dummy这个“新”节点。原地合并法要求更高连哨兵节点都不新建直接在两个输入链表上通过调整next指针完成合并最后返回两条链表中头节点值更小的那一个作为结果头节点。实现方式并不复杂核心是维护三个指针l1、l2和cur。l1和l2分别指向两条链表中尚未合并的第一个节点cur指向已经合并好的结果链表的尾部。每次比较l1.val和l2.val把较小者接到cur.next然后对应的指针前进。最后同样是把剩余部分链接上。区别在于初始时cur不指向哨兵而是指向None我们需要特殊处理结果链表的头节点。代码可以这么写def mergeTwoListsInPlace(list1, list2): if not list1: return list2 if not list2: return list1 # 确定结果链表的头节点 if list1.val list2.val: head list1 list1 list1.next else: head list2 list2 list2.next cur head while list1 and list2: if list1.val list2.val: cur.next list1 list1 list1.next else: cur.next list2 list2 list2.next cur cur.next if list1: cur.next list1 if list2: cur.next list2 return head你有没有发现这个代码和带哨兵节点的迭代法几乎一模一样只是把“哨兵节点”换成了“先手动确定头节点”的几步。所以有些面试官会问原地合并和带哨兵的迭代法本质区别是什么答案其实很微妙——两者都不创建额外链表都复用了原有节点唯一区别是哨兵节点方案多了一个临时节点而原地方案用一次判断替代了哨兵。从空间复杂度看它们都是 O(1)从代码风格看哨兵方案更统一从“抠门”程度看原地方案更能体现对指针的掌控力。4.2 三种解法的对比从工程、面试、扩展性三个维度看这里我整理了一张表建议你收藏起来面试前快速扫一眼维度迭代法哨兵递归法原地合并法代码长度短最短中等时间复杂度O(nm)O(nm)O(nm)空间复杂度O(1)O(nm)O(1)是否需要新节点1个哨兵节点不需要不需要出错难易程度低低中面试官印象稳巧指针功底扎实工程上我更推荐迭代法原因很简单哨兵节点让代码无需单独处理头节点为空的情况逻辑分支更少后期维护起来不容易漏边界。面试时如果你想展示自己对链表的控制力可以在迭代法讲完以后主动说“如果要求不使用额外节点我可以改写成原地版本只是需要先处理一下头节点的确定逻辑。”这比一上来就写原地版本更稳妥——万一你在处理头节点的几个分支里写漏了面试官会直接看到。4.3 原地合并法的潜在陷阱头节点处理与空链表原地合并法的第一个潜在陷阱是两个输入链表都为空这时直接返回None。上面的代码开头已经用两个if处理了空链表所以后面可以放心比较list1.val和list2.val。第二个陷阱是在确定head时有些初学者会把head和cur混在一起写结果头节点没接上返回了一个子链表。这里的关键是一旦确定了head就要立即让对应的l1或l2指针前进一位否则头节点会被重复接入形成环。第三个陷阱是循环结束后忘记接尾部。比如list1提前走完此时list2还剩一大截如果你不把cur.next list2加上结果链表就断了。很多人在白板上写代码时容易漏掉这两行因为觉得“循环结束了不就行了吗”——不是的剩余节点是整个链表的组成部分必须显式接上。我习惯在写完循环后立刻补上两个if把它当成固定动作就像写文件时一定记得close()一样。注意合并时如果直接修改了list1和list2的节点next指针原链表的结构就被破坏了。如果调用方后续还要使用原始链表这种写法会导致数据丢失。面试时一定要确认题意是否允许修改原链表。5. 面试变形题与深度追问从合并两个到合并K个5.1 合并K个有序链表分治合并与优先队列的两条路线LeetCode 21 最常见的变形是 LeetCode 23“合并K个有序链表”。刚把两个链表的合并练熟你会怎么处理 K 个最朴素的做法是每次拿一个链表和结果链表做两两合并总共做 K-1 次时间复杂度是 O(K × N)其中 N 是所有链表节点的总数——因为第一轮要比较 K 个链表的头节点第二轮变成 K-1 个平均复杂度偏高。更优的做法有两种分治合并和优先队列。分治合并的思路是把 K 个链表两两配对每对用“合并两个有序链表”的方法合并成一条然后继续两两配对直到剩一条。这样每一轮需要合并的链表数量减半总共进行 logK 轮复杂度降为 O(N log K)。写成代码时基本的两个链表合并函数就是 LeetCode 21 的解法直接复用。优先队列的思路更直接把所有链表的头节点放进一个小顶堆每次从堆顶弹出最小的节点接到结果链表的尾部然后把该节点的next推入堆中。堆的大小为 K所以每次操作是 O(log K)总共 N 次操作总复杂度同样是 O(N log K)。面试官通常希望你说出这两种方案并比较优劣优先队列代码更简洁但需要额外的堆空间分治合并空间取决于递归深度。这道变形题可以算是检验你对 LeetCode 21 是否真正理解的试金石因为它的核心操作仍然是“比较两个节点值并推进指针”。5.2 链表中判断有序性、去重、反转与合并的组合拳刷题圈里特别爱把链表题组合起来考。比如面试官给你一个乱序链表让你先排序再去重最后反转输出——本质上就在考归并排序的合并步骤加链表反转。归并排序在链表上的实现正是递归地把链表拆成两半分别排序然后用“合并两个有序链表”的方法把两个有序子链表合起来。所以 LeetCode 21 不只是解题它是归并排序在链表上能跑起来的关键一环。再举个例子LeetCode 148“排序链表”要求 O(n log n) 时间复杂度和 O(1) 空间复杂度。你如果用归并排序递归实现栈空间会是 O(log n)严格来说是 O(log n) 而不是 O(1)。要实现真正的 O(1) 空间需要改成自底向上的迭代归并先从长度为1的子链表开始两两合并再合并长度为2的……每一轮合并子链表时用的正是“合并两个有序链表”。很多人做这题卡住不是不会归并排序的思想而是不会在链表上正确写“找到一个子链表的结尾并切开”这步操作。LeetCode 21 掌握得越熟练写 LeetCode 148 时就越顺手。5.3 面试追问清单这些问题你都能接住吗我把这几年在面试中遇到过的追问整理成了一份清单你可以用来自查如果两个链表中存在大量重复值你的比较操作还能不能保持稳定如果其中一个链表已经为空你的代码是否正确返回另一个链表而不产生额外的空节点如果用迭代法合并后原链表结构被破坏了你是否清楚哪些节点被移动、哪些节点仍属于原链表如果你的合并函数需要支持“不修改原链表”的语义你会怎么调整实现第4个问题最阴险。很多人的第一反应是“那就重新拷贝每个节点呗”但完整答案是新建一个哨兵节点和一个tail指针每次比较时新建一个值为较小者值的节点接到tail后面而不是把原节点接过去。这样原链表完全不受影响时间复杂度依然是 O(nm)空间复杂度变成 O(nm)。拷贝节点和移动节点是两种完全不同的合并语义面试官通过这一问就能看出你对链表内存模型的理解深度。6. 测试样例与调试心得用极端输入验证你的代码6.1 必跑的六组测试用例写完了三种解法怎么验证它们是对的我整理了几组必跑的测试样例你可以直接当作回归测试用例用用例编号list1list2期望输出1空空空2空[1, 2, 3][1, 2, 3]3[1, 3, 5]空[1, 3, 5]4[1, 2, 4][1, 3, 4][1, 1, 2, 3, 4, 4]5[1, 2, 3][4, 5, 6][1, 2, 3, 4, 5, 6]6[4, 5, 6][1, 2, 3][1, 2, 3, 4, 5, 6]第4个用例里的两个1和第5、6个用例重点验证循环结束后尾部拼接是否正确。很多人在第6组用例上翻车list2的头节点比list1的头节点小结果链表头节点来自list2如果你的原地合并版本头节点初始化写错了这一组用例立刻暴露问题。6.2 白板调试法画指针不画链表一个我强烈推荐的调试技巧不要画整条链表只画三个指针。在白板或草稿纸上把l1、l2、cur分别标在对应节点上每执行一行代码就更新一次指针位置。这样执行到循环体内部时你很容易发现某个指针没有前进、或者cur.next接错了节点。我自己刷这道题时养成的一个习惯是每次写完后用第4组用例走一遍完整流程数一数合并后的链表节点个数是否等于两个链表节点个数之和。如果数量对不上说明要么漏接节点要么形成了环。长度校验是链表题最重要的“金标准”比看十万个中间打印都管用。6.3 常见报错与解决速查表最后给你整理一张排查速查表覆盖我自己和身边同事刷题时遇到的高频问题现象可能原因解决办法返回结果是空链表返回了cur而不是dummy.next或head检查返回值是不是真正的头节点结果链表少了几个节点循环结束后没接剩余链表补上if list1: cur.next list1和if list2: cur.next list2程序进入死循环指针方向错误比如把list1 list1.next写成了list1.next cur仔细区分“移动指针”和“修改next指向”访问了None.val循环条件写成了while list1 or list2改成while list1 and list2空链表单独处理结果链表包含原链表之外的值节点拷贝逻辑写错把val以外的属性也复制了只处理val和next必要时检查是否有其他字段合并后原链表被破坏原地合并法直接改动了节点指针如果调用方需要原链表改用新建节点版本这些坑我在带新人时见过无数次几乎每个人都至少踩过其中两个。提前把这张表贴在你刷题笔记本的首页能节省你大把的调试时间。7. 写在最后从“会写代码”到“讲清楚代码”刷 LeetCode 21 很容易陷入一种错觉代码跑通了这题就会了。但面试时真正拉开差距的是你能不能讲清楚“为什么”。为什么用哨兵节点为什么循环条件是while list1 and list2为什么最后可以直接拼接剩余链表这三个问题能答得流畅你对链表的理解就已经超过大多数只背题解的人。我个人的习惯是刷这道题时同时写三个版本然后对比它们的空间复杂度和代码可读性。在工程里我会选迭代法因为它的 O(1) 空间和清晰的循环结构最适合放进生产代码在面试里我会先讲迭代法再拿递归法展示思路的简洁如果面试官追问再补充原地合并版的改动点。这套“由稳到巧”的展示节奏几乎百试百灵。如果你现在正在准备面试建议你把这道题当成一个起点顺着它去刷 LeetCode 23合并K个有序链表、LeetCode 148排序链表、LeetCode 86分隔链表和 LeetCode 143重排链表。你会发现它们都在反复使用同一个动作比较两个节点、接指针、移动指针。把 LeetCode 21 吃透后面这些题的核心逻辑你就已经会了一半。