企业官网建设流程全解析

LeetCode第21题“合并两个有序链表”，应该是我见过最经典的一道链表入门题。不管是校招笔试、考研数据结构，还是平时刷题练手，它出现的频率都高得惊人。题面看起来也简单：给你两个已经按升序排好的单链表，把它们合并成一个新的升序链表，返回合并后的头节点。但真正动手写的时候，很多人会在头节点处理、指针移动顺序、循环结束后的收尾这些地方卡住。这篇文章就从思路到细节完整拆一遍这道题，同时把链表操作里那些容易被忽略的底层功夫也一并讲清楚。适合刚开始接触链表的同学，也适合想把自己的解法讲得更严谨的人，面试前拿这篇文章快速过一遍尤其实用。

1. 题目本质与核心思路拆解

1.1 先读懂题目再动手：题面到底在说什么

这道题输入是两个单链表的头节点，一般定义成l1和l2。每个链表节点包含一个整数val和一个指向下一个节点的指针next。链表本身是按非递减顺序排列的，也就是说1->2->4这种形式，节点值从头到尾不下降。输出要求是返回合并后的链表的头节点，合并后的链表也要升序。

很多初学者上来就闷头写，写到一半才发现自己都没搞清楚“能不能新建节点”“要不要保留原链表结构”这些问题。在 LeetCode 这个题的标准设定下，你不需要新建额外节点，直接复用原来的节点、修改它们的next指针就行。这一点很关键：它决定了这道题的空间复杂度能做到 O(1)，也是链表合并和数组合并最大的区别。数组合并两个有序数组，通常要开一个额外数组来放结果；链表合并只需要“改指针”，不需要搬动节点本身。

这里还需要搞清楚单链表的节点定义，不同语言写法略有差异。Python 里是这个样子：

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next

C++ 里则是：

struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} };

理解这个结构是后面所有操作的基础。链表的每个节点在内存里不一定是连续存放的，正是靠next指针串成一条链。这也意味着，合并链表最核心的动作不是“移动数据”，而是“改变指针指向”。

1.2 核心策略：谁小谁接上

合并两个有序链表的迭代思路，一句话就能说清：两个指针分别指向两条链的当前节点，每次比较这两个节点的值，把值较小的节点摘下来，接到结果链表的尾部，然后让那个链表的指针往后挪一位，另一个指针不动，继续比较。

为什么这样一定能得到正确的升序链表？因为两个输入链表各自都是升序的，所以两个链表当前节点中较小的那个，就是所有剩余节点中最小的。拿走它之后，剩下两条链依然各自有序，问题规模缩小了，但性质不变。这就是典型的“贪心”策略，每一步都做当前看起来最优的选择，最终全局最优。生活里也好理解：两摞按时间排好的档案，你要把它们合成一摞，只需要每次看两摞最上面那张谁的日期更早，把它抽出来放在新的一摞最上面，重复到全部抽完。

每次比较只需要一次，被选中的节点就永久进入了结果链表，不会再被访问。所以整道题最多比较m + n - 1次，时间复杂度是 O(m+n)，其中m和n分别是两个链表的长度。因为全程只用了几个指针变量，没有申请额外节点，空间复杂度是 O(1)。

1.3 哑节点：为什么要一个占位符

新手写这道题最容易卡住的地方，就是“返回哪个节点”。如果用最朴素的写法，第一轮比较前，结果链表的头节点还是未知的，你必须先单独判断一次：

if l1.val <= l2.val: head = l1 l1 = l1.next else: head = l2 l2 = l2.next

然后才进入循环。这种写法不是不行，但它把“第一轮”变成了特殊情况，代码里凭空多出一堆分支，逻辑一旦复杂就容易出错。而且如果在循环里维护一个tail指针指向结果链表尾部，那么head和tail是分开初始化的，看代码时脑子要多转一下。

解决办法就是引入哑节点，也叫占位节点、哨兵节点。它本身不存有效数据，只是为了让“当前结果链表的尾部”这个角色在第一步就有着落：

dummy = ListNode(0) cur = dummy

之后每轮比较，只需要把选中的节点接到cur.next，然后cur = cur.next。从头到尾，所有轮次的逻辑完全一致，不用对第一轮做任何特殊处理。循环结束后，dummy.next就是合并后链表的真实头节点，直接返回它就行。

哑节点是链表题里极其常用的技巧，不只是这道题。删除链表倒数第 N 个节点、在链表头部插入节点、反转链表的一部分，都经常用到它。它的本质是“用一个不参与业务逻辑的额外节点，抹平边界情况的特殊处理”，让代码更规整，也更不容易漏掉边界分支。

2. 迭代解法实现与细节深挖

2.1 代码全貌：先跑通再讲道理

