企业官网建设流程全解析

不用被“合并两个有序链表”这种朴素题目劝退，它在力扣上是第21题，地位却很特别——既是链表题里的“hello world”，又是后续很多复杂题目的积木。许多人刷到这题时觉得简单，扫一眼就翻过去了，结果到“合并K个升序链表”“两两交换链表中的节点”甚至“排序链表”时卡住，回头才发现是这道基础题的理解不够扎实。我自己最早也是草草写完迭代版就完事，直到在面试里被问“递归版怎么写？递归的调用栈你画得出来吗？”才意识到这题值得认真拆一遍。

这篇文章会把第21题从头到尾做一个完整的拆解：从题目到底考查什么，到迭代法和递归法两套解法的推导过程与代码实现，再到复杂度分析、面试延伸题和实战中容易踩的坑。内容尽量照顾两种读者——刚接触链表的新手可以按步骤慢慢跟，有经验的也可以直接跳到后面看边界条件和变种思路。

1. 先拆题：这道题真正在考什么

1.1 题目本身的描述

先把原题说清楚。给定两个升序排列的链表，比如l1 = 1 -> 2 -> 4和l2 = 1 -> 3 -> 4，要求把它们合并成一个新的升序链表，并且新链表仍然保持升序，最终结果是1 -> 1 -> 2 -> 3 -> 4 -> 4。题目给的是节点定义，通常是这样的结构：

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

链表的头节点代表整个链表的起始位置，每个节点只知道自己存的值和下一个节点是谁，这种线性结构决定了我们只能从前往后遍历，不能像数组那样随机访问。

1.2 题面背后的三个核心考点

这题表面是“合并”，实际上在考察三个基本能力：

第一个：对链表指针移动的掌控。和数组题不同，链表没有下标，你能做的就是通过next指针一步一步走。很多新手在合并时容易把指针指乱，搞出环或者丢节点，根源就是对“谁动了、谁没动”缺乏清晰认知。

第二个：对“哑节点”这个技巧的运用。这是链表题里极其常用的一招。新链表需要一个起点，但一开始这个起点是空的，直接拿l1或l2的头节点当新链表的头，写起来会非常别扭，因为你要单独处理“第一次选谁当头”。哑节点（dummy node）就是先造一个占位的空节点，最后返回dummy.next，让整个合并过程变得统一流畅。

第三个：边界条件的完备性。两个链表可能一个为空、可能两个都为空、可能在合并过程中一个先走完。这些情况如果不提前想清楚，代码很容易在运行时抛空指针异常。

1.3 这道题为什么值得反复刷

《21. 合并两个有序链表》在力扣上是“简单”难度，但它的价值不在于难度，而在于它是一系列高频题的共同基础。力扣第23题“合并K个升序链表”就是本题的N路扩展；第148题“排序链表”中间步骤需要用到两个有序链表的合并；第86题“分隔链表”虽然思路不同，但对指针的精细操作要求完全一致。把这题吃透，后面遇到这些题时会顺畅很多。

我个人的建议是：这题至少要能写出迭代版和递归版两种解法，并且能在不看题解的情况下把两种思路完整推导一遍。这并不难，但带来的回报很直接——面试中凡是涉及链表操作的问题，核心都在于对指针和边界条件的把握，而这题恰好把这两点练得最充分。

2. 迭代解法：把每一步指针移动都安排明白

2.1 核心思路：谁小谁先走

迭代法的思路用一句话就能说清：同时遍历两个链表，比较当前两个节点的值，把值较小的那个接到结果链表上，然后让对应链表的指针前进一步。重复这个过程，直到某一个链表走完，再把剩下的链表整体拼接上去。

这个过程可以用排队来类比：两个队伍的人已经按身高从低到高排好了，现在要把他们合成一个队伍。每次看一眼两个队头的个子，把矮的那个拉出来站到新队伍末尾，然后看下一个。当其中一个队伍空了，直接把另一个队伍剩下的人整个接上。

2.2 用哑节点统一处理

写代码前，先想清楚一个问题：新链表的头从哪里来？

一种朴素做法是：先单独比较l1和l2的头节点，把较小的那个作为新链表的头，然后进入循环。这能用，但代码会多一个分支，而且逻辑上不够统一。更干净的方式是使用哑节点：

