企业官网建设流程全解析

开头

LeetCode HOT 100 第21题：合并两个有序链表，这道题可以说是链表类题目里的“第一课”。很多公司面试的第一道算法题就是它，热度和使用频率在题库里常年排在前列。凡是系统刷过LeetCode的人，基本都绕不过这道题。它的代码量很短，短到只有十几行，但里面包含的东西一点都不少：哑节点、双指针、递归、边界条件处理……几乎每个话题拿出来都够面试官追问十分钟。适合准备算法面试的求职者，也适合刚入门数据结构、想通过一道题打通链表基本功的学习者。这篇文章我会把这道题的两种主流解法、背后的原理、刷题时容易踩的坑，以及面试中的常见追问，一次说清楚。

1. 题目拆解：先搞清楚“合并有序链表”到底在考什么

1.1 题目到底在问什么

题目本身描述非常简洁：给定两个升序排列的单链表，按顺序把两个链表合并成一个新的升序链表，然后返回新链表的头节点。听起来很简单，但这背后有几个隐含约束值得细说。

第一，链表是“引用的集合”，和数组不同，我们不能随机访问某个位置的节点，必须从头开始一个个走。第二，题目没有说“不能修改原链表”，所以一个合法的解法完全可以在原链表节点上做指针调整，不需要分配新的节点来存数据，这正是迭代法的核心思路。第三，两个链表可能是空的，也可能长度差异很大，边界条件处理必须完整覆盖所有输入情况。

面试里我见过不少人一上来就写得很顺，结果把合并后的链表输出出来发现少了节点，或者末尾指针没有断开，直接串到原链表的中间位置。这些问题的根源都是没有在动手前把“指针从哪来、到哪里去、谁连着谁”想清楚。

1.2 这道题为什么值得反复做

从面试角度说，这道题是“保底送分题”，也是“深挖追问题”。它短，所以作为开场题不会给候选人太大压力；但它又覆盖了链表操作中最核心的几个技巧，所以面试官很容易从中延伸出更复杂的变体，比如“合并k个有序链表”“链表归并排序”“判断两个链表是否相交”等。

从学习角度说，这道题是理解链表“引用语义”最好的载体。数组里我们交换两个元素，只是交换位置上的值；链表里调整顺序，本质是改变节点的 next 指向。很多人学链表总是迷迷糊糊，就是因为脑子里还停留在“数组思维”，没有建立“指针思维”。把这道题的迭代写法彻底吃透，你对“指针到底指向什么”会有一个质的提升。

2. 迭代法：哑节点与穿针引线

2.1 为什么不直接用一个新链表的头节点作为起点

先思考一个问题：合并后的链表，头节点到底应该是 list1 的头还是 list2 的头？这取决于两个头节点的值谁更小。如果单独写一个 if 分支去判断“谁做新头”，代码会多一条分支，而且后续每做一步都要维护“当前节点是谁”的状态，非常啰嗦。

更优雅的做法是引入一个哑节点（dummy node），也叫虚拟头节点。这个节点不保存任何有意义的数据，它的唯一作用是给新链表一个统一的起点。后续不管是 list1 的节点还是 list2 的节点接入，都通过同一个游标指针 cur 来操作，最后返回 dummy->next 就是真正合并后的头节点。这样在逻辑上就彻底消除了“第一个节点要单独处理”的尴尬。

我个人的体会是，哑节点的本质是一种“哨兵模式”。它不参与业务逻辑，却能把边界情况化成普通情况。这个技巧在链表题里几乎无处不在：删除倒数第k个节点、翻转链表的一部分、环形链表找入口……凡是头节点可能变化的题目，你都可以尝试用哑节点来简化逻辑。

2.2 迭代写法的完整实现与逐行剖析

先看完整的 C++ 实现，我习惯用 C++ 写算法面试题，因为它对指针的暴露最直白，最容易看出一个人是否真正理解链表：

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { ListNode* dummy = new ListNode(0); ListNode* cur = dummy; while (list1 != nullptr && list2 != nullptr) { if (list1->val <= list2->val) { cur->next = list1; list1 = list1->next; } else { cur->next = list2; list2 = list2->next; } cur = cur->next; } if (list1 != nullptr) { cur->next = list1; } if (list2 != nullptr) { cur->next = list2; } return dummy->next; }

这块代码的逻辑顺序非常重要。第一，比较的是 list1->val 和 list2->val，取较小者接入；第二，接入操作是 cur->next = list1，然后立刻让 list1 指向它的下一个节点，再让 cur 也往前移动一步。这两步“先接再移”的顺序一旦写反，就会出现当前节点还没接上，游标却已经跑到下一个位置的问题。

