力扣第21题“合并两个有序链表”在链表题里属于入门但又极其经典的模型。很多刷题的人第一眼觉得这题简单真正手写时却总在指针移动、空链表处理、递归返回这些细节上卡住。我见过不少刚接触链表的同学上来就背迭代或递归模板结果换个题目照样不会。其实这题的核心价值是把“链表遍历、指针移动、节点拼接”这三个动作一次性讲清楚。无论你用C、Java还是Python都值得亲手写几遍再把自己的思路讲出来。这篇文章我就从题面拆起把迭代与递归两种主流解法的实现细节、常见坑位、同类扩展题目都过一遍当作一份可以直接参考的刷题笔记。1. 题目到底在问什么先把题面吃透1.1 两条有序链表长什么样力扣21题的输入是两个升序链表例如1 - 2 - 4和1 - 3 - 4要求把它们合并成一条新的升序链表结果是1 - 1 - 2 - 3 - 4 - 4。很多人第一次看到返回值是 ListNode 就有点蒙因为题目在网页上展示的是数组风格[1,2,4]和[1,3,4]但实际在代码里你拿到的并不是数组而是一个已经构造好的 ListNode 对象每个节点只有val和next两个字段。链表的天然特性是只能从头节点开始沿着next方向单向遍历不能像数组一样随机访问也不能直接调用排序函数。合并两个有序链表的核心动作就是同时遍历这两条链表每次从两条链表的当前位置中挑出值更小的那个节点接到结果链表的尾部然后继续往后走。整个过程和“合并两个有序数组”的思路很像但链表的特点在于你操作的是节点指针而不是下标。1.2 返回值与链表操作的本质题目要求返回合并后的链表头节点。注意这里的返回值应该是一个 ListNode而不是数组或者其他容器。链表的“头节点”就是第一个有效数据节点。很多人在本地调试时习惯打印一串数字但在力扣上你返回的是链表头判题系统会沿着next不断遍历比较你返回结果和期望结果是否每个节点的值都一致。这题本质上考的是“穿针引线”的能力结果链表不需要从零创建全新的节点而是直接复用输入的节点只是调整它们的next指向。比如输入1 - 2和3 - 4合并过程可以把2的next指向3这样结果就是1 - 2 - 3 - 4。你在过程中没有new任何新节点只是改变了一些节点的指向。这一点很重要因为如果每合并一个节点就new一个新节点虽然也能得到正确顺序但空间复杂度会从 O(1) 变成 O(n)并且失去了这道题关于链表指针操作的训练意义。1.3 从热词反推的常见理解偏差我在刷题社区里看到不少和“链表”相关的热词比如“循环单链表”“不带头结点的单链表”“链表插入”“逆置链表”等说明很多人基础概念还没理顺就急着做题。在这道题里力扣给出的链表是不带头结点的普通链表也就是说第一个节点就存有效数据没有单独的哑节点。如果你习惯了自己定义链表时带一个头结点做题时就要特别注意函数返回的应当是真数据节点而不是一个空的哨兵节点。另一个常见误区是觉得“合并两个有序链表”需要先新建一个空链表然后把两个链表的值一个个复制进去。这在逻辑上没错但实现起来绕且浪费。正确做法是让返回值直接指向两条输入链表中较小那个头节点然后通过指针不断串联。理解到这个层面后面看迭代和递归代码都会顺畅很多。2. 两种主流解法迭代和递归选哪个2.1 迭代法用哨兵节点省掉一半判断迭代法的写法非常固定基本是“三指针”结构一个哨兵节点 dummy一个游标指针 cur以及两个分别指向 l1 和 l2 当前节点的指针。每次比较 l1.val 和 l2.val把较小的节点接到 cur.next然后让那个链表的指针前进一位同时让 cur 也前进一位。循环结束后如果某条链表还有剩余节点直接把它整个接到结果链表的尾部。为什么用哨兵节点因为结果链表的头节点在循环开始前是未知的你总得知道最终合并后的第一个节点是谁。如果没有哨兵你通常要先判断 l1 和 l2 哪个值更小单独处理第一个节点再进入循环。这样代码会多出一个 if而且更容易漏边界。哨兵节点的 val 可以随便给比如 0 或者 -1它不会被返回最后返回的是 dummy.next。ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur dummy; while (l1 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 ? l1 : l2; return dummy.next; }这段代码里l1 l2是循环条件意味着只要有一条链表走完了循环就停止。最后用cur-next l1 ? l1 : l2接上剩余部分。这个写法很简洁但新手容易漏掉最后一步。你可以这样理解循环结束时两条链表中可能还有一条没走完因为剩下的每个节点都已经比另一条链表的剩余节点小或者另一条已经为空所以直接把整条剩余链表挂到结果后面即可。2.2 递归法把“合并”拆成“当前最小节点子问题”递归写法更短但理解门槛稍高。核心思路是合并 l1 和 l2只需要先找出两个头节点中较小的那个让它的 next 指向“合并剩余部分”的结果然后返回这个较小节点。比如 l1 1-3l2 2-4因为 1 小于 2所以合并后的头是 l1 的这个 1 节点而 l1.next 应该指向mergeTwoLists(3-None, 2-4)的结果。递归不断缩小规模直到某一条链表为空直接返回另一条链表。递归终止条件就是 l1 为空或者 l2 为空。这个条件非常关键因为如果没有终止条件递归会无限调用下去最终栈溢出。由于函数每次只处理一个头节点递归深度最多是两条链表的总长度。在力扣这种在线判题环境里测试链表长度一般不会深到栈溢出但如果你实际工作中处理几万、几十万节点的链表就要谨慎用递归。def mergeTwoLists(self, l1, l2): 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注意这里修改了原链表节点的 next 指向。递归返回的是“已经合并好的链表头”所以l1.next self.mergeTwoLists(l1.next, l2)这句话是把 l1 的 next 指向后续合并结果。许多人第一次写递归时会尝试返回一个新建链表但这里你会发现直接复用原节点更符合链表题的气质代码也更省。2.3 复杂度与适用场景对比两种解法的时间复杂度都是 O(mn)因为每条链表的每个节点最多被比较一次。空间复杂度有差别迭代法是 O(1)只用了几个指针递归法是 O(mn)因为每次调用都会占用一层系统栈。看起来迭代法更优但递归法的优势在于代码和思路更贴近“自顶向下”的分解方式更容易写对。我在实际刷题和面试中给出一个建议如果目标就只是为了过题两种都可以如果目标是训练工程思维建议优先写迭代法因为它不依赖额外栈空间并且更接近你后续写复杂链表操作时的真实手感。不过递归法能加深你对“子问题”的理解比如后面做合并 K 个有序链表时分治写法就和递归思想一脉相承所以两者都值得练。解法时间复杂度额外空间复杂度代码简洁度推荐场景迭代 哨兵O(mn)O(1)中工程实现、面试稳妥递归O(mn)O(mn)高理解分治、速写题解3. 代码实现与逐行拆解3.1 C 实现理解指针与哨兵先看完整的 C 解法class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur dummy; while (l1 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 ? l1 : l2; return dummy.next; } };逐行来看。ListNode dummy(0)在栈上创建了一个哨兵节点它的 val 是 0next 默认空。ListNode* cur dummy;让 cur 指向这个哨兵。进入循环后如果 l1 的当前值小于 l2 的当前值就把 l1 这个节点接到 cur 的后面然后把 l1 指针往后移一位否则就接 l2并把 l2 后移。注意这里如果两个值相等会走 else 分支也就是接 l2这样不影响正确性因为两个链表都是有序的相等时接哪个都行剩下的节点顺序依然正确。cur cur-next;这行放在 if 外面是因为不管接了 l1 还是 l2cur 都需要指向结果链表的最新尾部。如果你把它分别写进两个分支里代码就会重复。循环结束后用cur-next l1 ? l1 : l2;接上剩余部分。这里如果 l1 不为空就接 l1否则接 l2。因为两个链表不可能同时都还有剩余节点所以这句不会接错。最后返回dummy.next这才是合并后真正的第一个有效节点。3.2 Python 实现优雅的or写法Python 版本和 C 结构几乎一样但写法上可以利用 Python 的or简化剩余链表拼接class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) 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 or l2 return dummy.nextcur.next l1 or l2在 Python 里表示优先取 l1如果 l1 为空则取 l2。这和 C 里l1 ? l1 : l2是一样的意思。很多 Python 新手会担心l1 or l2会不会把整个节点对象当成布尔值判断实际上l1是None或节点None为假节点为真逻辑上完全正确。这里有个小细节dummy ListNode(0)和cur dummy它们指向同一个新节点。当你执行cur.next l1时因为 cur 和 dummy 引用同一个对象所以 dummy 的 next 也会同步改变。这也是为什么最后可以返回dummy.next。如果你不小心写成dummy.next l1或把 cur 搞丢结果就会出错。3.3 递归实现C 和 Python 的不同习惯C 递归写法class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!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; } } };Python 递归写法前面已经给出了。两种语言的逻辑完全一致。关键要理解递归的返回每次函数返回的都是当前合并完成后的最小头节点。第一个递归调用发生在l1-next mergeTwoLists(l1-next, l2)它会把 l1 下一个节点和后一条链表的合并结果接回来。这个过程会一直递归到某条链表为空然后开始逐层返回。你可以拿一个小例子在纸上画一遍很快就能看出它和迭代殊途同归。3.4 边界条件与用例验证刷题时一定要在本地或者力扣上多测几组边界数据。我常用的测试用例包括l1 []l2 []两条空链表返回空链表。l1 []l2 [0]一条为空一条只有一个节点返回[0]。l1 [1,2,4]l2 [1,3,4]标准用例结果[1,1,2,3,4,4]。l1 [5]l2 [1,2]第一条链表较长或较短不平衡结果[1,2,5]。l1 [1]l2 [2]两个单节点结果[1,2]。实际上空链表判断是很多人的第一个坎。迭代写法里由于while l1 and l2本身就处理了空链表所以不会访问空指针递归写法里两个if not l1 / if not l2也是同样的作用。如果你写的代码在进入比较前没有判空一旦 l1 或 l2 为空访问l1.val就直接报空指针错误。4. 常见坑错过这几处一提交就红4.1 空链表判断为什么这么关键很多人觉得空链表是边界情况不重要但力扣判题会把空链表作为最基本的测试用例所以这个坑几乎是必踩的。假设你写的 while 循环条件是while (l1 || l2)然后在循环里直接比较值当其中一条链表为空时访问空指针的val就会崩溃。你需要保证判断逻辑里明确覆盖了空指针情况。最普通的处理方式就是像上面的迭代代码一样用while (l1 l2)限制循环最后拼接剩余部分。递归写法更简单两个终止条件直接返回对方链表。如果题目要求你不能修改原链表而是返回全新的链表那么空链表的处理思路会略有不同但核心原则不变必须先处理“至少一条链表为空”的情况否则后面所有逻辑都不成立。我在实际写代码时习惯先在注释里明确三个基础分支都为空、一个为空、都不为空。这样写出来的代码结构更稳。4.2 别把原链表节点弄丢或造成循环迭代法中最容易出现的错误是在某个分支里忘了移动 l1 或 l2。比如你写了cur-next l1;但忘了l1 l1-next;那么下一次循环你还会把同一个 l1 拿出来比较发现它依然小于 l2然后再次接到结果链表中结果链表里就会出现同一个节点的“回路”。在力扣上这可能表现为超时或者后续遍历时访问到之前已经遍历过的节点甚至形成无限循环。正确顺序是先让 cur 指向选定节点再移动对应链表的头指针最后再移动 cur。移动的先后顺序其实可以交换但逻辑上要保证每个节点只被“取走”一次。我的习惯是在 if 分支里先接节点再移动链表指针最后统一被cur cur-next;移动。这样可以避免在分支里重复移动 cur减少出错概率。还有一些人会在最后拼接剩余链表时写成这样的循环while(l1) { cur-next l1; l1 l1-next; cur cur-next; } while(l2) { cur-next l2; l2 l2-next; cur cur-next; }这当然也能得到正确结果但没必要。因为剩余链表本身已经有序直接把整条链表接上去就行不需要逐个节点重组。逐个处理会让代码更长也更可能引入新 bug。简洁的cur-next l1 ? l1 : l2;足够清晰。4.3 递归的终止条件与栈溢出递归写法的问题主要集中在两点一是终止条件写错二是栈溢出。终止条件写错比较典型的是只写了if (!l1) return l2;却忘了另一条空链表情况这样当 l2 为空而 l1 还有节点时递归会继续访问 l1 节点直到 l1 也变空才停结果虽然可能碰巧对但逻辑不严谨。更糟糕的情况是你在非空判断前就取l1.val那样遇到空链表会直接报错。栈溢出在力扣这题上其实不容易触发因为测试用例的链表长度有限。但是在面试环境下如果你写的递归没有明显的终止条件面试官可能会追问“如果链表有一百万个节点会怎么样”。你可以回答递归深度等于合并后链表长度最坏情况 O(mn)在大规模数据下可能导致栈溢出所以工程上更倾向迭代。这个追问点其实挺常见建议提前想清楚。4.4 带头结点和不带头结点的一个提醒前面提到力扣的链表是不带头结点的但很多人刷题时习惯自己造工具链表或者看到其他题解里有带头结点的写法容易混。带头结点意味着链表有一个额外的、val 无意义的空头节点真正的数据从 head.next 开始不带头结点则 head 就是第一个有效节点。力扣题的输入输出都是不带头结点的所以返回dummy.next是因为 dummy 是局部哨兵并非真正的头结点。如果你自己写测试代码想构造链表要注意两种风格的转换。比如本地测试时你写了个带哨兵的链表类把它当作参数传给力扣函数就可能因为多了一个空头节点而导致结果不匹配。我建议本地调试时干脆也按力扣的规则用节点对象和 None 表示链表末端不要额外包一层。这样思路干净也不容易混淆。5. 题目变体与刷题扩展5.1 合并 K 个有序链表从两两合并到优先队列做会了合并两个有序链表最自然的延伸就是力扣 23 题“合并 K 个有序链表”。这道题有很多种做法最简单的思路是每次取 K 个链表头中最小的节点接到结果链表后面然后把那个节点所在链表的指针往后移动。为了快速找到最小值可以维护一个最小堆堆顶就是当前最小的节点。堆的大小是 K所以每次插入和取出是 O(log K)总时间复杂度 O(n log K)其中 n 是所有链表节点总数。两两合并的方法也能解 K 链表你可以用第一个链表和第二个合并得到结果后再和第三个合并以此类推。这样每合并一次都要遍历一遍当前结果链表总复杂度会退化到 O(Kn)。分治法会更好一些每次把 K 个链表分成两半分别合并再总体合并。你可以发现分治法的底层就是反复调用 mergeTwoLists。这也解释了为什么 21 题是这道进阶题的基础。5.2 链表题的基础操作自查清单我看到热词里有“链表遍历”“c结构体链表基本语法”“python单链表逆序”“单链表的基本操作实验”等说明很多人还没把基础动作练扎实。刷 21 题之前最好先确认自己能默写几个操作如何构造一个单链表、如何在头部插入、如何在尾部插入、如何删除指定节点、如何反转链表。这些操作并不是每次都会直接考但几乎每道链表题都离不开。以遍历为例最基本的形式就是cur head while cur: print(cur.val) cur cur.next以反转链表为例迭代版用三个指针 prev、cur、next每次把当前节点的 next 指向前一个节点然后整体向前移动。合并两个有序链表中虽然没有反转但你对“指针移动”的熟练度决定了代码能不能一次写对。建议在刷这题之前先把这些基础操作单独写一遍再回到这道题你会发现思路清晰很多。5.3 刷题顺序建议从合并到更多链表题如果按照由易到难的顺序刷链表题我建议这样排先做 21 题合并两个有序链表再做 83 题删除排序链表中的重复元素接着做 206 题反转链表然后挑战 23 题合并 K 个有序链表最后可以试试 148 题排序链表。这样安排的原因是21 题让你学会“同时遍历两条链表并拼接”83 题让你学会“在单链表中跳过重复节点”206 题让你掌握“指针方向反转”23 题把合并能力放大到 K 条链表148 题则要求综合排序和合并能力。很多人刷题习惯按题型集中突破我觉得这比随机刷效率高得多。链表题尤其适合这样做因为它们的代码相似度很高只要掌握了几个套路很多中等问题都能拆成熟悉的小问题。比如排序链表可以用归并排序思路找中点、递归排序、再合并核心还是 21 题的合并逻辑。6. 实际调试中的一点心得最后聊点我自己的经验。我在第一次做这道题时用的是递归代码很漂亮跑测试也过了但后来在模拟面试里被要求改成迭代才发现自己对指针状态的跟踪不够熟练。从那以后我每写一类链表题都会要求自己至少同时会迭代和递归两种版本并且在本地自己构造几条链表做测试。链表这类题尤其适合“画图调试”在纸上画出节点和 next 指向然后照着代码手动走一遍很多问题比如丢节点、死循环都能很快暴露。如果你也是刚开始刷题建议把本地调试工具准备好比如写一个数组转链表的辅助函数以及一个打印链表的函数。这样你可以在本地跑任何力扣链表题不用依赖在线编辑器的打印功能。我当时写 Python 时用的转换函数大致是这样def make_linked_list(arr): dummy ListNode(0) cur dummy for val in arr: cur.next ListNode(val) cur cur.next return dummy.next def print_list(head): res [] while head: res.append(str(head.val)) head head.next print( - .join(res))有了这两个函数测试合并两个有序链表就很方便先用make_linked_list([1,2,4])构造 l1再用make_linked_list([1,3,4])构造 l2调用mergeTwoLists后直接打印结果。这种本地调试习惯让我后来刷链表题省了不少时间。合并两个有序链表是一个非常基础的“算法思维翻译成指针操作”的样本。把这道题彻底吃透你不仅能轻松应付面试中常见的链表合并变体也能为后续更复杂的链表题打下扎实基础。如果你还没把这题彻底搞懂不妨先停下来把手上的代码关掉拿一张白纸画一画两个链表、三个指针一步步走完整个合并过程再去写代码。很多时候点头觉得懂了和亲手写对之间差的就是这么一次慢速推演。
LeetCode 21 合并两个有序链表：迭代与递归两种解法详解
力扣第21题“合并两个有序链表”在链表题里属于入门但又极其经典的模型。很多刷题的人第一眼觉得这题简单真正手写时却总在指针移动、空链表处理、递归返回这些细节上卡住。我见过不少刚接触链表的同学上来就背迭代或递归模板结果换个题目照样不会。其实这题的核心价值是把“链表遍历、指针移动、节点拼接”这三个动作一次性讲清楚。无论你用C、Java还是Python都值得亲手写几遍再把自己的思路讲出来。这篇文章我就从题面拆起把迭代与递归两种主流解法的实现细节、常见坑位、同类扩展题目都过一遍当作一份可以直接参考的刷题笔记。1. 题目到底在问什么先把题面吃透1.1 两条有序链表长什么样力扣21题的输入是两个升序链表例如1 - 2 - 4和1 - 3 - 4要求把它们合并成一条新的升序链表结果是1 - 1 - 2 - 3 - 4 - 4。很多人第一次看到返回值是 ListNode 就有点蒙因为题目在网页上展示的是数组风格[1,2,4]和[1,3,4]但实际在代码里你拿到的并不是数组而是一个已经构造好的 ListNode 对象每个节点只有val和next两个字段。链表的天然特性是只能从头节点开始沿着next方向单向遍历不能像数组一样随机访问也不能直接调用排序函数。合并两个有序链表的核心动作就是同时遍历这两条链表每次从两条链表的当前位置中挑出值更小的那个节点接到结果链表的尾部然后继续往后走。整个过程和“合并两个有序数组”的思路很像但链表的特点在于你操作的是节点指针而不是下标。1.2 返回值与链表操作的本质题目要求返回合并后的链表头节点。注意这里的返回值应该是一个 ListNode而不是数组或者其他容器。链表的“头节点”就是第一个有效数据节点。很多人在本地调试时习惯打印一串数字但在力扣上你返回的是链表头判题系统会沿着next不断遍历比较你返回结果和期望结果是否每个节点的值都一致。这题本质上考的是“穿针引线”的能力结果链表不需要从零创建全新的节点而是直接复用输入的节点只是调整它们的next指向。比如输入1 - 2和3 - 4合并过程可以把2的next指向3这样结果就是1 - 2 - 3 - 4。你在过程中没有new任何新节点只是改变了一些节点的指向。这一点很重要因为如果每合并一个节点就new一个新节点虽然也能得到正确顺序但空间复杂度会从 O(1) 变成 O(n)并且失去了这道题关于链表指针操作的训练意义。1.3 从热词反推的常见理解偏差我在刷题社区里看到不少和“链表”相关的热词比如“循环单链表”“不带头结点的单链表”“链表插入”“逆置链表”等说明很多人基础概念还没理顺就急着做题。在这道题里力扣给出的链表是不带头结点的普通链表也就是说第一个节点就存有效数据没有单独的哑节点。如果你习惯了自己定义链表时带一个头结点做题时就要特别注意函数返回的应当是真数据节点而不是一个空的哨兵节点。另一个常见误区是觉得“合并两个有序链表”需要先新建一个空链表然后把两个链表的值一个个复制进去。这在逻辑上没错但实现起来绕且浪费。正确做法是让返回值直接指向两条输入链表中较小那个头节点然后通过指针不断串联。理解到这个层面后面看迭代和递归代码都会顺畅很多。2. 两种主流解法迭代和递归选哪个2.1 迭代法用哨兵节点省掉一半判断迭代法的写法非常固定基本是“三指针”结构一个哨兵节点 dummy一个游标指针 cur以及两个分别指向 l1 和 l2 当前节点的指针。每次比较 l1.val 和 l2.val把较小的节点接到 cur.next然后让那个链表的指针前进一位同时让 cur 也前进一位。循环结束后如果某条链表还有剩余节点直接把它整个接到结果链表的尾部。为什么用哨兵节点因为结果链表的头节点在循环开始前是未知的你总得知道最终合并后的第一个节点是谁。如果没有哨兵你通常要先判断 l1 和 l2 哪个值更小单独处理第一个节点再进入循环。这样代码会多出一个 if而且更容易漏边界。哨兵节点的 val 可以随便给比如 0 或者 -1它不会被返回最后返回的是 dummy.next。ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur dummy; while (l1 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 ? l1 : l2; return dummy.next; }这段代码里l1 l2是循环条件意味着只要有一条链表走完了循环就停止。最后用cur-next l1 ? l1 : l2接上剩余部分。这个写法很简洁但新手容易漏掉最后一步。你可以这样理解循环结束时两条链表中可能还有一条没走完因为剩下的每个节点都已经比另一条链表的剩余节点小或者另一条已经为空所以直接把整条剩余链表挂到结果后面即可。2.2 递归法把“合并”拆成“当前最小节点子问题”递归写法更短但理解门槛稍高。核心思路是合并 l1 和 l2只需要先找出两个头节点中较小的那个让它的 next 指向“合并剩余部分”的结果然后返回这个较小节点。比如 l1 1-3l2 2-4因为 1 小于 2所以合并后的头是 l1 的这个 1 节点而 l1.next 应该指向mergeTwoLists(3-None, 2-4)的结果。递归不断缩小规模直到某一条链表为空直接返回另一条链表。递归终止条件就是 l1 为空或者 l2 为空。这个条件非常关键因为如果没有终止条件递归会无限调用下去最终栈溢出。由于函数每次只处理一个头节点递归深度最多是两条链表的总长度。在力扣这种在线判题环境里测试链表长度一般不会深到栈溢出但如果你实际工作中处理几万、几十万节点的链表就要谨慎用递归。def mergeTwoLists(self, l1, l2): 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注意这里修改了原链表节点的 next 指向。递归返回的是“已经合并好的链表头”所以l1.next self.mergeTwoLists(l1.next, l2)这句话是把 l1 的 next 指向后续合并结果。许多人第一次写递归时会尝试返回一个新建链表但这里你会发现直接复用原节点更符合链表题的气质代码也更省。2.3 复杂度与适用场景对比两种解法的时间复杂度都是 O(mn)因为每条链表的每个节点最多被比较一次。空间复杂度有差别迭代法是 O(1)只用了几个指针递归法是 O(mn)因为每次调用都会占用一层系统栈。看起来迭代法更优但递归法的优势在于代码和思路更贴近“自顶向下”的分解方式更容易写对。我在实际刷题和面试中给出一个建议如果目标就只是为了过题两种都可以如果目标是训练工程思维建议优先写迭代法因为它不依赖额外栈空间并且更接近你后续写复杂链表操作时的真实手感。不过递归法能加深你对“子问题”的理解比如后面做合并 K 个有序链表时分治写法就和递归思想一脉相承所以两者都值得练。解法时间复杂度额外空间复杂度代码简洁度推荐场景迭代 哨兵O(mn)O(1)中工程实现、面试稳妥递归O(mn)O(mn)高理解分治、速写题解3. 代码实现与逐行拆解3.1 C 实现理解指针与哨兵先看完整的 C 解法class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode dummy(0); ListNode* cur dummy; while (l1 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 ? l1 : l2; return dummy.next; } };逐行来看。ListNode dummy(0)在栈上创建了一个哨兵节点它的 val 是 0next 默认空。ListNode* cur dummy;让 cur 指向这个哨兵。进入循环后如果 l1 的当前值小于 l2 的当前值就把 l1 这个节点接到 cur 的后面然后把 l1 指针往后移一位否则就接 l2并把 l2 后移。注意这里如果两个值相等会走 else 分支也就是接 l2这样不影响正确性因为两个链表都是有序的相等时接哪个都行剩下的节点顺序依然正确。cur cur-next;这行放在 if 外面是因为不管接了 l1 还是 l2cur 都需要指向结果链表的最新尾部。如果你把它分别写进两个分支里代码就会重复。循环结束后用cur-next l1 ? l1 : l2;接上剩余部分。这里如果 l1 不为空就接 l1否则接 l2。因为两个链表不可能同时都还有剩余节点所以这句不会接错。最后返回dummy.next这才是合并后真正的第一个有效节点。3.2 Python 实现优雅的or写法Python 版本和 C 结构几乎一样但写法上可以利用 Python 的or简化剩余链表拼接class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) - ListNode: dummy ListNode(0) 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 or l2 return dummy.nextcur.next l1 or l2在 Python 里表示优先取 l1如果 l1 为空则取 l2。这和 C 里l1 ? l1 : l2是一样的意思。很多 Python 新手会担心l1 or l2会不会把整个节点对象当成布尔值判断实际上l1是None或节点None为假节点为真逻辑上完全正确。这里有个小细节dummy ListNode(0)和cur dummy它们指向同一个新节点。当你执行cur.next l1时因为 cur 和 dummy 引用同一个对象所以 dummy 的 next 也会同步改变。这也是为什么最后可以返回dummy.next。如果你不小心写成dummy.next l1或把 cur 搞丢结果就会出错。3.3 递归实现C 和 Python 的不同习惯C 递归写法class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { if (!l1) return l2; if (!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; } } };Python 递归写法前面已经给出了。两种语言的逻辑完全一致。关键要理解递归的返回每次函数返回的都是当前合并完成后的最小头节点。第一个递归调用发生在l1-next mergeTwoLists(l1-next, l2)它会把 l1 下一个节点和后一条链表的合并结果接回来。这个过程会一直递归到某条链表为空然后开始逐层返回。你可以拿一个小例子在纸上画一遍很快就能看出它和迭代殊途同归。3.4 边界条件与用例验证刷题时一定要在本地或者力扣上多测几组边界数据。我常用的测试用例包括l1 []l2 []两条空链表返回空链表。l1 []l2 [0]一条为空一条只有一个节点返回[0]。l1 [1,2,4]l2 [1,3,4]标准用例结果[1,1,2,3,4,4]。l1 [5]l2 [1,2]第一条链表较长或较短不平衡结果[1,2,5]。l1 [1]l2 [2]两个单节点结果[1,2]。实际上空链表判断是很多人的第一个坎。迭代写法里由于while l1 and l2本身就处理了空链表所以不会访问空指针递归写法里两个if not l1 / if not l2也是同样的作用。如果你写的代码在进入比较前没有判空一旦 l1 或 l2 为空访问l1.val就直接报空指针错误。4. 常见坑错过这几处一提交就红4.1 空链表判断为什么这么关键很多人觉得空链表是边界情况不重要但力扣判题会把空链表作为最基本的测试用例所以这个坑几乎是必踩的。假设你写的 while 循环条件是while (l1 || l2)然后在循环里直接比较值当其中一条链表为空时访问空指针的val就会崩溃。你需要保证判断逻辑里明确覆盖了空指针情况。最普通的处理方式就是像上面的迭代代码一样用while (l1 l2)限制循环最后拼接剩余部分。递归写法更简单两个终止条件直接返回对方链表。如果题目要求你不能修改原链表而是返回全新的链表那么空链表的处理思路会略有不同但核心原则不变必须先处理“至少一条链表为空”的情况否则后面所有逻辑都不成立。我在实际写代码时习惯先在注释里明确三个基础分支都为空、一个为空、都不为空。这样写出来的代码结构更稳。4.2 别把原链表节点弄丢或造成循环迭代法中最容易出现的错误是在某个分支里忘了移动 l1 或 l2。比如你写了cur-next l1;但忘了l1 l1-next;那么下一次循环你还会把同一个 l1 拿出来比较发现它依然小于 l2然后再次接到结果链表中结果链表里就会出现同一个节点的“回路”。在力扣上这可能表现为超时或者后续遍历时访问到之前已经遍历过的节点甚至形成无限循环。正确顺序是先让 cur 指向选定节点再移动对应链表的头指针最后再移动 cur。移动的先后顺序其实可以交换但逻辑上要保证每个节点只被“取走”一次。我的习惯是在 if 分支里先接节点再移动链表指针最后统一被cur cur-next;移动。这样可以避免在分支里重复移动 cur减少出错概率。还有一些人会在最后拼接剩余链表时写成这样的循环while(l1) { cur-next l1; l1 l1-next; cur cur-next; } while(l2) { cur-next l2; l2 l2-next; cur cur-next; }这当然也能得到正确结果但没必要。因为剩余链表本身已经有序直接把整条链表接上去就行不需要逐个节点重组。逐个处理会让代码更长也更可能引入新 bug。简洁的cur-next l1 ? l1 : l2;足够清晰。4.3 递归的终止条件与栈溢出递归写法的问题主要集中在两点一是终止条件写错二是栈溢出。终止条件写错比较典型的是只写了if (!l1) return l2;却忘了另一条空链表情况这样当 l2 为空而 l1 还有节点时递归会继续访问 l1 节点直到 l1 也变空才停结果虽然可能碰巧对但逻辑不严谨。更糟糕的情况是你在非空判断前就取l1.val那样遇到空链表会直接报错。栈溢出在力扣这题上其实不容易触发因为测试用例的链表长度有限。但是在面试环境下如果你写的递归没有明显的终止条件面试官可能会追问“如果链表有一百万个节点会怎么样”。你可以回答递归深度等于合并后链表长度最坏情况 O(mn)在大规模数据下可能导致栈溢出所以工程上更倾向迭代。这个追问点其实挺常见建议提前想清楚。4.4 带头结点和不带头结点的一个提醒前面提到力扣的链表是不带头结点的但很多人刷题时习惯自己造工具链表或者看到其他题解里有带头结点的写法容易混。带头结点意味着链表有一个额外的、val 无意义的空头节点真正的数据从 head.next 开始不带头结点则 head 就是第一个有效节点。力扣题的输入输出都是不带头结点的所以返回dummy.next是因为 dummy 是局部哨兵并非真正的头结点。如果你自己写测试代码想构造链表要注意两种风格的转换。比如本地测试时你写了个带哨兵的链表类把它当作参数传给力扣函数就可能因为多了一个空头节点而导致结果不匹配。我建议本地调试时干脆也按力扣的规则用节点对象和 None 表示链表末端不要额外包一层。这样思路干净也不容易混淆。5. 题目变体与刷题扩展5.1 合并 K 个有序链表从两两合并到优先队列做会了合并两个有序链表最自然的延伸就是力扣 23 题“合并 K 个有序链表”。这道题有很多种做法最简单的思路是每次取 K 个链表头中最小的节点接到结果链表后面然后把那个节点所在链表的指针往后移动。为了快速找到最小值可以维护一个最小堆堆顶就是当前最小的节点。堆的大小是 K所以每次插入和取出是 O(log K)总时间复杂度 O(n log K)其中 n 是所有链表节点总数。两两合并的方法也能解 K 链表你可以用第一个链表和第二个合并得到结果后再和第三个合并以此类推。这样每合并一次都要遍历一遍当前结果链表总复杂度会退化到 O(Kn)。分治法会更好一些每次把 K 个链表分成两半分别合并再总体合并。你可以发现分治法的底层就是反复调用 mergeTwoLists。这也解释了为什么 21 题是这道进阶题的基础。5.2 链表题的基础操作自查清单我看到热词里有“链表遍历”“c结构体链表基本语法”“python单链表逆序”“单链表的基本操作实验”等说明很多人还没把基础动作练扎实。刷 21 题之前最好先确认自己能默写几个操作如何构造一个单链表、如何在头部插入、如何在尾部插入、如何删除指定节点、如何反转链表。这些操作并不是每次都会直接考但几乎每道链表题都离不开。以遍历为例最基本的形式就是cur head while cur: print(cur.val) cur cur.next以反转链表为例迭代版用三个指针 prev、cur、next每次把当前节点的 next 指向前一个节点然后整体向前移动。合并两个有序链表中虽然没有反转但你对“指针移动”的熟练度决定了代码能不能一次写对。建议在刷这题之前先把这些基础操作单独写一遍再回到这道题你会发现思路清晰很多。5.3 刷题顺序建议从合并到更多链表题如果按照由易到难的顺序刷链表题我建议这样排先做 21 题合并两个有序链表再做 83 题删除排序链表中的重复元素接着做 206 题反转链表然后挑战 23 题合并 K 个有序链表最后可以试试 148 题排序链表。这样安排的原因是21 题让你学会“同时遍历两条链表并拼接”83 题让你学会“在单链表中跳过重复节点”206 题让你掌握“指针方向反转”23 题把合并能力放大到 K 条链表148 题则要求综合排序和合并能力。很多人刷题习惯按题型集中突破我觉得这比随机刷效率高得多。链表题尤其适合这样做因为它们的代码相似度很高只要掌握了几个套路很多中等问题都能拆成熟悉的小问题。比如排序链表可以用归并排序思路找中点、递归排序、再合并核心还是 21 题的合并逻辑。6. 实际调试中的一点心得最后聊点我自己的经验。我在第一次做这道题时用的是递归代码很漂亮跑测试也过了但后来在模拟面试里被要求改成迭代才发现自己对指针状态的跟踪不够熟练。从那以后我每写一类链表题都会要求自己至少同时会迭代和递归两种版本并且在本地自己构造几条链表做测试。链表这类题尤其适合“画图调试”在纸上画出节点和 next 指向然后照着代码手动走一遍很多问题比如丢节点、死循环都能很快暴露。如果你也是刚开始刷题建议把本地调试工具准备好比如写一个数组转链表的辅助函数以及一个打印链表的函数。这样你可以在本地跑任何力扣链表题不用依赖在线编辑器的打印功能。我当时写 Python 时用的转换函数大致是这样def make_linked_list(arr): dummy ListNode(0) cur dummy for val in arr: cur.next ListNode(val) cur cur.next return dummy.next def print_list(head): res [] while head: res.append(str(head.val)) head head.next print( - .join(res))有了这两个函数测试合并两个有序链表就很方便先用make_linked_list([1,2,4])构造 l1再用make_linked_list([1,3,4])构造 l2调用mergeTwoLists后直接打印结果。这种本地调试习惯让我后来刷链表题省了不少时间。合并两个有序链表是一个非常基础的“算法思维翻译成指针操作”的样本。把这道题彻底吃透你不仅能轻松应付面试中常见的链表合并变体也能为后续更复杂的链表题打下扎实基础。如果你还没把这题彻底搞懂不妨先停下来把手上的代码关掉拿一张白纸画一画两个链表、三个指针一步步走完整个合并过程再去写代码。很多时候点头觉得懂了和亲手写对之间差的就是这么一次慢速推演。
