1. 这道题到底是什么从一个高频面试题说起如果不是刷题的人第一次看到“合并两个有序链表”可能会觉得奇怪链表是个啥有序链表又要怎么合并其实这个题目在算法题库里编号21属于链表类型里最常被拿来当“人生第一题”的入门题。它做的事情一句话就能讲清楚给你两个已经按从小到大排好序的链表把它们合并成一个新的、依然按从小到大排序的链表最后返回合并后链表的头节点。听起来很简单对吧但就这么一道看似不起眼的题背后其实藏着好几个面试官真正想考的东西你对指针操作熟不熟你对“头节点可能变”这件事有没有概念你知不知道什么时候用迭代、什么时候用递归以及你有没有处理空链表这种极端情况的下意识。很多后来的链表难题比如合并K个有序链表、链表版归并排序、甚至一些环形链表变体底层都在反复使用这道题的思想。所以我经常跟准备面试的朋友说这道题刷明白链表题型差不多就通了一半。这篇文章适合几类人看。第一类是刚接触数据结构、准备系统补链表知识的学生第二类是马上要面试、想把高频题吃透的求职者第三类是日常写业务代码但偶尔要处理链表、想捡回基本功的工程人员。我会把两种主流解法迭代和递归都拆开讲连哨兵节点为什么要用、递归出口怎么想这种细节也一起说清楚最后还会带出几个高频变式比如合K个、链表归并排序、以及如果题目换成有序数组又该怎么办。2. 先理解解法选型为什么迭代和递归是两条主流路线2.1 合并的本质每次挑一个更小的节点挪过来先看一张“心理图”。假设有两个队伍每个队伍内部已经按个子高矮排好了队现在要把两队合成一队保持依然按个子高矮排队。最直观的做法是什么就是每次比较两个队最前面那个人谁矮谁先站到新队伍里然后那个队伍往前走一步。重复这个过程直到某一边空了把另一边剩下的人直接接在后面。链表合并完全一样。两个有序链表L1和L2各自维护一个指针指向当前还没被取走的头节点。每次比较两个指针所指节点的值谁小就把谁接到结果链表的尾部然后那个指针往后移动一步。这个过程持续到某一个指针为空最后把另一个链表剩下的部分直接拼上去。这个逻辑非常朴素但你把它写成健壮的代码会有两个细节必须处理好一是结果链表的头节点可能一开始是L1的头也可能是L2的头你要怎么优雅地处理这种“头不确定”的情况二是连接的时候指针的移动顺序错了链表就会断掉。这两个问题是这道题真正的考点也是后面很多链表题的死穴。2.2 为什么普遍推荐哨兵节点dummy node针对“头节点不确定”的问题业界有一个非常成熟的小技巧先造一个虚拟头节点叫它哨兵节点它的next一开始指向空然后让一个移动指针current从哨兵出发谁小就把谁挂在current后面然后current往前走。合并结束后返回的是dummy.next也就是真正的头节点。这个做法妙在哪里它让你完全不需要写“如果L1的头小返回L1的头否则返回L2的头”这种冗余分支。因为所有节点都是统一挂在current后面的头是谁的问题被天然规避了。我第一次自己写这道题的时候犯过一个特别蠢的错我用了head变量记录结果头但是合并过程中发现头可能是L1也可能是L2于是我在循环里写了两段几乎一样的代码最后还是因为一处更新漏了而Bug。用哨兵节点之后这种低级错误直接消失。哨兵节点不参与最终结果的数据它只是一个工具人但你几乎所有“头会变”的链表题里都能用到它比如链表反转、删除倒数第N个节点、两两交换节点都是同一个套路。2.3 另一条路递归用“子问题”的眼光看合并如果你不想用循环也可以从递归角度想这个问题。递归的思考方式和迭代不太一样迭代是“一步步做出来”递归是“我假设子问题已经解决只处理当前这一步”。具体到这道题假设L1的头节点小于L2的头节点那么合并后的结果头肯定是L1的头接下来需要做的事是什么是把L1.next和整个L2合并合并好了的结果作为L1.next的后续。于是就可以写成l1.next mergeTwoLists(l1.next, l2); return l1;。同理如果L2的头更小那就反过来。这个递归思路其实更接近数学归纳法先想清楚最小的情况也就是某个链表为空返回另一个链表然后想清楚递推关系即当前层只负责选一个更小头剩下交给递归去拼。递归写法代码很短很多刚学的人看了会觉得奇妙但真正面试的时候要小心一个问题如果测试用例给了一条很长的链表递归可能导致调用栈太深某些语言环境里会爆栈。所以实际项目中如果链表长度不可控迭代写法是更稳妥的选择。我在后面的章节会给你一个比较具体的取舍建议和适用范围说明。3. 手把手写代码迭代实现的完整过程3.1 定义好链表节点结构不管什么语言链表题第一步都是先把节点结构摆出来。以Python为例最常见定义长这样class ListNode: def __init__(self, val0, nextNone): self.val val self.next next这里val是节点存的值next是指向下一个节点的引用。后面所有的代码都基于这个结构。如果你用的是C语言对应的是结构体加指向结构体的指针用Java就是内部类加引用。思路完全一致只是语法不同。3.2 迭代解法的标准代码下面是Python版迭代实现也是我平时最推荐练习的版本def merge_two_lists(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) current dummy while l1 and l2: if l1.val l2.val: current.next l1 l1 l1.next else: current.next l2 l2 l2.next current current.next # 一边已经走完了把另一边剩余部分直接接上 current.next l1 if l1 else l2 return dummy.next这段代码里最需要注意的就三处。第一处是dummy ListNode(0)这个哨兵节点本身的值不重要后面也不会返回它。第二处是循环里的三行选中一个节点后先current.next 被选中的节点再把被选中链表的指针向后移动最后current current.next。这三条的先后顺序绝对不能乱。我见过有朋友把l1 l1.next写在current.next l1之前结果l1已经往后走了current.next却还指着原来的l1。虽然因为赋值顺序的原因可能碰巧没出问题但在更复杂场景里这就是断链的根源。第三处是循环结束后那句current.next l1 if l1 else l2它的作用是直接把还没走完的那个链表的剩余部分整体挂上去不需要再逐个遍历因为剩余部分本来就是有序的。3.3 为什么这个写法的时间和空间都是最优的时间复杂度方面两个链表每个节点都只会被访问一次总节点数设为m和n那整体就是O(mn)。这个复杂度是下界因为你要合并所有节点每个节点你总得看一眼。空间复杂度上迭代法除了几个指针和哨兵节点没有额外使用和输入规模相关的存储所以是O(1)。递归法的空间复杂度就有明显差别了它要占用O(mn)的调用栈空间在最坏情况下比如两条链表交替大小每个递归层都得往下压一层栈深度会达到mn。这也是我说工程里优先用迭代法的根本原因不是递归不好而是空间开销不划算。3.4 手写一个例子做逐步验证为了让你彻底放心我用一组小数据走一遍。假设L1是1 - 3 - 5L2是2 - 4 - 6。初始dummy - Nonecurrent指向dummy。第一步l1.val1l2.val21更小。current.next指向1节点l1移动到3current移动到1节点。此时结果链是dummy - 1。第二步l1.val3l2.val22更小。current.next指向2节点l2移动到4current移动到2节点。结果链是dummy - 1 - 2。第三步l1.val3l2.val43更小。current.next指向3节点l1移动到5current移动到3节点。结果链是dummy - 1 - 2 - 3。第四步l1.val5l2.val44更小。current.next指向4节点l2移动到6current移动到4节点。第五步l1.val5l2.val65更小。current.next指向5节点l1变成空current移动到5节点。此时while条件不再满足l1已经为空于是执行current.next l1 if l1 else l2l2里还有6节点直接接在5后面。最终结果链1 - 2 - 3 - 4 - 5 - 6。完美。4. 递归解法拆解短代码背后的严谨逻辑4.1 递归出口为什么要优先考虑“空链表”递归法写起来非常短但新手最容易在“出口”上卡住。出口就是递归结束的条件在这道题里非常直观如果L1为空就不用再比较了直接返回L2如果L2为空直接返回L1。这个出口一旦缺失递归就会一直调用下去直到栈溢出。为什么这个出口是天然正确的因为一个空链表和一个非空链表合并结果就是那个非空链表本体不需要做任何改动。哪怕两个都空随便返回哪一个返回的都是空链表也正确。所以出口不用写得复杂两条if就够。4.2 递推公式让子问题帮你干活递推公式是这个样子的如果L1头节点更小那合并结果的头是L1的头剩下的工作是“把L1.next和L2这两个链表合并结果接在L1头后面”。文字写出来像绕口令用代码反而清楚def merge_two_lists(l1: ListNode, l2: ListNode) - ListNode: if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next merge_two_lists(l1.next, l2) return l1 else: l2.next merge_two_lists(l1, l2.next) return l2注意看递归调用返回的是“合并完成的链表头”直接赋给当前的next这一步把子问题的结果接到了当前节点后面。这个思想是我只决策当前这一步选谁后续所有节点都由递归帮我排好。4.3 递归 vs 迭代面试现场怎么选经常有朋友问我两种写法都学会了面试时候写哪个比较好我的建议是先想清楚再说别一上来就写。如果你的面试官比较传统或者你担心递归栈空间的讨论引来追问直接写迭代最稳妥。如果面试官问“还能不能优化有没有别的思路”你再秀出递归写法顺势说出“递归风格清晰但空间O(mn)迭代空间O(1)”这种对比通常会加分。还有一个现实考量如果你在工程中写链表代码链表长度没准儿有多大递归栈溢出风险是真实存在的。所以我对工作党更推荐迭代作默认写法递归作为理解工具和面试展示用法。两种都要会但出手选迭代这是我个人的经验。5. 实操对比测试什么样的用例能帮你看清代码对不对5.1 一组必测的边界用例清单写完代码怎么验证对不对千万别只拿一个常规用例跑一遍就算完事。链表题最大的坑就是边界条件我总结了一个最小测试集你拿这道题去跑跑过就基本稳了用例编号L1输入L2输入期望输出主要考察点1空空空双空链表2空1 - 21 - 2L1为空31 - 2空1 - 2L2为空41 - 21 - 21 - 1 - 2 - 2相等值节点51 - 32 - 41 - 2 - 3 - 4常规交替合并6121 - 2单节点合并71 - 5 - 92 - 31 - 2 - 3 - 5 - 9长度不对称第2和第3是很多人会忽略的用例。代码里如果忘了处理“某一边先走完”的情况很可能会在循环结束后去访问空指针的val直接报错。第4个用例专门验证相等值的处理我代码里用的是所以相等的节点会优先取L1这没问题如果你用那就会优先取L2结果上也对唯一要注意的是要保持判断一致。5.2 调试链表题的一个实用技巧链表题调试起来比数组麻烦因为你没法直接打印整个链表。我最常用的小技巧是写一个辅助的链表转列表函数方便在小样本下打印结果def linked_list_to_list(head): result [] while head: result.append(head.val) head head.next return result然后配合一个构造链表的函数把数组转成链表就能用普通测试框架跑断言了def list_to_linked_list(arr): dummy ListNode(0) current dummy for val in arr: current.next ListNode(val) current current.next return dummy.next这两个辅助函数看着不起眼实际刷链表题的时候能给你省很多事。把用例跑过去以后再顺手验证一下极端情况比如一万个节点交替大小确认迭代法不爆栈心里就踏实了。6. 考点外延从这道题能串起哪些更复杂的链表题6.1 变式一合并K个有序链表很多面试官不会止步于“两个”他会追问如果给你K个有序链表呢这就是LeetCode第23题的样子。最直白的思路是每次从K个链表的头里选最小的那个接上K个链表都维护一个指针。这样时间复杂度O(KN)N是所有节点总数。为什么因为每选一个节点都比较K次。更好一点的做法是利用优先队列堆把K个链表的头放进小根堆每次弹出最小的节点然后再把该节点的next入堆。这样选一个节点的时间是O(logK)整体O(NlogK)。这个方案相当常用而且堆里存的是“链表节点”而非“值”你需要给堆指定比较规则因为节点本身不能直接比大小。在Python里可以用heapq加元组或者在节点类里实现比较方法。这一问能明显拉开面试差距它的基础就是这道合并两个有序链表的比较逻辑。6.2 变式二链表版归并排序你可能听说过归并排序的核心就是“分治”加“合并”。数组版很好写链表版其实更贴合归并排序的本质。给一个无序链表排序第一步用快慢指针找中点把链表切成两半第二步递归排序左半和右半第三步用这道题学到的合并逻辑把两个有序链表串起来。没有额外数组存储只需要改指针空间复杂度可以做到O(logN)这也是链表比数组更适合归并排序的地方。这个变式把快慢指针、递归、合并三个知识点放在一道题里是综合题典型考法。你能独立完成它说明合并两个有序链表已经内化成了基础能力而不是只会背代码。6.3 变式三如果是合并两个有序数组呢面试官还可能把链表换成数组来考比如给你两个有序数组要合并成一个有序数组但要求原地操作、不额外开大数组。这时候思路就反过来了从数组的尾巴往前面填。先把两个数组的有效长度加起来然后从后往前比较把较大的数字放到末尾空出的位置。为什么从后往前因为从前往后填会把还没处理的值覆盖掉丢失数据。从后往前填天然避开了这个问题每个元素都能安全落位。这个变式提醒了一件事同样叫“合并”链表和数组的操作方式完全不同。链表靠改指针数组靠移动元素位置。你能快速在这两种数据结构之间切换思维说明真正理解了这里的核心逻辑而不是只会照着模版敲。7. 常见问题与排查技巧实录7.1 指针丢失链表题最大的Bug来源我见过太多人写完链表题跑测试用例时发现结果链只有一半节点或者干脆形成一个环。十次里有八次都是指针丢失。什么叫指针丢失就是你在把当前节点的next指向新节点时没有先保存原本的下一个节点导致原来的链后半段找不到了。在这道题里指针丢失的高危操作是当你执行current.next l1之后紧接着应该移动l1到l1.next但如果你移动的是current或者忘记移动l1下一次循环就会把同一个节点再挂一次结果链里出现重复节点或者循环。我的建议是每写完一次指针操作就口头问自己一句我是不是把“当前链表那个指针”和“结果链那个指针”搞混了一句话保命。7.2 死循环和环的隐患还有一种低概率但极其隐蔽的问题如果两条链表里有一个节点它的next指回了自己无序链表里正常不会出现但某些测试数据会故意构造循环就会永远出不来。虽然有序链表合并这道题理论上不会出现环但面试时你可以顺嘴提一句“如果输入有环需要先用快慢指针检测环”这是加分的细节。它说明你不只会调标准输入还考虑到了异常数据的影响。7.3 面试现场的节奏建议以我模拟面试见过的情况来说这道题最容易翻车的不是写不出来而是上来就埋头写代码。很多候选人直接写迭代写对了但面试官问他为什么要用哨兵节点、不用行不行、空间复杂度多少他就有点卡壳。我的建议是先说思路讲讲合并的核心动作是“每次选小的”说说哨兵节点的作用然后写代码写完主动说复杂度和边界测试。整个过程大概四五分钟却比闷头写二十分钟印象分高得多。8. 最后再分享一个实际中的体会我在带新人或者帮朋友改代码时经常发现一个规律凡是链表题容易出错的人往往在写之前没有先在纸上画一画“这个节点指向谁、那个指针现在在哪个节点上”。链表题和数组题完全不同数组的索引你一眼能看到边界链表全靠指针在走你不画出过程出问题几乎是必然的。所以我的习惯动手前先画两三个节点的示意。不需要画多复杂把节点之间的指向画清楚代码写起来就顺很多。如果你是从零开始学这道题我的建议是第一遍照着迭代思路手写写完跑那七条测试用例第二遍不看代码自己用递归思路再写一遍第三遍再想想K个链表怎么合并。三遍下来这道题就真正沉淀成你自己的东西了。往后再遇到链表反转、链表排序、两两交换你会发现它们都有一个共同的味道弄清楚指针前后关系剩下的就是比较和赋值的事情。# 博文示例Markdown 格式1. 这道题到底是什么从一个高频面试题说起如果不是刷题的人第一次看到“合并两个有序链表”可能会觉得奇怪链表是个啥有序链表又要怎么合并其实这个题目在算法题库里编号21属于链表类型里最常被拿来当“人生第一题”的入门题。它做的事情一句话就能讲清楚给你两个已经按从小到大排好序的链表把它们合并成一个新的、依然按从小到大排序的链表最后返回合并后链表的头节点。听起来很简单对吧但就这么一道看似不起眼的题背后其实藏着好几个面试官真正想考的东西你对指针操作熟不熟你对“头节点可能变”这件事有没有概念你知不知道什么时候用迭代、什么时候用递归以及你有没有处理空链表这种极端情况的下意识。很多后来的链表难题比如合并K个有序链表、链表版归并排序、甚至一些环形链表变体底层都在反复使用这道题的思想。所以我经常跟准备面试的朋友说这道题刷明白链表题型差不多就通了一半。这篇文章适合几类人看。第一类是刚接触数据结构、准备系统补链表知识的学生第二类是马上要面试、想把高频题吃透的求职者第三类是日常写业务代码但偶尔要处理链表、想捡回基本功的工程人员。我会把两种主流解法迭代和递归都拆开讲连哨兵节点为什么要用、递归出口怎么想这种细节也一起说清楚最后还会带出几个高频变式比如合K个、链表归并排序、以及如果题目换成有序数组又该怎么办。保证你读完既能上手写代码又能在面试现场把思路讲明白。2. 先理解解法选型为什么迭代和递归是两条主流路线2.1 合并的本质每次挑一个更小的节点挪过来先看一张“心理图”。假设有两个队伍每个队伍内部已经按个子高矮排好了队现在要把两队合成一队保持依然按个子高矮排队。最直观的做法是什么就是每次比较两个队最前面那个人谁矮谁先站到新队伍里然后那个队伍往前走一步。重复这个过程直到某一边空了把另一边剩下的人直接接在后面。链表合并完全一样。两个有序链表L1和L2各自维护一个指针指向当前还没被取走的头节点。每次比较两个指针所指节点的值谁小就把谁接到结果链表的尾部然后那个指针往后移动一步。这个过程持续到某一个指针为空最后把另一个链表剩下的部分直接拼上去。这个逻辑非常朴素但你把它写成健壮的代码会有两个细节必须处理好一是结果链表的头节点可能一开始是L1的头也可能是L2的头你要怎么优雅地处理这种“头不确定”的情况二是连接的时候指针的移动顺序错了链表就会断掉。这两个问题是这道题真正的考点也是后面很多链表题的死穴。2.2 为什么普遍推荐哨兵节点dummy node针对“头节点不确定”的问题业界有一个非常成熟的小技巧先造一个虚拟头节点叫它哨兵节点它的next一开始指向空然后让一个移动指针current从哨兵出发谁小就把谁挂在current后面然后current往前走。合并结束后返回的是dummy.next也就是真正的头节点。这个做法妙在哪里它让你完全不需要写“如果L1的头小返回L1的头否则返回L2的头”这种冗余分支。因为所有节点都是统一挂在current后面的头是谁的问题被天然规避了。我第一次自己写这道题的时候犯过一个特别蠢的错我用了head变量记录结果头但是合并过程中发现头可能是L1也可能是L2于是我在循环里写了两段几乎一样的代码最后还是因为一处更新漏了而Bug。用哨兵节点之后这种低级错误直接消失。哨兵节点不参与最终结果的数据它只是一个工具人但你几乎所有“头会变”的链表题里都能用到它比如链表反转、删除倒数第N个节点、两两交换节点都是同一个套路。2.3 另一条路递归用“子问题”的眼光看合并如果你不想用循环也可以从递归角度想这个问题。递归的思考方式和迭代不太一样迭代是“一步步做出来”递归是“我假设子问题已经解决只处理当前这一步”。具体到这道题假设L1的头节点小于L2的头节点那么合并后的结果头肯定是L1的头接下来需要做的事是什么是把L1.next和整个L2合并合并好了的结果作为L1.next的后续。于是就可以写成l1.next mergeTwoLists(l1.next, l2); return l1;。同理如果L2的头更小那就反过来。这个递归思路其实更接近数学归纳法先想清楚最小的情况也就是某个链表为空返回另一个链表然后想清楚递推关系即当前层只负责选一个更小头剩下交给递归去拼。递归写法代码很短很多刚学的人看了会觉得奇妙但真正面试的时候要小心一个问题如果测试用例给了一条很长的链表递归可能导致调用栈太深某些语言环境里会爆栈。所以实际项目中如果链表长度不可控迭代写法是更稳妥的选择。3. 手把手写代码迭代实现的完整过程3.1 定义好链表节点结构不管什么语言链表题第一步都是先把节点结构摆出来。以Python为例最常见定义长这样class ListNode: def __init__(self, val0, nextNone): self.val val self.next next这里val是节点存的值next是指向下一个节点的引用。后面所有的代码都基于这个结构。如果你用的是C语言对应的是结构体加指向结构体的指针用Java就是内部类加引用。思路完全一致只是语法不同。3.2 迭代解法的标准代码下面是Python版迭代实现也是我平时最推荐练习的版本def merge_two_lists(l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) current dummy while l1 and l2: if l1.val l2.val: current.next l1 l1 l1.next else: current.next l2 l2 l2.next current current.next # 一边已经走完了把另一边剩余部分直接接上 current.next l1 if l1 else l2 return dummy.next这段代码里最需要注意的就三处。第一处是dummy ListNode(0)这个哨兵节点本身的值不重要后面也不会返回它。第二处是循环里的三行选中一个节点后先current.next 被选中的节点再把被选中链表的指针向后移动最后current current.next。这三条的先后顺序绝对不能乱。我见过有朋友把l1 l1.next写在current.next l1之前结果l1已经往后走了current.next却还指着原来的l1。虽然因为赋值顺序的原因可能碰巧没出问题但在更复杂场景里这就是断链的根源。第三处是循环结束后那句current.next l1 if l1 else l2它的作用是直接把还没走完的那个链表的剩余部分整体挂上去不需要再逐个遍历因为剩余部分本来就是有序的。3.3 为什么这个写法的时间和空间都是最优的时间复杂度方面两个链表每个节点都只会被访问一次总节点数设为m和n那整体就是O(mn)。这个复杂度是下界因为你要合并所有节点每个节点你总得看一眼。空间复杂度上迭代法除了几个指针和哨兵节点没有额外使用和输入规模相关的存储所以是O(1)。递归法的空间复杂度就有明显差别了它要占用O(mn)的调用栈空间在最坏情况下比如两条链表交替大小每个递归层都得往下压一层栈深度会达到mn。这也是我说工程里优先用迭代法的根本原因不是递归不好而是空间开销不划算。3.4 手写一个例子做逐步验证为了让你彻底放心我用一组小数据走一遍。假设L1是1 - 3 - 5L2是2 - 4 - 6。初始dummy - Nonecurrent指向dummy。第一步l1.val1l2.val21更小。current.next指向1节点l1移动到3current移动到1节点。此时结果链是dummy - 1。第二步l1.val3l2.val22更小。current.next指向2节点l2移动到4current移动到2节点。结果链是dummy - 1 - 2。第三步l1.val3l2.val43更小。current.next指向3节点l1移动到5current移动到3节点。结果链是dummy - 1 - 2 - 3。第四步l1.val5l2.val44更小。current.next指向4节点l2移动到6current移动到4节点。第五步l1.val5l2.val65更小。current.next指向5节点l1变成空current移动到5节点。此时while条件不再满足l1已经为空于是执行current.next l1 if l1 else l2l2里还有6节点直接接在5后面。最终结果链1 - 2 - 3 - 4 - 5 - 6。完美。4. 递归解法拆解短代码背后的严谨逻辑4.1 递归出口为什么要优先考虑“空链表”递归法写起来非常短但新手最容易在“出口”上卡住。出口就是递归结束的条件在这道题里非常直观如果L1为空就不用再比较了直接返回L2如果L2为空直接返回L1。这个出口一旦缺失递归就会一直调用下去直到栈溢出。为什么这个出口是天然正确的因为一个空链表和一个非空链表合并结果就是那个非空链表本体不需要做任何改动。哪怕两个都空随便返回哪一个返回的都是空链表也正确。所以出口不用写得复杂两条if就够。4.2 递推公式让子问题帮你干活递推公式是这个样子的如果L1头节点更小那合并结果的头是L1的头剩下的工作是“把L1.next和L2这两个链表合并结果接在L1头后面”。文字写出来像绕口令用代码反而清楚def merge_two_lists(l1: ListNode, l2: ListNode) - ListNode: if not l1: return l2 if not l2: return l1 if l1.val l2.val: l1.next merge_two_lists(l1.next, l2) return l1 else: l2.next merge_two_lists(l1, l2.next) return l2注意看递归调用返回的是“合并完成的链表头”直接赋给当前的next这一步把子问题的结果接到了当前节点后面。这个思想是我只决策当前这一步选谁后续所有节点都由递归帮我排好。理解了这个你以后再遇到“反转链表”的递归版、“归并排序”的递归版都能用同一套眼光去看。4.3 递归 vs 迭代面试现场怎么选经常有朋友问我两种写法都学会了面试时候写哪个比较好我的建议是先想清楚再说别一上来就写。如果你的面试官比较传统或者你担心递归栈空间的讨论引来追问直接写迭代最稳妥。如果面试官问“还能不能优化有没有别的思路”你再秀出递归写法顺势说出“递归风格清晰但空间O(mn)迭代空间O(1)”这种对比通常会加分。还有一个现实考量如果你在工程中写链表代码链表长度没准儿有多大递归栈溢出风险是真实存在的。所以我对工作党更推荐迭代作默认写法递归作理解工具和面试展示用法。两种都要会但出手选迭代这是我个人的经验。5. 实操对比测试什么样的用例能帮你看清代码对不对5.1 一组必测的边界用例清单写完代码怎么验证对不对千万别只拿一个常规用例跑一遍就算完事。链表题最大的坑就是边界条件我总结了一个最小测试集你拿这道题去跑跑过就基本稳了用例编号L1输入L2输入期望输出主要考察点1空空空双空链表2空1 - 21 - 2L1为空31 - 2空1 - 2L2为空41 - 21 - 21 - 1 - 2 - 2相等值节点51 - 32 - 41 - 2 - 3 - 4常规交替合并6121 - 2单节点合并71 - 5 - 92 - 31 - 2 - 3 - 5 - 9长度不对称第2和第3是很多人会忽略的用例。代码里如果忘了处理“某一边先走完”的情况很可能会在循环结束后去访问空指针的val直接报错。第4个用例专门验证相等值的处理我代码里用的是所以相等的节点会优先取L1这没问题如果你用那就会优先取L2结果上也对唯一要注意的是要保持判断一致。5.2 调试链表题的一个实用技巧链表题调试起来比数组麻烦因为你没法直接打印整个链表。我最常用的小技巧是写一个辅助的链表转列表函数方便在小样本下打印结果def linked_list_to_list(head): result [] while head: result.append(head.val) head head.next return result然后配合一个构造链表的函数把数组转成链表就能用普通测试框架跑断言了def list_to_linked_list(arr): dummy ListNode(0) current dummy for val in arr: current.next ListNode(val) current current.next return dummy.next这两个辅助函数看着不起眼实际刷链表题的时候能给你省很多事。把用例跑过去以后再顺手验证一下极端情况比如一万个节点交替大小确认迭代法不爆栈心里就踏实了。6. 考点外延从这道题能串起哪些更复杂的链表题6.1 变式一合并K个有序链表很多面试官不会止步于“两个”他会追问如果给你K个有序链表呢最直白的思路是每次从K个链表的头里选最小的那个接上每选一个节点都比较K次。全部合并完需要O(KN)时间N是所有节点的总数。更好一点的做法是利用优先队列堆把K个链表的头放进小根堆每次弹出最小的节点然后再把该节点的next入堆。这样选一个节点的时间是O(logK)整体O(NlogK)。这个方案相当常用而且堆里存的是“链表节点”而非“值”你需要给堆指定比较规则因为节点本身不能直接比大小。这一问能明显拉开面试差距它的基础就是这道合并两个有序链表的比较逻辑。6.2 变式二链表版归并排序你可能听说过归并排序的核心就是“分治”加“合并”。数组版很好写链表版其实更贴合归并排序的本质。给一个无序链表排序第一步用快慢指针找中点把链表切成两半第二步递归排序左半和右半第三步用这道题学到的合并逻辑把两个有序链表串起来。没有额外数组存储只需要改指针空间复杂度可以做到O(logN)这也是链表比数组更适合归并排序的地方。这个变式把快慢指针、递归、合并三个知识点放在一道题里是综合题典型考法。你能独立完成它说明合并两个有序链表已经内化成了基础能力而不是只会背代码。6.3 变式三如果是合并两个有序数组呢面试官还可能把链表换成数组来考比如给你两个有序数组要合并成一个有序数组但要求原地操作、不额外开大数组。这时候思路就反过来了从数组的尾巴往前面填。先把两个数组的有效长度加起来然后从后往前比较把较大的数字放到末尾空出的位置。为什么从后往前因为从前往后填会把还没处理的值覆盖掉丢失数据。从后往前填天然避开了这个问题每个元素都能安全落位。这个变式提醒了一件事同样叫“合并”链表和数组的操作方式完全不同。链表靠改指针数组靠移动元素位置。你能快速在这两种数据结构之间切换思维说明真正理解了这里的核心逻辑而不是只会照着模版敲。7. 常见问题与排查技巧实录7.1 指针丢失链表题最大的Bug来源我见过太多人写完链表题跑测试用例时发现结果链只有一半节点或者干脆形成一个环。十次里有八次都是指针丢失。什么叫指针丢失就是你在把当前节点的next指向新节点时没有先保存原本的下一个节点导致原来的链后半段找不到了。在这道题里指针丢失的高危操作是当你执行current.next l1之后紧接着应该移动l1到l1.next但如果你移动的是current或者忘记移动l1下一次循环就会把同一个节点再挂一次结果链里出现重复节点或者循环。我的建议是每写完一次指针操作就口头问自己一句我是不是把“当前链表那个指针”和“结果链那个指针”搞混了一句话保命。7.2 死循环和环的隐患还有一种低概率但极其隐蔽的问题如果两条链表里有一个节点它的next指回了自己无序链表里正常不会出现但某些测试数据会故意构造循环就会永远出不来。虽然有序链表合并这道题理论上不会出现环但面试时你可以顺嘴提一句“如果输入有环需要先用快慢指针检测环”这是加分的细节。它说明你不只会调标准输入还考虑到了异常数据的影响。7.3 面试现场的节奏建议以我模拟面试见过的情况来说这道题最容易翻车的不是写不出来而是上来就埋头写代码。很多候选人直接写迭代写对了但面试官问他为什么要用哨兵节点、不用行不行、空间复杂度多少他就有点卡壳。我的建议是先说思路讲讲合并的核心动作是“每次选小的”说说哨兵节点的作用然后写代码写完主动说复杂度和边界测试。整个过程大概四五分钟却比闷头写二十分钟印象分高得多。8. 最后再分享一个实际中的体会我在带新人或者帮朋友改代码时经常发现一个规律凡是链表题容易出错的人往往在写之前没有先在纸上画一画“这个节点指向谁、那个指针现在在哪个节点上”。链表题和数组题完全不同数组的索引你一眼能看到边界链表全靠指针在走你不画出过程出问题几乎是必然的。所以我的习惯动手前先画两三个节点的示意。不需要画多复杂把节点之间的指向画清楚代码写起来就顺很多。如果你是从零开始学这道题我的建议是第一遍照着迭代思路手写写完跑那七条测试用例第二遍不看代码自己用递归思路再写一遍第三遍再想想K个链表怎么合并。三遍下来这道题就真正沉淀成你自己的东西了。往后再遇到链表反转、链表排序、两两交换你会发现它们都有一个共同的味道弄清楚指针前后关系剩下的就是比较和赋值的事情。