很多人第一次写的时候会问：为什么最后两个 if 可以直接把剩下的链表整段接上，不需要循环？因为剩下的那段链表本身已经是有序的，它内部的结构无需任何改动，只需要让新链表的尾节点指向它的头节点即可。这是链表合并和数组合并的一个显著区别。

2.3 复杂度分析和空间占用说明

迭代法的时间复杂度是 O(m + n)，其中 m 和 n 分别是两个链表的长度。因为每轮循环都会让 list1 或 list2 前进一步，最终最多走完两个链表的所有节点。

空间复杂度是 O(1)。这里有个容易误解的点：dummy 节点不是需要额外分配的吗？严格来说，dummy 节点占用的空间是常量级的，不随链表长度增长，所以算 O(1)。还有一种更“抠门”的写法，直接复用其中一个链表的头节点作为结果链表的头，不需要 new 哑节点，但那种写法要单独处理“第一个节点选谁”的分支，代码可读性会下降。我建议刷题阶段用哑节点，面试手写时也优先用哑节点，清晰比省一个节点的空间更重要。

3. 递归法：把大象装进冰箱的三句话

3.1 递归的本质是什么

递归解法的代码比迭代法更短，但是理解门槛更高。核心思路可以概括为：每次只解决“当前两个节点的比较”，剩下的部分交给递归函数自己去处理。

具体来说，如果 list1 的头节点值更小，那么这个节点就应该是合并结果的头节点，它的 next 应该是“list1 的下一个节点 和 list2 合并后的结果”。同理，如果 list2 的头节点值更小，就反过来。递归的出口是：有一个链表为空，那么直接返回另一个链表。

你可以把递归理解成一个“延迟承诺”。当前节点先确定“我该接谁”，至于“我的后面怎么排”，我不直接算，而是把问题缩小一点，再交给同样的函数。这个缩小问题的过程，就是递归的精髓。

3.2 递归写法完整实现

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) { if (list1 == nullptr) { return list2; } if (list2 == nullptr) { return list1; } if (list1->val <= list2->val) { list1->next = mergeTwoLists(list1->next, list2); return list1; } else { list2->next = mergeTwoLists(list1, list2->next); return list2; } }

这段代码的关键在于理解每一层递归的返回值。返回值永远是“那两个链表合并后的头节点”。所以当 list1->val 更小时，list1 的 next 就指向“list1->next 和 list2 合并后的结果”，然后整个函数返回 list1。这个逻辑其实和迭代法是完全一致的，只是换了一种表达方式。

很多初学者盯着这段代码看半天，感觉“好像看懂了，但想不出来”。我的建议是把递归调用展开成树状结构，手动写几次。比如 list1 = [1, 3, 5]，list2 = [2, 4, 6]，递归执行时每一层的返回值是什么、谁接了谁，拿笔画一遍就通了。

3.3 递归的空间代价到底是多少

递归法的空间复杂度不是 O(1)，而是 O(m + n)。因为每次递归调用都会在系统栈上占一层空间，最坏情况下递归深度等于两个链表的总长度。在面试中这是一个常见的追问点，有些人会把递归的空间复杂度答成 O(1)，这就是没搞清楚。

那递归法是不是就一定比迭代法差？也不是。递归代码简洁，展示的是对问题结构的理解；迭代代码显式可控，展示的是对指针的掌握。两者在面试中都是合格解。不过在实际系统中，如果链表特别长，递归深度过大可能导致栈溢出，所以生产环境我一般优先写迭代。

4. 边界条件与常见问题排查实录

4.1 极易踩空的边界条件

作为一道简单题，绝大多数提交出错的场景都集中在几个特殊的输入情况上。我整理了一份测试用例清单，建议写完代码后第一时间跑这些用例：

特别是“一个链表为空”的情况，很多人不是不会处理，而是忘记处理。我在模拟面试中见过不少候选人，一开始把 while 循环写对了，但循环结束后没有把剩余链表接上，导致输出缺了一截。

4.2 链表操作中的经典指针陷阱

第一个经典陷阱是“指针丢失”。比如你写 cur->next = list1 之后，必须先 list1 = list1->next，否则下次循环你还在用同一个 list1 节点，最后合并结果里会出现重复节点。顺序颠倒的直接后果就是死循环或者结果链表结构错乱。

第二个经典陷阱是“忘记移动 cur”。每次接完一个节点，cur 必须跟着往前挪一步，否则后面的节点会把前面的节点覆盖掉，结果链表只保留最后一个节点。我在审代码的时候遇到过几次这种问题，表现形式五花八门，但根因都一样：游标没有前进。