dummy = ListNode(-1) cur = dummy

dummy节点本身不存有效数据，它的作用只是给新链表一个起始的挂载点。合并过程中，cur始终指向新链表的最后一个节点，每次接入一个新节点，cur就移动到新节点上。最终返回dummy.next，就能拿到真正的新链表头。

这一步初看有点绕，但它是链表题最常见的统一化技巧。后面写“合并K个链表”的优先级队列解法时，哑节点同样会让代码简洁很多。

2.3 完整代码（Python版）

class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(-1) 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

这段代码短，但每一行都有讲究。while l1 and l2保证了比较的安全性——只要有一个链表为空，循环就结束，不会出现空指针访问。if l1.val <= l2.val这里用<=而不是<，是为了保证稳定性——如果两个值相等，优先取l1的节点，这属于细节层面的严谨性，面试时说出来是加分项。最后那句cur.next = l1 if l1 else l2是整个函数里最省心的一行，它同时处理了三种情况：l1为空、l2为空、两者都为空。

2.4 再给一个Java版本和C++版本

class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummy = new ListNode(0); ListNode cur = dummy; while (l1 != null && l2 != null) { if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } else { cur.next = l2; l2 = l2.next; } cur = cur.next; } cur.next = l1 != null ? l1 : l2; return dummy.next; } }

class Solution { public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* dummy = new ListNode(0); ListNode* cur = dummy; while (l1 != nullptr && l2 != nullptr) { if (l1->val <= l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } cur->next = l1 != nullptr ? l1 : l2; return dummy->next; } };

三种语言逻辑完全一致，唯一要注意的是C++里new出来的dummy节点需要手动释放内存，不过在实际刷题环境中通常不追究这一点，面试时提一句“工程上要注意delete”反而显得有经验。

2.5 边界条件逐个过一遍

写链表题最怕的就是边界条件想不全。我把这题的边界情况列出来，你可以对着检查自己的代码：

细看会发现，只要while条件正确、最后一步拼接代码写对了，上面所有情况都能覆盖到。这也是为什么我说哑节点加循环加尾部拼接这个模式，是链表合并题的标准答案——它天然免疫了大部分边界问题。

3. 递归解法：把大问题切成同构的小问题

3.1 递归的思考方式

如果说迭代是“一步一步走”，递归就是“我只需要解决当前这一步，剩下的交给同样的规则”。对于合并两个链表来说，定义merge(l1, l2)为“合并两个链表并返回新链表的头节点”，那么这一步的操作其实只有两种可能：

• 如果l1.val <= l2.val，新链表的头应该是l1，而l1.next之后的部分和l2需要按同样的规则继续合并；
• 否则，新链表的头是l2，l1和l2.next继续合并。

可以看到，每一次递归都在缩小问题的规模——其中一个链表的节点数量减少了。递归的终止条件也很自然：当l1为空时，直接返回l2；当l2为空时，直接返回l1。

3.2 递归代码实现

class Solution: def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode: 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

这段代码非常简洁。核心在于赋值语句l1.next = self.mergeTwoLists(l1.next, l2)——它把原链表的一个节点“拆”下来，让它的next指向后续合并的结果。每一步递归都会从l1或l2中取出一个节点作为返回值的头，因此递归深度等于两个链表的总长度。

3.3 递归过程可视化：用例子走一遍

拿l1 = 1 -> 3、l2 = 2 -> 4举例。调用merge(1->3, 2->4)时，因为1 <= 2，所以取l1的1，然后递归调用merge(3, 2->4)。在merge(3, 2->4)里，3 > 2，于是取l2的2，递归调用merge(3, 4)。merge(3, 4)里3 <= 4，取l1的3，递归调用merge(null, 4)。此时l1为空，直接返回4。逐层回溯后拼出来的新链表就是1 -> 2 -> 3 -> 4。

推动过程可以用一个简单的括号表达：

merge(1->3, 2->4) = 1 -> merge(3, 2->4) = 1 -> 2 -> merge(3, 4) = 1 -> 2 -> 3 -> merge(null, 4) = 1 -> 2 -> 3 -> 4