直接给出可用的迭代版本，Python 写法是：

def merge_two_lists(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 if l1 else l2 return dummy.next

这几行代码，说它是链表题里的“标准答案”也不为过。思路清晰，边界干净，几乎没有多余成分。我第一次认真琢磨这段代码的时候，惊讶于它竟然能把合并两个有序链表写得这么利落。但越是简洁的代码，越需要拆开看每一行在干什么，否则面试时你可能连cur = cur.next忘了写都不知道问题出在哪里。

C++ 版本也顺带贴一下，逻辑完全一样：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* dummy = new ListNode(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; }

注意这里如果new出来的dummy是手动分配的内存，实际工程里记得要释放，否则会有小内存泄漏。在线评测一般不管这个，但写工程代码时最好是栈上创建或者用智能指针。

2.2 三个变量各司其职：循环不变量是关键

这段代码里有几个变量，它们的职责要分清楚：

• dummy：占位节点，最终不参与结果链表的业务数据，它的next指向结果链表的第一个真实节点。
• cur：结果链表当前的尾节点，始终保持指向“已经串好的最后一个节点”。
• l1、l2：两个原链表中还没被合并的剩余部分各自的头指针。

理解这段代码最好的方式，是把它当成一个“循环不变量”来维护。所谓循环不变量，就是在每次循环执行前都必须成立的性质。这里的不变量是：结果链表从dummy.next到cur已经是升序的，且l1、l2各自仍然保持升序，它们的所有节点值都不小于已合并部分的最大值。

每轮循环做的事情，就是从l1和l2的当前头节点里选出值较小的那个，接到cur.next上，然后更新cur和对应链表的指针，让上述不变量继续保持。循环结束时，有一条链已经为空，另一条链剩下的所有节点都大于等于已合并部分的末尾值，所以直接拼上去就行。调试的时候，你甚至可以在循环体里临时加个断言，检查结果链表的单调性，这样能早发现指针串联错误。

2.3 循环退出与收尾：为什么可以直接拼接

循环条件是while l1 and l2，也就是说，只要有一条链遍历完了，循环就结束。这时候出现两种情况：

• l1为空，l2还有剩余节点；
• l2为空，l1还有剩余节点；
• 两条链同时为空，等价于cur.next = l2，而l2是空节点，结果也正确。

关键点是，剩余的那条链本身是有序的，而且剩余部分的所有节点值一定不小于cur当前指向的节点的值。为什么？因为每一次迭代，我们都是从两个链表的当前头节点中选出较小的那个，选完之后，另一个链表的头节点（即剩余链表的第一个节点）一定大于等于刚选走的节点。这个性质在循环过程中始终成立。所以循环结束时，直接把剩下那条链接到cur.next，不需要再比较，也不破坏整体有序性。

这里有个新手容易绕不过来的问题：万一剩余链表里有比已经合并部分末尾更小的节点怎么办？答案是不会。因为如果剩余链表的头节点比已合并部分末尾小，那么它在某轮循环中就应该被提前选走，而不可能留到现在。这个结论听着简单，但自己能严谨地证明一遍，比背十遍代码都有用。

2.4 复杂度与边界场景：一次想全，调试不慌

时间复杂度 O(m+n) 的道理前文说过，每个节点最多被比较一次、被接入一次。空间复杂度 O(1)，没有额外申请节点。这个复杂度已经是最优了，因为你至少要遍历一遍两个链表的全部节点才能确定顺序。

边界场景提前过一遍，写代码时心里就有底：

• l1为空，l2不为空：循环一次都不执行，cur.next = l2，直接返回整个l2。
• l1不为空，l2为空：同样直接返回l1。
• 两个都为空：返回None，这也是合法结果。
• 两个链表长度相差很大：比如一个长度 3，一个长度 10000，那么循环在短链表耗尽后退出的更早，长链表剩余部分整段接上去，非常高效。
• 节点值有相等的情况：用<=判断时，相等时优先取l1的节点，这会让合并后的链表保持稳定，即相等节点的相对顺序不会被打乱。

这些边界情况，建议自己在草稿纸上画几个用例跑一遍，比如[1,3,5]和[2,4,6]，画着画着就会对链表指针的移动产生肌肉记忆。

3. 递归解法与两种思路的权衡

3.1 递归代码：每一层只解决“当前头节点是谁”

有些题用递归写起来特别顺，因为问题的结构天然就是递归的。合并两个有序链表就可以这样理解：要合并l1和l2，只需要确定合并后链表的第一个节点是谁——它肯定是l1.val和l2.val中较小的那个；确定好第一个节点之后，剩下的就是“把较小的那个链表的 next 指向 merge(较小链表.next, 另一条链表)”，这是一个规模更小的同样问题。

写成代码就是：

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

递归代码的出口就是空链表判断：如果l1空，就直接返回l2；如果l2空，就直接返回l1。两个都空的情况已经被第一个判断覆盖了，因为not l1为真时直接返回l2，此时的l2就是None。

3.2 递归执行过程拆解：用一个小例子走到底

代码短，不代表看得懂。我拿l1 = [1,3,5]、l2 = [2,4,6]来手动展开一下递归调用。先调用merge(1, 2)，因为1 <= 2，所以这一层要返回的节点是1，但它的next要先由merge(3, 2)的结果决定。接着merge(3, 2)里2 <= 3，返回2，它的next由merge(3, 4)决定。merge(3, 4)返回3，next由merge(5, 4)决定……这样一层一层“递”下去，直到某一侧链表先变成空，就开始逐层“归”回来。

真正的回溯顺序是：最底层返回某个剩余链表后，上一层把返回结果接到自己的next上，然后带着自己这个节点继续往上返回。最终整条链就变成了1->2->3->4->5->6。这个过程用文字描述有点绕，但在纸上画几层调用关系就非常直观。建议新手一定要把调用树画一遍，否则面试时写递归很容易写反。

3.3 迭代 vs 递归：到底选哪个

两种解法都能 AC，但实际使用时要权衡。我整理了一张对比表：

递归版虽然看起来只有四行核心逻辑，但每递归一层，就要占用一份函数调用栈空间。递归深度最大会达到m+n，而且两个链表长度都很大时，这个深度在 Python、C++ 里都有可能触发栈溢出。所以工程代码里我一般推荐迭代版，空间确定是 O(1)，不会出现调用栈爆炸。面试时可以先给递归版展示思路，再补一句“如果链表很长，我会改成迭代版”，显得你对两种方案的风险都心里有数。

3.4 递归的常见误解与易错点

我见过不少同学栽在递归的几个细节上。第一个误解是“递归会新建节点”。不会的，递归返回的都是原链表里的节点，只是修改了next指向，本质上还是在改原链表结构。第二个误解是“递归比迭代更省空间”，实际上刚才说了，递归额外消耗调用栈空间，空间复杂度是 O(m+n)，比迭代高。

第三个易错点是搞混赋值顺序。递归体里必须先确定本层返回的节点，再修改它的next。如果你反过来，先改了next再返回，就可能把本层节点和递归结果的关系搞乱。第四个易错点是只写一个空链表出口，比如只判断if not l1: return l2，忘了l2为空的情况。递归出口一定要两个都判断，缺一个就会在某些输入下报空指针异常或者返回错误结果。

4. 测试用例设计与常见问题排查

4.1 一套可以直接抄的测试用例

写算法题，代码跑通只是第一步，能不能想到全面的测试用例才是真正拉开差距的地方。我习惯在本地为这道题准备这样一组用例：

这些用例基本覆盖了题目可能出现的所有形态。跑测试的时候，除了看最终的结果链表值顺序对不对，还要注意别把原链表改得乱七八糟。有些在线平台会把l1、l2的原始结构用于后续测试，如果你改坏了原链表，后面用例可能莫名其妙失败。

4.2 代码调试中最容易踩的几个坑

指针类 bug 是最难肉眼发现的一类问题，因为代码看着都对，但运行结果就是不对。我帮你把高频坑集中列一下。

第一个坑是忘记移动cur指针。很多人写完cur.next = l1之后，忘了写cur = cur.next，导致下一轮又把新节点接在同一个位置上，结果链表永远只有最后一个节点，前面的节点全丢了。这个问题在纸上推演一遍就能发现，关键是在循环体结束前，cur必须指向最新接上的节点。

第二个坑是返回了dummy而不是dummy.next。dummy是一个值无关紧要的占位节点，如果直接返回它，结果链表就多了一个多余的头节点，判题必然报错。写代码时最后一行的return dummy.next要形成肌肉记忆。

第三个坑是提前修改了l1或l2的头指针，导致后续判断出错。比如你先把较小节点接到cur.next上，然后又用l1 = l1.next，如果这段代码写错顺序，就可能跳过节点，或者把同一个节点接入两次。正确的做法是先保留要移动的指针，比如tmp = l1.next，然后再修改l1。当然标准写法里直接l1 = l1.next放在cur.next = l1之后是安全的，因为此时l1还没被覆盖。

第四个坑是在 C/C++ 场景下，如果手动delete了节点，可能会导致返回的链表指针悬空。这个题的标准解法不会删除节点，但如果你自己加了一些“清理”逻辑，要注意不是所有被遍历过的节点都能释放，被合并进结果链表的节点必须保留。

4.3 面试官围绕这道题常追问的几个点

这道题虽然简单，但面试官很擅长在它基础上加问。我总结几个出现频率极高的问题。

第一个是稳定性。如果两个链表里有相同值的节点，合并后它们的相对顺序会改变吗？用<=取l1的节点，那么l1中相同值的节点会排在l2中相同值的节点之前，这种归并是稳定的。如果改用<，相等时就会取l2的节点，稳定性就反了。弄清楚这个细节，能体现你对归并过程有深入理解。

第二个问题是能否做到不修改原链表。题目默认允许复用原节点，但有些场景要求合并结果是一份全新链表，原链表保持不变。这种情况下就不能直接改next，需要每一步新建节点并复制val，时间复杂度仍然 O(m+n)，空间复杂度变成 O(m+n)。面试时可以主动提一句，显得你考虑过只读场景。

第三个问题是如果输入的是降序链表怎么办。把比较符号反过来就行，核心逻辑完全一致，所以这道题并不只适用于升序。

第四个问题是如果链表里有环呢。这个题默认输入是两个无环的单链表。如果面临有环的输入，必须先做环检测，否则合并过程会死循环。

把这些追问提前想明白，面这道题的时候就会从容很多。

5. 延伸扩展：从合并两个到合并 K 个

5.1 合并 K 个有序链表的三种常见思路

掌握了两个链表的合并，就掌握了更复杂问题的地基。LeetCode 第 23 题“合并 K 个升序链表”，正是这道题的直接升级版。给定 K 个有序链表，把它们合并成一个有序链表，常见思路有三种。

第一种是逐个合并。把第一个和第二个合并，结果再和第三个合并，依次类推。假设链表总节点数是 N，这种做法的总复杂度是 O(KN)，因为越到后面，当前结果链表越长，反复被扫描的开销越大。优点是代码最简单，但效率在 K 较大时不理想。

第二种是分治合并，也叫两两合并。把 K 个链表两两配对，每一对用我们这道题的mergeTwoLists合并，得到约 K/2 个新链表；再两两合并，重复直到只剩一个链表。这个过程很像归并排序，每一轮的总操作量是 O(N)，一共进行 logK 轮，总复杂度 O(NlogK)。这个思路在面试里是加分项，因为它体现了对“归并”思想的理解。

第三种是优先队列（最小堆）。先把 K 个链表的头节点全部放入一个小根堆，每次弹出最小的节点，接入结果链表尾部，然后把该节点的next节点再入堆。循环直到堆为空。时间复杂度同样是 O(NlogK)，空间复杂度 O(K)。在 K 比链表长度还大的场景里，这个方案很实用。

5.2 归并思想在链表题里的渗透

对链表的归并思想一旦熟练，很多题都能迎刃而解。最典型的就是链表排序（LeetCode 第 148 题）。对一个单链表排序，最常见的高效做法就是“自顶向下归并排序”：先用快慢指针找到链表中点，把链表拆成左右两半，递归排序，然后用我们这道题的合并函数把两个有序链表合起来。整个过程几乎是本题的复用。

还有一些题看着不一样，但底层也是归并的影子。比如“合并两个有序数组”用的是类似的双指针思路，只是数组不能像链表那样只改指针，需要额外空间。再比如“两个有序链表求交集”也可以借鉴双指针同时推进的框架。把这道题练熟，相当于给未来的链表题打下了一个很扎实的地基。

5.3 真实工程里的多路归并影子

有同学会问，这种纯粹的算法题，实际工作里真的用得上吗？当然用得上。多路归并是很多底层系统的核心逻辑。外部排序就是典型场景：当要排序的数据量远超内存时，系统会先把大文件切分成多个小片段，每个片段在内存里排序后写成有序片段文件，然后对这些有序片段做多路归并，最终得到一个整体有序的大文件。这个多路归并过程，和“合并 K 个有序链表”的概念几乎一模一样，只是操作对象从链表的节点变成了文件里的数据块。

数据库里也有类似的东西。比如 sort merge join 在处理两个有序表时，就是双指针同时扫两条有序序列，按连接条件逐步推进。再比如 Git 在合并多个分支时，本质上也在处理多个有序或可排序的提交序列之间的关系。所以哪怕你现在只是刷题，这些“无聊的链表题”其实都对应着一套真实存在的工程范式。

我个人带过不少同学刷这道题，最大的感受是：不要觉得自己看懂了就跳过。链表题的熟练度，是画图画出来的，不是肉眼读代码读出来的。花 20 分钟在纸上把迭代版和递归版的指针变化各自推演一遍，比刷十道同类题更有用。如果在线判题时出现“改来改去还是错”的玄学 bug，别硬想，先回到草稿纸上跑一个小用例，把每次循环后的链表状态写出来，问题基本一眼就能看见。这个习惯，也是我至今写链表代码不慌的原因。