第三个经典陷阱是“提前返回 dummy”。正确写法是 return dummy->next，但总有新手写成 return dummy。这相当于多返回了一个值为 0 的哨兵节点，最后结果链表开头多出一个不存在的节点。这个错误特别隐蔽，因为在本地测试时可能因为打印逻辑没注意而被忽略。

4.3 常见问题速查表

5. 面试延伸：这道题还能引出什么考法

5.1 合并 k 个有序链表

这道题的进阶版是 LeetCode 23：合并 k 个有序链表。表面上是把两个链表换成 k 个，难度却直接跨了一个量级。最常见的解法有两种。

第一种是“两两合并”，把第 1 个和第 2 个合并，结果再和第 3 个合并，依次类推。这种方法实现简单，但总时间复杂度的推导有点意思。假设每个链表长度为 n，做 k-1 次合并，每次合并都能达到 O(kn) 的量级，整体就退化成 O(k²n)。面试时你需要能分析出这个复杂度。

第二种是用优先队列（堆）来维护 k 个链表的当前头节点，每次取出最小的节点接入结果，然后推入该节点的下一个节点。复杂度是 O(nk logk)，在 k 比较大的时候优势非常明显。这里需要你熟练使用堆这种数据结构，很多人卡在“优先队列里存放的是节点，比较器要按节点值排序”这个细节上。

5.2 与归并排序的关联

链表的归并排序核心就是“找中点、递归排序、然后合并”。其中“合并”这一步，用的就是这道题的 merge 逻辑。所以如果你把 21 题吃透了，链表归并排序其实已经完成了一半。

我建议把这两道题放在同一天刷。先写 21 题的迭代版本，再尝试写链表的归并排序，你会发现“排序”中最关键的一步你早就掌握了。而且链表的归并排序不需要额外开辟数组来存数据，空间复杂度可以做到 O(logn)，只靠递归栈的空间，这是它相对于数组归并排序的一个优势。

5.3 原地合并与内存优化

这道题还存在一个“不 new 任何节点”的变体要求。意思是你不能创建哑节点，也不能复制节点值，只能在原链表上调整 next 指针。解法依然清晰：先比较两个链表头节点，选较小者作为结果头，然后迭代合并后面的节点。

这种写法的意义在于展示你对“链表就是引用操作”的深度理解。但它的代码分支处理会稍微多一点，因为第一个节点必须单独选。我在实际手写时还是推荐带哑节点的版本，至少在白板上更容易讲清楚思路。面试中主动说一句“我也可以用哑节点来减少边界分支”，比憋半天写一个没有哑节点的版本要好得多。

6. 刷题之外的复盘笔记

6.1 这道题最优的刷法顺序

根据刷题经验，拿到这道题不要急着抄答案，而是按四个阶段来推进。第一阶段，用笔在纸上画出两个链表，模拟一遍指针移动过程，不看任何代码。第二阶段，自己写出第一个能通过的迭代版本，跑几个边界用例。第三阶段，尝试写递归版本，并分析两种写法的空间复杂度。第四阶段，打开编辑器的调试工具，在每个循环入口打印当前节点的值和指针位置，观察“接”“移”两个动作的执行顺序。

这四个阶段做完，你会发现自己对链表的“引用思维”有了很大的变化。以后再碰到“反转链表”“删除倒数第n个节点”这类题，至少不会在“指针到底指向哪”这个问题上卡壳。

6.2 个人一点实操建议

刷题这件事最怕的就是“看懂了但写不出”。我自己的做法是：每道题看完答案后，一定要把代码关掉，从头自己写一遍。如果写到一半卡住，就回顾一下卡住的那个点，而不是马上再看答案。这道题我前前后后带着不少人过过，大多数卡住的地方都很一致：“合并结束后剩余链表怎么接”“递归时返回的到底是谁”。想清楚这两个问题，这道题就是真正拿下了。

如果现在你准备面试，建议把这道题的迭代版本练到闭着眼睛能默写，然后把递归版本练到能流畅解释每一步的返回值和作用。你这道题的掌握程度，基本就代表了你在链表基本功这一块的下限。

6.3 后续还可以怎么扩展

这道题做完，可以马上接三道关联题：反转链表、删除链表的倒数第N个节点、环形链表。这三道题加上本题，就构成了链表最核心的五个操作：合并、反转、删除、判环、找中间点。把这五类操作都吃透，链表面试就基本不虚了。

另外还有一个思维扩展点，就是你把合并两个有序链表理解为“双指针归并”，这个概念会反复出现在数组的合并有序数组、字符串的交替拼接等场景里。所以这道题的本质并不只在链表本身，它是“归并思想”的缩影。有了这层理解，下次遇到任何“两个有序结构合并成一个有序结构”的问题，哪怕它长得再奇怪，你的第一反应都会是双指针。