1. 问题拆解与链表前置知识1.1 为什么这道题是链表操作的必修课先说结论力扣热题100里的第21题“合并两个有序链表”是几乎所有刷题路线图都会放在链表专题早期的一道题。如果你刚开始刷力扣或者链表题总是写不顺这道题值得认真过三遍以上。这道题的核心需求很简单给定两个升序排列的链表把它们合并成一个新的升序链表并返回。这里有个关键约束题目要求我们直接操作原链表节点而不是新建节点复制值。这意味着你没法偷懒写一个“把两个链表的值都取出来排序再重建”的方案必须从指针层面去理解节点的拼接。我见过太多人一开始就卡在“用迭代法写出来了但边界处理不对”“递归解法看着优雅但自己写不出来”这两种状态上。说到底都是因为对链表这个数据结构缺乏“指针视角”的直觉。链表跟数组最大的不同在于数组你可以用下标随意访问任意位置链表你只能顺着next一个一个走。这种“只能往前走不能回头”的特性决定了链表的操作思路和数组完全不同。这道题让我想到生活中的一个场景你手里有两副已经按大小排好的扑克牌现在要合成一副依然有序的牌。最自然的做法就是每次比较两副牌最上面那张小的那张先放进新牌堆然后继续比较。链表的合并思路跟这个一模一样只是“牌堆顶部”换成了“当前指针指向的节点”。作为一个常年在算法题里摸爬滚打的人我的建议是不要急着背解题代码先强迫自己用手在纸上画链表。画三到五个节点的链表模拟指针一步步移动的过程把每一轮比较、每一次指针改动的结果都画出来。这个“画图驱动理解”的方法比看十遍题解都管用。1.2 读懂题目隐含的三个信息很多初学者拿到这道题之后第一反应是“这不就是把两个链表串起来吗”但真正写起来才发现处处是坑。这里我把题目里没有明说、但直接影响代码正确性的隐含信息拆开讲一讲。第一个隐含信息两个链表可能为空。题目描述里通常会说“如果两个链表都为空返回空链表如果一个为空返回另一个”。但很多人在写代码的时候会忘记这个前提上来就访问head1.val直接抛空指针异常。所以我的习惯是任何链表题第一行就处理空指针判断不给边界留机会。第二个隐含信息两个链表本身有序但并不知道哪个链表的当前节点更小。有的题目会明确说L1和L2都是升序但并不会告诉你哪个链表的头节点更小。所以你必须每走一步都比较两个链表的当前节点值而不是“先串完一个链表再串另一个”。第三个隐含信息合并后的链表要保持稳定性不能破坏原有的大小关系。虽然这道题没有明确说“相等元素谁先谁后”但面试官普遍默认期望稳定合并也就是当两个节点值相等时优先取L1的节点。这个细节在面试中容易被追问记住了会显得你考虑问题更全面。以上三个信息其实对应了三种常见的错误写法忘记判空、错误地先串完一条链、相等时随意选择。把这三个坑提前记住你写的代码会比大多数人的更稳。2. 核心方法详解与实操要点2.1 迭代解法从头到尾的指针接力迭代法应该是大多数人最先掌握的写法。思路很直白用两个指针分别指向L1和L2的当前节点用一个哨兵节点dummy作为新链表的前置头节点然后不断比较两个指针指向的值把较小的节点接到tail后面同时让对应指针前进一步。这里哨兵节点的使用非常关键。为什么需要一个dummy节点因为合并后的链表头节点是不确定的——可能是L1的头节点也可能是L2的头节点。如果你不借助哨兵节点就得单独处理“新链表为空时的首次插入”这种特殊逻辑。有了dummy节点所有节点都是“在tail后面追加”代码结构一下就统一了。def mergeTwoLists(l1, l2): dummy ListNode(-1) 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 is not None else l2 return dummy.next注意最后一行的处理逻辑循环退出时说明至少有一个链表走到了尽头。这时不需要再逐个比较了直接把另一个链表剩余的部分整体接上即可。因为两个链表本身有序剩余的节点天然都是有序的整体接上不会破坏整个链表的顺序。这段代码我建议你亲手写至少三遍。第一遍对着题解抄写第二遍盖住代码自己写第三遍在纸上画出dummy、tail、l1、l2四个指针的变化过程。等你能把四个指针的位置都画清楚迭代法这一关就算过了。2.2 递归解法把问题“缩小”的智慧递归解法在思路上更优雅但也是很多人第一次接触时觉得“懂了但写不出来”的典型。递归的核心逻辑其实只有一句话当前哪个头节点更小就选它作为结果链表的头然后让它指向“剩余两个链表合并的结果”。这句话听起来有点绕我换个方式讲。假设你拿到两个链表你要做的第一件事是确定合并后链表的头节点是谁。比较L1的头和L2的头小的那个就是整个合并结果的头。假设L1的头更小那么合并结果的头就是L1当前这个节点。这个节点后面应该接什么呢应该接“L1.next和L2合并后的结果”。所以你把原问题转化成了一个规模更小的问题合并L1.next和L2。这就是递归的神奇之处你在解决大问题时已经默认小问题可以以相同的方式解决。def mergeTwoLists(l1, l2): if not l1: return l2 if not 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递归的终止条件就是某一条链表为空。一旦L1为空直接返回L2L2为空直接返回L1。这跟迭代法里最后一行“把剩余链表整体接上”的思想完全一致只是表达方式不同。我要特别提醒一个初学者容易犯的错递归函数内部千万不能新建节点而是直接在原链表节点上修改next指针。有些学生担心“递归会不会把原链表弄丢”其实不会因为每次递归只修改一个节点的next指向而且修改之前已经把剩下的部分通过递归调用解决了。这种“先处理子问题再拼接当前节点”的顺序保证了不会丢失后续节点。2.3 两张解法对比到底该用哪一种很多人刷题时会有个执念总想找到“最优写法”。但实际上面试和笔试场景里两种写法都能被接受关键看你能否把逻辑讲清楚。我直接给个对比表方便你对照着理解。对比维度迭代法递归法时间复杂度O(nm)O(nm)空间复杂度O(1)只用了常数额外指针O(nm)递归调用栈深度代码量8~10行5~8行理解门槛低贴近直觉较高需要理解子问题划分适合场景实际开发、内存敏感场景面试展示思维深度、函数式风格如果从纯工程角度说迭代法明显更优因为递归在极端情况下的调用栈空间不可忽视。比如两个链表各有5000个节点递归深度会达到10000层在部分默认栈较小的运行环境里甚至可能直接栈溢出RecursionError。而迭代法完全不担心这个问题这也是我在项目里绝不使用递归去遍历链表的根本原因。但在面试场景里我会建议你两种都熟练掌握。面试官如果已经看过你写了迭代法往往会在追问环节换个口吻问一句“能用递归实现一下吗”这时候你要是支支吾吾写不出来前面展示的好印象就得打折扣。反过来如果你先用递归写面试官追问迭代法那就是送分题。所以我给你的建议是以迭代法作为兜底方案递归法作为加分技能两个都要练。3. 边界条件与复杂度推导3.1 四种边界情况的现场模拟链表题最抓狂的地方永远在边界。我第一次写这道题时自以为逻辑天衣无缝结果Run的瞬间就被空链表用例教做人了。这四种边界情况我不希望你再用一次提交去试错。第一种两个链表都为空。返回None即可这是最简单的边界。第二种L1为空L2非空。正确返回值是L2而不是新建一个链表。因为题目要求合并如果其中一个为空另一个本身就是合并结果直接返回即可。第三种L1非空L2为空。同理返回L1。第四种两个链表都不为空但所有L1节点值都小于L2节点值。这种情况下代码会先把L1全部串完然后L1变成None循环退出最后把整个L2整体接到tail后面。这要求“最后整体拼接剩余部分”的逻辑必须正确很多人在这个分支上写错比如把tail.next指向了None。我在教学中总结了一个检验边界是否想清楚的小技巧写完代码后不要急着提交先在注释里写下这四行空链表 空链表空链表 非空链表非空链表 空链表某条链表全部节点都更小每一条都问自己一个问题现在我的代码走的是哪个分支返回值是什么如果四个分支都答得出来这题就稳了。3.2 时间复杂度和空间复杂度到底怎么算这道题的复杂度推导其实很有意思也非常适合面试口述。先说时间复杂度。假设L1有n个节点L2有m个节点。合并过程中每轮比较只处理一个节点要么把L1的当前节点接入新链表要么把L2的当前节点接入新链表。所以循环最多执行nm次时间复杂度就是O(nm)。这里有个容易混淆的点当一条链表先走到尽头时剩余的另一条链表会整体接入不再额外比较。这部分的操作是O(1)级别的指针赋值不是逐节点复制。所以整体时间复杂度不会超过O(nm)更准确地说当其中一个链表为空时可以做到O(min(n,m))但通常在大O表示法里直接说O(nm)就可以了。再看空间复杂度这是两种解法的分水岭。迭代法全程只用了dummy、tail、l1、l2这几个指针额外空间是O(1)。递归法不一样每层递归都会占用一块栈空间最大递归深度取决于两条链表的长度总和nm所以空间复杂度是O(nm)。在力扣的题解区你会看到很多人强调“迭代法的空间复杂度优于递归”这个结论的理论依据就在这里。当然在实际面试过程中口述复杂度不需要背公式你只要说清楚“每个节点最多被访问一次所以时间O(nm)迭代只用了固定指针空间O(1)递归调用栈会随链表长度增长空间O(nm)”就足够了。能够用自己的语言把复杂度的来龙去脉讲清楚比背诵标准答案有价值得多。3.3 不创建新节点的意义在哪里题目明确要求不创建新节点这个限制值得展开几句。细想一下如果允许新创建链表这道题就会变得非常“数组化”新建一个链表遍历两个原链表每次都new一个节点并赋值。代码写起来也挺顺但完全没有链表操作的感觉。这道题刻意加了这个限制就是想逼你学会“改变指向”。链表的核心操作从来不是“创建”而是“断开和连接”。你要理解节点之间的next关系是灵活可变的就像调整链条的扣环一样。把一个节点从原链表中取下、接续到新链表的尾部是通过修改指针完成的不需要复制任何值。从工程角度看这也是链表的实际价值所在。在内存敏感的场景里如果每次合并都要创建新节点意味着额外申请了一大块内存。而原地合并只改指针不申请新内存效率高得多。这种“改指针而不是新建数据”的思路在操作系统内核、内存池设计、垃圾回收算法等底层系统里尤其常见。4. 实操过程记录与表述优化4.1 从暴力思路到最优解的心路变迁很多人在刚接触这道题时先想到的是最暴力的解法遍历两个链表把值全部取出来放进数组排序再创建新链表。我承认这个思路毫无逻辑错误甚至时间复杂度都是O((nm)log(nm))放在小规模数据上完全能跑。但为什么我们不推荐这种写法第一它破坏了题目的“原地合并”约束如果是在面试中写出来面试官多半会直接追问“能不能用O(1)空间完成”。第二它让你完全错失了链表操作最有价值的部分——指针修改。第三从拓展性来说暴力解法没有任何可以迁移到其他链表题上的skills而迭代法和递归法是后续很多中等难度链表题的基础。我记得自己刚开始刷题时也干过这种傻事取出来排序确实省事但刷到后面发现完全不行。比如“K个升序链表合并”这道困难题用“取出来排序”的思路去套你会发现自己压根不知道该怎么高效地处理K个链表的中途变化。而如果你从一开始就用“两两合并”的思路后面这道困难题就能自然迁移了。这里给个实操建议刷题时给自己立个规矩——如果一道题要求原地操作比如原地合并、原地反转就算你能用额外空间写出正确答案也要尝试写一个不使用额外空间的版本。长期下来你的指针操作思维能力会有质的提升。4.2 测试用例设计与本地验证流程在力扣上提交代码前我强烈建议你先在本地跑一遍自己的测试用例。很多人在线提交失败后才开始找bug既浪费时间又打击信心。这里我分享一套适合链表的自测流程。第一步准备测试数据。我通常写三个测试函数构造链表、打印链表、释放链表如果是C/C。构造链表的代码很简单从一个数组创建单向链表。打印链表则是把每个节点的值打印出来方便肉眼核对。这些辅助函数虽然不起眼却是所有链表题的公共基础设施建议直接做成模板。第二步跑基础用例。至少要包括普通有序链表合并、空链表与非空链表的合并、两个等长链表合并、一个链表长度远大于另一个、两个链表完全相等的情况。第三步跑随机测试。Python里可以生成大量随机数组排序后构造链表再调用你的merge函数最后断言合并后的链表确实有序。这个随机测试的思路不只适用于这道题几乎所有链表题都能用。以下是我常用的随机测试模板import random def random_list(length): arr sorted(random.randint(0, 100) for _ in range(length)) dummy ListNode(-1) tail dummy for v in arr: tail.next ListNode(v) tail tail.next return dummy.next for _ in range(1000): l1 random_list(random.randint(0, 20)) l2 random_list(random.randint(0, 20)) merged mergeTwoLists(l1, l2) values [] while merged: values.append(merged.val) merged merged.next assert values sorted(values), fFailed: {values}跑完1000组随机测试还没出错你的代码正确性基本就板上钉钉了。这个习惯可能看起来有些繁琐但对刷题效率的提升非常明显——你在线提交前就消除了大量低级bug留下的时间可以去琢磨更难的题目。4.3 力扣在线编辑器的小技巧力扣的在线编辑器上手很简单但还是有几个细节值得一提。第一默认的语言模板里会给出ListNode的类定义你不需要重复定义直接在Solution类里写方法即可。第二如果要在本地调试记得自己把ListNode类补充上否则会报NameError。第二点经常被忽略力扣的测试用例是自动构造链表的你不需要关心如何从输入数组构造。但本地调试不同你得自己写构造函数。我建议把以下几段代码存成自己的工具片段随用随取class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def build_list(values): dummy ListNode(-1) tail dummy for v in values: tail.next ListNode(v) tail tail.next return dummy.next def print_list(head): res [] while head: res.append(head.val) head head.next print(res)另外力扣的定位日志或者调试控制台适合用来输出中间变量的值。如果你实在找不到bug可以在循环里print一下l1.val、l2.val和tail.val看看指针的移动是否符合预期。不少题目代码逻辑很绕靠眼睛找不出bug但一打印马上就能定位问题。5. 面试现场的高频追问与做题心态5.1 面试官最爱追问的五个问题这道题在面试中出现的概率极高稀奇的是很多人只会刷题却答不好面试官追加的追问。这里我把最常见的五个追问整理出来每个都给出参考思路。追问一“如果一个链表为空你的代码会怎么样”这是考你对边界条件的理解。参考回答是如果L1为空返回L2如果L2为空返回L1两个都为空返回None。追问二“你的递归解法会爆栈吗”这是考空间复杂度的理解。参考回答递归深度取决于较长链表的节点数在数据量极大的情况下递归调用栈可能溢出论工程稳健性迭代法更好。追问三“能不能不用递归也不用dummy哨兵节点写一版”别慌这道题的迭代写法如果不借助dummy会比较麻烦但也不是不能写。你需要单独处理“链表头是L1还是L2”的问题。这个追问主要看你是否能从不同角度拆解问题。建议平时把这个无dummy的版本也练习一遍以防面试官突然要求。追问四“如果这个题要求保证稳定性相等元素怎么处理”参考回答当l1.val l2.val时优先取L1的节点。这样从原链表视角看相等元素的相对顺序不会改变满足稳定合并的要求。追问五“两个链表已经有序为什么不能直接把A链表的尾部接到B链表的头部”这是最常见的误区因为L1和L2是“各自有序”不代表把L1的所有节点都放在L2所有节点之前仍然整体有序。比如L1最大值可能是100L2最小值可能是1直接相接得到1,2,3,…,100,200,…,但开头却可能是100之后接1序列就乱套了。把这些追问提前准备到位面试时如果你能对答如流对整体评价绝对加分。5.2 编码现场最容易出现的三个手误我做了几年技术面试官见过无数候选人在白板上写这道题。说实话真正会写的人不需要想太久反而是那些“知道思路但手跟不上”的人容易犯三种低级错误。第一种手误把tail.next和tail搞混。很多人写着写着把“更新l1指针”和“更新tail指针”混在一起导致某个节点被跳过去了。解决办法是在写的时候盯着三个变量看当前比较的l1、当前比较的l2、新链表的尾节点tail。每一步都问自己一句哪个指针要前进是不是该更新tail了第二种手误循环条件写错。最常见的错误是写成while l1.next and l2.next这样会导致最后一个节点不被处理合并结果少一个节点。正确写法是while l1 and l2只要两个链表的当前节点都存在就要继续比较。第三种手误返回值写错。要么是return tail要么是return dummy这两种都是错的。应该返回dummy.next因为dummy是哨兵节点dummy.next才是合并后链表的真正头节点。我在教学生时经常说一句话哨兵节点就是“虚拟头”你在最后一定要绕过它。5.3 刷题路上的心态建设最后我想聊一点形而上的东西。很多人刷力扣热题100总想一口气刷完遇到这道题觉得简单就直接跳过觉得“我会了”。但实际上链表题只看不练是非常容易眼高手低的。我见过太多人面试时“我知道思路但写不出来”根因就是练得太少。我自己的习惯是一道简单题至少有三种做法时才算出关一种是标准解法另一种是带着限制条件的解法比如不用递归、不用dummy第三种是能够扩展到相似题的通用解法。比如这道题标准解法是迭代递归扩展情形就是“合并K个有序链表”。平时做一道简单题我会顺手把它的中等、困难扩展题搜出来看一眼不求马上做出来但至少知道它们之间的联系。说到底刷leetcode不能只追求AC率。AC只是起点理解背后的数据结构本质和边界处理思想才是关键。合并两个有序链表这道题虽然是力扣热题100里最简单的一档但它渗透出来的指针操作、递归划分、边界控制、复杂度推导这些能力会陪伴你一直到后面几十道链表题。我个人在实际项目里最常用到的反而是这道题里“哨兵节点”的思想。无论是实现一个双向链表缓存淘汰算法还是在系统代码里拼接日志链dummy节点这个技巧都能帮你省掉大量判空的重复代码。也正因为这样每次我带着新人刷题都会要求他们把这道题放在链表专题的第一位。扎实过一遍后面会少走很多弯路。