看到没？递归的每一步都没有动太多脑筋，但这个“无脑信任递归函数本身”的能力，恰恰是新手最需要练习的。

3.4 递归版有什么优缺点

递归版最大的优势是代码可读性高，逻辑清晰，不需要额外的哑节点，也省去了手动控制循环变量的麻烦。面试时写递归容易给面试官留下思维清晰的印象。

但递归也有代价。每层递归都会消耗调用栈空间，如果链表特别长（比如几十万个节点），递归深度过大可能导致栈溢出。迭代版的空间复杂度是O(1)，递归版则是O(n)，其中n是两个链表的长度之和。后面会详细算这笔账。

4. 复杂度分析：面试官一问就能答上来

4.1 时间复杂度：O(m + n)

不管迭代还是递归，每一步只处理一个节点。最坏情况下，两个链表的所有节点都需要被遍历一次，所以总的时间复杂度是O(m + n)，其中m和n分别是两个链表的长度。这里没有额外的比较开销，每个节点的比较次数都是常数级，因此这个复杂度是渐进最优的——毕竟合并两个有序链表至少需要查看所有节点才能确定最终顺序。

4.2 空间复杂度：两个版本差距明显

迭代版额外只用了两个指针变量（dummy和cur），不随输入规模增长，因此空间复杂度是O(1)。递归版每递归一层就占用一份栈帧，栈帧数量等于两个链表总节点数，因此空间复杂度是O(m + n)。在面试中，如果递归版能主动说出这个代价，并补充一句“工程上倾向于用迭代避免栈溢出”，面试官一般都会认可。

4.3 关于稳定性

假设两个链表中有相同值的节点，比如l1 = 1 -> 2 -> 5，l2 = 1 -> 3。合并结果是1 -> 1 -> 2 -> 3 -> 5。问题来了：两个值为1的节点谁在前？我的迭代版和递归版都用了<=，所以l1的1会排在l2的1前面。如果要求保持原始链表内的相对顺序（即稳定性），这个细节就很重要。大部分教科书算法都要求归并排序是稳定的，本题的合并操作作为归并排序的核心子过程，用<=也是一个好习惯。

4.4 复杂度速查表

5. 力扣提交中的隐藏细节与调试经验

5.1 你可能会写错的三个地方

我在力扣上提交这题时，差别不过几行代码，但新手经常会在这几个地方翻车：

第一个：忘记改cur指针。很多新手在把cur.next指向新节点后，忘了把cur移动到新节点上，结果新链表只有两个节点，后面的全部丢失。这类问题肉眼很难看出，需要逐步跟踪。一个实用建议是画三列“快照”：一列是cur当前指向哪个节点，一列是l1现在到哪了，一列是l2现在到哪了。每次循环结束前检查三列是否和预期一致。

第二个：返回值写错。有人写return dummy，有人写return cur，这两个都不对。dummy是占位节点，它的next才是真正的新链表头；cur指向的是最后一个节点，用它作为返回值只能拿到最后的节点。正确写法是return dummy.next。

第三个：边界条件不完整。比如把while l1 and l2错写成while l1.next and l2.next，一旦链表只有一个节点就会空指针。或者少了最后拼接剩余链表的那句cur.next = l1 if l1 else l2，结果合并结果总是丢一半。建议在本地把上面那张边界条件表逐个测一遍。

5.2 调试链表题的通用方法

链表题在力扣上直接跑用例很方便，出错时会显示节点的顺序，但如果你只想看中间某一步的状态，可以写一个辅助打印函数：

def print_list(head): res = [] while head: res.append(str(head.val)) head = head.next print(' -> '.join(res))

然后在循环里的关键位置调用它，观察l1、l2、cur的变化。这个方法虽然简单粗糙，但在排查指针问题时比盯着代码脑内模拟高效太多了，尤其面对复杂链表题时。

这里分享一个我自己的经验：链表题出错时，先别看输出结果，而是先想“我的指针最后一次变化是在哪一行”。链表题的大部分bug都是指针指向了错误的位置，而不是值比较出错。值比较错了输出可能是乱的但结构还在，指针错了往往是丢链或者成环。分清这两类问题能少走很多弯路。

5.3 本地运行完整示例

