LeetCode HOT100 里的链表题我印象最深的反而不是反转链表而是这道 21 题——合并两个有序链表。它看起来简单代码甚至能缩到十行以内但恰恰是这种“简单题”在面试里最能暴露一个人对指针、边界条件和递归过程的真实理解程度。如果你正在准备算法面试或者刚刷到链表专题这道题值得停下来多琢磨一会儿。这篇文章我把递归解法、迭代解法、常见的坑、调试技巧以及它背后的扩展题串起来讲一遍争取让你刷完这题之后连“合并K个有序链表”也能顺手拿下。先给题目定性输入两个升序链表 l1 和 l2输出一个新的升序链表返回它的头节点。新链表本质上是把原来两个链表中的节点重新串联而不是新建 val 副本看清这点很重要因为不少人在写题时会不知不觉违背这个约束。1. 为什么合并两个有序链表值得反复刷1.1 面试里真正想考的东西很多人吐槽这题“太简单了”不值得花时间。但真到了面试现场这题却是链表专题里出现频率最高的几道之一。原因很简单它考的不是你能不能背出答案而是你对链表结构的底层直觉。面试官问你“会写归并排序的链表版本吗”你说会然后他让你先写一个 merge 函数这时候很多人就卡住了。合并两个有序链表正是归并排序在链表结构上的核心子过程。你能不能在几分钟内写出一个不犯错、能处理边界、能解释指针移动逻辑的版本直接决定了后续更复杂题目的成败。我见过不少候选人代码能跑通但问他“为什么这里要返回 dummy.next”答不上来问他“递归版本的空间复杂度是多少”说是 O(1)。这类回答一出来基本等于告诉面试官这题是背的。所以这题值得反复刷不是为了这道题本身而是为了把链表这种数据结构彻底想明白。1.2 链表题的前置知识看清ListNode长什么样说句实话很多人在链表题上栽跟头不是不会写逻辑而是对 ListNode 这个结构本身缺乏体感。链表节点可以理解成火车车厢每节车厢装着一个数字val还挂着一根钩子next钩子指向下一节车厢。你要合并两列火车不是把数字抄一遍而是把车厢之间的钩子重新挂好。在 LeetCode 环境里节点定义通常是这样的class ListNode: def __init__(self, val0, nextNone): self.val val self.next next每个节点只有两个核心字段val 和 next。链表本身没有一个独立的“头对象”你拿到手的就是第一个节点的引用。这意味着只要你把某个节点的 next 指向了另一条链上的节点后面的一整串节点就被带过来了不需要逐个复制。这个特性既是链表题方便的地方也是出 bug 最频繁的地方——因为指针一旦指错整条链的关系就乱了。2. 递归解法十几行代码背后是一场指针接力2.1 递归思考先找到最小子问题递归解法的核心不是从头到尾模拟合并过程而是问自己一个问题mergeTwoLists(l1, l2) 这个函数它到底要返回什么答案是返回合并后链表的头节点。那么站在当前这一步如果 l1.val 比 l2.val 小头节点必然是 l1 的当前节点。头节点确定后剩下的问题就变成了——把 l1.next 和 l2 合并再把合并结果挂到 l1.next 上。这一步想通了递归代码就呼之欲出class Solution: 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注意这里的递归出口如果 l1 为空说明左边走完了剩下整条 l2 直接作为结果返回反之亦然。这个出口语句看着简单却是整道题最容易漏掉的部分——一旦漏了函数会一路 next 到 None 再访问 val直接报空指针异常。2.2 用 [1,2,4] 和 [1,3,4] 完整走一遍递归过程只看代码不演练很难建立直观感受。我拿题目的标准示例走一遍。初始链表l1 1→2→4l2 1→3→4。第一次调用两个 val 都是 1不满足 l1.val l2.val走 else 分支。这时头节点确定为 l2 的 1然后递归调用 mergeTwoLists(l1, l2.next)也就是 1→2→4 和 3→4 去合并。第二次调用1 3走 if 分支取 l1 的 1递归合并 2→4 和 3→4。第三次2 3取 l1 的 2递归合并 4 和 3→4。第四次4 3取 l2 的 3递归合并 4 和 4。第五次两个 val 都是 4走 else取 l2 的 4递归合并 4 和 None。这时 l2 是 None触发递归出口返回 l1 剩下的 4。然后开始回溯每个“return l1 / return l2”把刚才确定好的头节点逐层交还给上一层上一层再把它挂到自己的 next 上。最终拼成的链是 1→1→2→3→4→4。这个过程很像一场接力赛每一层递归只确定一个头节点剩下的交给下一层等下一层跑完再把接力棒接回来。2.3 递归的代价空间不是 O(1)递归版本最大的迷惑性就是看起来只用了一个函数好像没开额外空间。但实际每递归一层系统都要在调用栈上压入当前函数的状态。最坏情况下合并两个长度分别为 n 和 m 的链表递归深度能达到 nm所以空间复杂度是 O(nm)。这在面试里是个经典追问点。你可以这样回答面试官递归写法代码优雅、可读性强适合讲解思路但它会消耗 O(nm) 的调用栈空间如果链表很长比如十万个节点会有栈溢出风险。想做到严格的 O(1) 空间就得用迭代写法。这也是为什么我建议两种解法都要熟练掌握而不只是背一种。3. 迭代解法哨兵节点是链表题的万金油3.1 为什么合并结果需要dummy头节点迭代解法的思路更贴近“人怎么合并两列有序车厢”就是拿两个指针分别指向 l1 和 l2 的当前节点不断比较 val把较小的那个节点从原链上“拆下来”接到结果链上。但这里有个小麻烦合并后的链头到底是 l1 的头还是 l2 的头在循环前无法确定。如果不做处理通常要写一堆 if-else 单独判断第一次挂节点的情况代码会很啰嗦。这时候就该请出哨兵节点也叫 dummy 节点你先创建一个不算数的节点挂在结果链最前面让所有操作都统一成“往 cur.next 后面挂节点”最后返回 dummy.next 就是真正的头。这个技巧在链表题里出现频率极高反转链表、删除倒数第 N 个节点、合并 K 个链表全都能用上。3.2 迭代代码逐行拆解class Solution: def mergeTwoLists(self, 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逐行看。dummy ListNode(-1) 只是占位它的 val 可以是任意值反正最后返回时会跳过他。cur 开始时指向 dummy之后永远指向结果链的尾节点。进入 while 循环条件是 l1 和 l2 同时不为空。只要有一条链走完了循环就退出因为剩下的部分不需要再逐个比较——它本身就是有序的直接整段接上即可。循环内部如果 l1.val l2.val就把 l1 的当前节点接到 cur.next 上同时 l1 指针后移一位否则接 l2 的节点l2 后移。注意这里用了 而不是 也就是说当两个节点值相等时优先取 l1 的节点。这对最终结果的正确性没有影响因为合并后只要求整体升序不要求“原链表元素的相对顺序保持不变”。循环体最后cur cur.next 把 cur 移到新接入的节点上保证下次挂接的位置是链尾。循环结束后最多只剩一条链还有节点。此时 cur.next l1 if l1 else l2 把整段剩余链挂上来再返回 dummy.next完成。这个写法把边界情况收得很干净l1 或 l2 一开始就是空链表也能正确处理因为 while 循环根本不进入直接返回另一条完整链。3.3 递归与迭代怎么选我把两种解法的关键差异整理成一张表面试前可以反复对照着看维度递归解法迭代解法时间复杂度O(nm)O(nm)空间复杂度O(nm)O(1)代码可读性高逻辑简洁中等需要理解哨兵套路主要风险调用栈溢出指针后移遗漏造成死循环面试官追问点为什么空间不是 O(1)为什么需要 dummy 节点我的建议是面试中先讲递归版本快速表达“我理解了子问题结构”当面试官追问空间复杂度时再自然切换到迭代版本。这样既能展示思路的多样性也能体现对工程细节的敏感度。实际工程里如果链表规模不可控我几乎都会选迭代版本因为 O(1) 空间在嵌入式、移动端这类内存敏感环境下是硬指标。4. 链表的坑都一样我踩过的四个版本4.1 每次提交都错在哪这道题我前前后后刷过很多遍也看过周围不少人写总结下来有四个反复出现的错误版本。第一个错误循环结束后没有接剩余链。这种写法在两条链长度相等时能碰巧通过但只要有一条链更长输出就会丢失后半截节点。根本原因是没有理解“剩余段本来就是有序的整体接上即可”这条核心性质容易把问题想复杂试图用 while 循环继续比较已经为空的链表。第二个错误只移动了 cur忘记移动 l1 或 l2。代码里最容易出现这种漏写比如 cur.next l1 之后忘了 l1 l1.next。结果就是同一个节点被反复接入形成环最后提交时直接超时。这类 bug 在本地跑一遍小例子可能发现不了因为链表很短时看起来像是对的但输出长度会莫名其妙地不对。第三个错误return dummy 而不是 dummy.next。这个属于理解层面的失误。dummy 是自己造的占位节点谁也没说过它是结果链的一部分。返回 dummy 会把一个 val 为 -1 的假节点带出来。我在给朋友 review 代码时看到过好几次基本都是“我明明把所有节点都挂对了为什么输出前面多了一个数”的困惑。第四个错误为了省事新建节点而不是复用节点。比如在循环里每次 new 一个 ListNode(node.val) 再拼接。这样做在 LeetCode 判题机上通常也能过返回的链表内容和预期一致但它违背了题目“由原链表拼接而成”的要求而且凭空增加了 O(nm) 的内存分配。在面试中这么写面试官一眼就能看出你对指针操作不够自如。链表题的核心魅力就是“改指针、复用节点”如果放弃这个优势还不如直接去合并数组。4.2 一套好用的链表调试方法链表题调试起来比数组麻烦得多因为很多环境没法直观展示链式结构。我自己习惯写一个极简的打印函数把链表转成数组字符串def print_list(head): res [] while head: res.append(str(head.val)) head head.next print( - .join(res) if res else None) # 用法示例 l1 ListNode(1, ListNode(2, ListNode(4))) l2 ListNode(1, ListNode(3, ListNode(4))) merged Solution().mergeTwoLists(l1, l2) print_list(merged) # 1 - 1 - 2 - 3 - 4 - 4遇到死活跑不对的情况我强烈建议在循环里多打几行现场信息比如每次接入节点后打印当前 l1、l2、cur 的 val 和 next。链表题最怕“脑内模拟”因为指针状态一多人脑很快就跟不上了。用打印还原现场通常几步就能定位是哪个指针没动、哪个节点被重复挂了。4.3 边界用例清单除了功能用例我还建议每道链表题都备一套固定边界用例做回归场景输入期望输出两链为空l1None, l2NoneNone单链为空l1None, l21→2→31→2→3一长一短l11→5, l22→3→4→61→2→3→4→5→6全部相等l11→1, l21→11→1→1→1逆序输入l15→3, l24→2非升序结果基于错误前提不在讨论范围特别提醒链表题的输入约定非常依赖“升序链表”这个前提。如果面试官给的输入不保证有序上面的合并逻辑就不能直接套用需要先排序。这也是为什么我总说读题时先确认前提条件比急着写代码更重要。5. 举一反三从两链表到K个有序链表5.1 最直接的思路两两合并学会合并两个链表之后最容易想到的扩展题就是“合并 K 个升序链表”。最朴素的做法是把第 1 个和第 2 个合并再把结果和第 3 个合并一直合到第 K 个。代码写起来几乎不用动脑复用 mergeTwoLists 就行。但复杂度需要算清楚假设每个链表平均长度为 n每合并一次都要遍历当前结果链的所有节点第一次合并后结果长度大约是 2n第二次再和长度为 n 的链表合并要遍历 3n累计起来就是 O(k^2 n) 的时间。这个复杂度在 k 比较大或 n 比较大时完全不可接受面试里如果只给出这个方案基本只能算“有思路”离“好答案”还有距离。5.2 分治法把复杂度降下来更优的思路是分治把 K 条链表两两配对合并。比如 8 条链表第一轮合并成 4 条第二轮合并成 2 条第三轮合并成 1 条。每一轮每个节点被访问一次总共有 log k 轮所以时间复杂度是 O(n k log k)。这个方案的好处是空间可控而且不需要引入复杂数据结构。分治法代码可以复用现成的 mergeTwoLists按区间递归或迭代合并都行class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]: if not lists: return None def merge_two(a, b): dummy ListNode(-1) cur dummy while a and b: if a.val b.val: cur.next a a a.next else: cur.next b b b.next cur cur.next cur.next a if a else b return dummy.next step 1 while step len(lists): for i in range(0, len(lists) - step, step * 2): lists[i] merge_two(lists[i], lists[i step]) step * 2 return lists[0]如果你在面试中先写了 O(k^2 n) 的暴力合并面试官大概率会让你继续优化。能接出分治法这道扩展题就算过关了。5.3 最小堆空间换时间另一种经典方案是用最小堆优先队列。思路是每次从 K 个链表的当前头节点里选出最小值接到结果链上然后把该链表的下一个节点压回堆里。这样每个元素进堆、出堆各一次每次操作 O(log k)总复杂度 O(n k log k)和分治法同阶。写 Python 时要注意一个细节堆里直接存 ListNode 是没法比较的因为节点类型没有定义小于号。常见做法是存三元组 (val, index, node)其中 index 是链表编号用来打破平局避免堆去比较后面的 node 对象import heapq class Solution: def mergeKLists(self, lists: List[Optional[ListNode]]) - Optional[ListNode]: dummy ListNode(-1) cur dummy heap [] for i, node in enumerate(lists): if node: heapq.heappush(heap, (node.val, i, node)) 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这个版本的优点是实现起来套路固定不太容易出错缺点是空间复杂度升到 O(k)因为堆里最多同时存 K 个节点。如果面试对空间有严格限制分治法会更有优势。5.4 同类的变式延伸合并两个有序链表这题往下还能延伸出不少相关题目。比如合并两个有序数组本质类似但因为数组不能原地随意插入通常需要从后往前填充以节省空间。再比如链表的归并排序第一步就要写链表切分找中点第二步就是这题的 merge 操作。又比如两数相加同样用到了“遍历两个链表并处理进位”的指针推进思路。所以我经常把这题比作链表专题的“敲门砖”。面试官想考察你对链表的掌控程度很多时候不会直接出一道难题而是从这种最基础的两两合并开始逐步加码。你能不能在基础题上给出干净、正确、能解释边界条件的回答往往决定了他后续要不要跟你聊更难的内容。我自己的练法是每过两三个月就回头把这题重写一遍递归、迭代各写一次并合上屏幕口头把两种写法的复杂度说一遍。这么做不需要太久但能防止自己对链表的手感退化。毕竟真正到了面试或线上排障的时候最怕的就是明明做过却因为细节生疏而卡壳。最后再分享一个小技巧如果你在看这题时觉得“我都能默写出来了不需要练了”那就试着给完全没学过链表的朋友讲一遍讲的时候逼迫自己想清楚每个指针为什么要这样移动。讲明白了才是真明白。
