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, val=0, next=None): 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(m+n)。这个复杂度是下界，因为你要合并所有节点，每个节点你总得看一眼。空间复杂度上，迭代法除了几个指针和哨兵节点，没有额外使用和输入规模相关的存储，所以是O(1)。递归法的空间复杂度就有明显差别了，它要占用O(m+n)的调用栈空间，在最坏情况下（比如两条链表交替大小，每个递归层都得往下压一层）栈深度会达到m+n。这也是我说工程里优先用迭代法的根本原因，不是递归不好，而是空间开销不划算。

3.4 手写一个例子做逐步验证

为了让你彻底放心，我用一组小数据走一遍。假设L1是1 -> 3 -> 5，L2是2 -> 4 -> 6。

初始：dummy -> None，current指向dummy。

第一步：l1.val=1，l2.val=2，1更小。current.next指向1节点，l1移动到3，current移动到1节点。此时结果链是dummy -> 1。

第二步：l1.val=3，l2.val=2，2更小。current.next指向2节点，l2移动到4，current移动到2节点。结果链是dummy -> 1 -> 2。

第三步：l1.val=3，l2.val=4，3更小。current.next指向3节点，l1移动到5，current移动到3节点。结果链是dummy -> 1 -> 2 -> 3。

第四步：l1.val=5，l2.val=4，4更小。current.next指向4节点，l2移动到6，current移动到4节点。

第五步：l1.val=5，l2.val=6，5更小。current.next指向5节点，l1变成空，current移动到5节点。

此时while条件不再满足，l1已经为空，于是执行current.next = l1 if l1 else l2，l2里还有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(m+n)，迭代空间O(1)”这种对比，通常会加分。

还有一个现实考量：如果你在工程中写链表代码，链表长度没准儿有多大，递归栈溢出风险是真实存在的。所以我对工作党更推荐迭代作默认写法，递归作为理解工具和面试展示用法。两种都要会，但出手选迭代，这是我个人的经验。

5. 实操对比测试：什么样的用例能帮你看清代码对不对

5.1 一组必测的边界用例清单

写完代码，怎么验证对不对？千万别只拿一个常规用例跑一遍就算完事。链表题最大的坑就是边界条件，我总结了一个最小测试集，你拿这道题去跑，跑过就基本稳了：

第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, val=0, next=None): 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(m+n)。这个复杂度是下界，因为你要合并所有节点，每个节点你总得看一眼。

空间复杂度上，迭代法除了几个指针和哨兵节点，没有额外使用和输入规模相关的存储，所以是O(1)。递归法的空间复杂度就有明显差别了，它要占用O(m+n)的调用栈空间，在最坏情况下（比如两条链表交替大小，每个递归层都得往下压一层）栈深度会达到m+n。这也是我说工程里优先用迭代法的根本原因，不是递归不好，而是空间开销不划算。

3.4 手写一个例子做逐步验证

为了让你彻底放心，我用一组小数据走一遍。假设L1是1 -> 3 -> 5，L2是2 -> 4 -> 6。

初始：dummy -> None，current指向dummy。

第一步：l1.val=1，l2.val=2，1更小。current.next指向1节点，l1移动到3，current移动到1节点。此时结果链是dummy -> 1。

第二步：l1.val=3，l2.val=2，2更小。current.next指向2节点，l2移动到4，current移动到2节点。结果链是dummy -> 1 -> 2。

第三步：l1.val=3，l2.val=4，3更小。current.next指向3节点，l1移动到5，current移动到3节点。结果链是dummy -> 1 -> 2 -> 3。

第四步：l1.val=5，l2.val=4，4更小。current.next指向4节点，l2移动到6，current移动到4节点。

第五步：l1.val=5，l2.val=6，5更小。current.next指向5节点，l1变成空，current移动到5节点。

此时while条件不再满足，l1已经为空，于是执行current.next = l1 if l1 else l2，l2里还有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(m+n)，迭代空间O(1)”这种对比，通常会加分。

还有一个现实考量：如果你在工程中写链表代码，链表长度没准儿有多大，递归栈溢出风险是真实存在的。所以我对工作党更推荐迭代作默认写法，递归作理解工具和面试展示用法。两种都要会，但出手选迭代，这是我个人的经验。

5. 实操对比测试：什么样的用例能帮你看清代码对不对

5.1 一组必测的边界用例清单

写完代码，怎么验证对不对？千万别只拿一个常规用例跑一遍就算完事。链表题最大的坑就是边界条件，我总结了一个最小测试集，你拿这道题去跑，跑过就基本稳了：

第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个链表怎么合并。三遍下来，这道题就真正沉淀成你自己的东西了。往后再遇到链表反转、链表排序、两两交换，你会发现它们都有一个共同的味道：弄清楚指针前后关系，剩下的就是比较和赋值的事情。