在力扣里可以直接跑，但如果想在本地调试，要自己构造测试用例。一个小模板：

def build_list(arr): dummy = ListNode(-1) cur = dummy for val in arr: cur.next = ListNode(val) cur = cur.next return dummy.next l1 = build_list([1, 2, 4]) l2 = build_list([1, 3, 4]) merged = Solution().mergeTwoLists(l1, l2) print_list(merged) # 期望输出：1 -> 1 -> 2 -> 3 -> 4 -> 4

有了这个模板，你可以把网上看到的测试用例直接复制进来验证，不用每次都在力扣网页上反复提交。

6. 延伸题：从第21题到第23题，合并K个有序链表

6.1 最常见的面试追问

面试官在你答完这题后，九成会追问一句：“如果现在不是两个链表，而是K个链表呢？”这就是力扣第23题“合并K个升序链表”的原型。你不要慌，这道题的解法可以从第21题延伸出来。

最暴力的方法是每次从K个头里找最小值，时间复杂度O(K * total)。稍微聪明一点的是“两两合并”：先合并链表1和2，再把结果和链表3合并，以此类推。这个做法每轮都要重新遍历已经合并出来的长链表，总的时间开销并不理想。

最推荐的方案是使用最小堆或者优先队列：先把K个链表的头节点放进一个大小为K的最小堆，每次从堆里弹出最小的节点，接到新链表上，再把这个节点的next节点推入堆中。因为堆操作是O(logK)的，总复杂度是O(total * logK)，其中total是所有节点的总数。实现时，哑节点的作用依然明显，堆的初始化和每次“弹出的节点接上，再把后继节点塞回去”这个流程，仔细看就是第21题每步操作的泛化版本。

6.2 为什么优先队列能保证顺序

你可能会想：堆里只存K个元素，凭什么弹出来的顺序就是全局有序的？原因很简单——K个链表各自内部都是升序的，所以全局最小值一定出现在K个链表的头节点之一。每弹出一个最小头节点，它的后继节点成为自己链表的新头，放进堆里参与下一轮比较。堆始终维护着K个链表的当前头，每次弹出的都是所有剩余节点里的最小值。这个过程保证了全局升序，不需要额外比较其他节点。

6.3 其他相关变种题目

顺着这个思路，还可以接着看第88题“合并两个有序数组”，这是链表合并的数组版本，要求原地合并；第148题“排序链表”要求在O(n log n)时间内对链表排序，归并排序的合并步骤就是本题的迭代版。把第21题和这几题放在一起刷，你会明显感觉到“合并有序序列”这个主题的普适性。

我自己的刷题顺序是：第21题 → 第88题 → 第23题 → 第148题，每道题都试图在上一题的基础上增加一点点复杂度。这样比在网上随机刷题要高效得多，因为每道题的知识点都有重合，理解深度会层层递进。

7. 最后聊聊刷题的取舍

第21题虽然简单，但它给了我一个很重要的提醒：很多题目的价值不在“会不会做”，而在“能不能讲清楚”。我见过不少人看一遍题解就觉得自己会了，但面试时要求手写这个函数，写是写出来了，问一句“为什么这里要用哑节点”就答不上来。

如果你现在开始刷链表题，我的建议是不要只做这一道就往前冲。把它和上面提到的几道题放在一组，用一个周末集中突破。判断标准很简单：不看答案能不能写出迭代版和递归版、能不能画出递归调用过程、能不能说清时间和空间复杂度、能不能在追问“如果是K个链表呢”时给出思路。

这题还有一个容易被忽略的点：在新链表上，我们直接复用了原有链表节点，没有新建任何节点。这一点在面试中值得主动提一句——说明你意识到合并操作是“改变指针指向”，而不是“复制节点值”。这体现的是对链表这种数据结构本质的理解，远比背代码更能打动面试官。

我记得自己第一次在纸上画这道题的递归展开时，画了整整一页才真正明白每一层调用发生了什么。从那以后，再碰到链表递归题，我都有了章法：先判断当前层需要解决的最小问题，找到递归体和终止条件，其余交给函数自身。第21题恰好是建立这种思维最好的训练场。希望这篇拆解能帮你省下一些当初我绕过的弯路。