1. 这道题为什么值得认真对待
先亮明身份：我是常年和数据结构、算法题打交道的工程师。带过的实习生、考研的学生、面试的人里，十个有七个会在"两个有序链表合并"这道题上栽跟头。题目本身简单到一句话能说清——把两个递增有序的链表，合并成一个新的递增有序链表——但往往越是这种题，越能暴露一个人对指针、边界条件、内存管理的理解是否扎实。
我第一次认真做这道题，是在准备考研专业课的时候。当时《数据结构》教材的链表章节排在绪论之后，习题2.5就是这道题。说实话，那时候我照着答案抄了一遍，以为自己会了。直到后来在项目里写归并排序的链表版本，被一个"少移动tail指针"的bug折磨了两个小时，才意识到当初根本没学透。
这道题最大的价值在于：它是归并排序的merge操作在链表形态下的最小实现。归并排序大家都知道，把数组拆成两半，分别排序，再合并。换成链表时，拆分和合并的形态会有变化，但"合并两个有序序列"这一步是完全一样的。外面那些更复杂的东西——多路归并排序、外部排序里的归并阶段、数据库里的merge join操作——内核都是这道题。所以你不把这道题吃透，后面会遇到一连串麻烦。
再说直白一点，LeetCode上的第21题"Merge Two Sorted Lists"就是这道题。大厂面试手撕算法时考它，不是因为题难，而是因为代码量小、涵盖的知识点足够多，能快速看出你会不会用哨兵节点/虚拟头节点、懂不懂避免无效判断、写出来的代码是否简洁可维护。
这篇文章里，我会把我实际写过、调试过、总结过的全部经验放出来，包括迭代解法和递归解法的代码、各种隐藏的边界条件、测试用例怎么设计、以及我踩过的所有坑。不需要特别深的功底，只要你懂链表的基本概念，就能跟上。
2. 先理清题目里三个容易被忽略的隐性条件
2.1 "利用原有结点"和"新建链表"是两种完全不同的写法
很多同学第一次看到这道题，第一反应是：把两个链表的值拷贝出来，放进一个新链表。这样真做出来，从输出结果上看没错，但这恰恰是教材习题最想考察的反面。
考研教材里这道题的原文一般会带一句"要求利用原表的结点空间，不额外申请新的结点"。意思是：你只能在原有节点之间改连线，不能malloc新节点来保存数据。这道题考察的是指针重接，不是值拷贝。
为什么这么要求？一方面是为了考察你是否理解链表在内存里是怎么存数据的——节点分散在各个地址上，只能通过next把前后关系串起来，合并的本质就是改变next的指向；另一方面是空间复杂度的要求，O(1)的辅助空间，而不是O(n+m)的新空间。你要是用数组或者新建节点去做，功能上没错，但违背了这个题目考察的意图，考试时至少要扣分。
2.2 带头结点还是不带头结点，处理方式不一样
这是习题和LeetCode之间最大的差异之一。国内教材的链表题，绝大部分默认带头结点。头结点是一个不存数据的节点，它存在的意义是让链表的删除、插入操作不需要区分"删第一个节点"和"删中间节点"，统一处理。而LeetCode版本是不带头结点的，直接给你第一个数据节点的指针。
这两种形式下，合并逻辑的主干一样，差别体现在初始化和返回头上。带头结点的写法，往往是把其中一个链表的头结点直接拿过来当作结果链表的头结点使用，最后返回这个头结点；不带头结点的写法，通常需要创建一个临时的虚拟头节点（dummy node）站在最前面，把合并后的节点一个个挂上去，最后返回dummy的next。
我建议你把两种都写一遍。因为面试时你遇到的输入不一定是什么形式，如果你只会LeetCode版的dummy写法，遇到带头结点、且要求你用原来头结点的说法，就会不知所措。
2.3 相同元素保留还是去掉，决定了比较符号
题目里只说了"有序"，没说是否有重复值。经典的合并要求是：合并后仍然递增有序，如果两个链表里有相等的值，它们都要出现在结果里。比如链表A有1、3，链表B有3、5，合并结果是1、3、3、5。
这时候写代码就比较稳妥了：
if (p->data <= q->data)注意这里用的是<=。用小于等于，当p和q指向的值相等时，优先取p那边的节点。这样写不会漏数据。如果你用了<，相等时取else分支，逻辑上也没错，结果还是有序的，但相等值从哪边取就变得不直观了。当然，我说的是标准练习题的做法，如果题目明确要求去重，那又是另一套写法了。
还有一个小细节：如果两个链表本来就是各自递增的，用<=能保证合并后相同值的相对顺序和原来一致，这在某些场景下算是稳定排序性质。教材上一般不特意强调，但你心里有数就好。
2.4 链表节点的基本定义
下面代码是我这篇文章里统一用的节点定义，带头和不带头场景我都基于它。如果你用的是C++，可以写成struct的构造函数形式，但C语言的写法更有助于看清内存操作：
typedef struct LNode { int data; struct LNode *next; } LNode;3. 迭代解法：把"接线"这个动作写干净
3.1 核心思路：双指针交替指向较小节点
迭代解法是整个题目最推荐的写法，它思路直接、空间复杂度O(1)、适合链表长度很大的场景。
我们先说不带头结点的情况。假设你有两个链表的头指针list1和list2，它们都指向第一个数据节点。合并的过程可以想象成两个队伍的人往一条新队伍里排队：队伍A和队伍B各派出一人站在队首，谁的值小谁先出列站到新队伍末尾，然后它背后的那个人顶上，继续比较。
用代码表示，需要一个"虚拟头节点"来起步：
struct ListNode { int val; struct ListNode *next; }; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode dummy; // 虚拟头节点，栈上分配 struct ListNode* tail = &dummy; // tail始终指向结果链表的最后一个节点 dummy.next = NULL; while (list1 && list2) { if (list1->val <= list2->val) { tail->next = list1; list1 = list1->next; } else { tail->next = list2; list2 = list2->next; } tail = tail->next; // 这一步非常容易忘 } // 循环结束后，一个链表已经走完，另一个可能还有剩余节点 tail->next = list1 ? list1 : list2; return dummy.next; }3.2 为什么非要用虚拟头节点
很多人一开始会写这样的代码：先判断list1->val和list2->val哪个小，把结果链表的头指针指向小的那个，然后再进入循环。这样写有一个麻烦：结果链表的第一个节点需要单独处理，循环体内变成"先接节点、再判断是否是第一个节点"。
虚拟头节点的核心思想就是：让第一个节点和后面的节点享受同样的处理逻辑。它本身不存数据，它存在的唯一意义是让tail->next在一开始有一个确定的指向位置。因为我们的返回值是dummy.next，所以这个虚拟节点不会被带出去。它就像一个临时垫在底下的桌垫，桌布铺好了，垫子自然可以留在原地。
这里有个小细节：dummy直接定义成结构体，而不是malloc出来的指针。原因很简单，虚拟头节点不需要长期存活，函数栈上定义它，生命周期正好覆盖整个函数执行期间，函数返回后自动失效，不用手动free，不会泄漏内存。如果你习惯用malloc创建虚拟头节点，在返回结果前得先free掉它，否则每次合并都会泄漏一个节点大小的内存，积少成多就很麻烦。
3.3 循环结束后的那一步到底在干什么
循环条件是while (list1 && list2)，只要两个链表都没走完，就一直比较、接线。循环退出时一定有一个链表走到了末尾（指针为NULL），另一个链表可能还剩一串节点，也可能也刚好走完。
关键点来了：剩下的那一整串节点，本身就是有序的，而且它们的值一定都不小于已经合并好的最后一个节点的值。比如链表A是1、3、5、7，链表B是2、4、6。走完循环后，链表B的6被接进去，链表A还剩7。此时不需要再比较、再调整，直接把tail的next指向剩下那个7即可。如果你还在傻傻循环去逐个比较，说明你对"有序"这个前提条件利用得不够充分，这是很多初学者的通病。
3.4 带头结点场景的另一种写法
如果题目明确说"链表带头结点"，而且要求不额外申请节点，最经典的做法是以A的头结点作为C的头结点，最后释放B的头结点。这种写法在考研习题答案里经常出现，也是我当年被老师重点要求背下来的版本：
LNode* mergeTwoLists(LNode* La, LNode* Lb) { LNode* tail = La; // 用A的头结点作为结果链表的头 LNode* p = La->next; LNode* q = Lb->next; while (p && q) { if (p->data <= q->data) { tail->next = p; p = p->next; } else { tail->next = q; q = q->next; } tail = tail->next; } tail->next = p ? p : q; free(Lb); // B的头结点已经没用了，释放掉 return La; // 结果链表的头结点就是A原来的头结点 }我明确说一下，这个写法有个副作用：原链表A和B的数据节点都被重新连到了同一个链表里，你再也无法通过La或Lb的头指针单独访问原来的链表了。如果你后续还想用原来的链表，就要小心。面试时主动跟面试官确认"这个合并是否允许修改原链表"，是很加分的交流，因为很多人不会意识到这点。
3.5 时间复杂度和空间复杂度
时间上，每个节点最多被比较一次、被接线一次，总耗时O(m+n)，其中m和n是两个链表的长度。空间上，只用了几个指针变量和一个栈上的虚拟节点头，辅助空间是O(1)。这就是这道题最理想的状态：时间线性，空间常数。
4. 递归解法：公式化写法，但要警惕递归深度
4.1 先写核心递归公式
递归解法很多人觉得难，但它其实有一个很好记的公式。有函数merge(a, b)：返回的是合并a和b两个链表后的头节点。
- 如果a为空，返回b
- 如果b为空，返回a
- 如果a的值较小，那么最终结果的头节点是a，a的next应该指向
merge(a->next, b)的结果 - 如果b的值较小或相等，那么最终结果的头节点是b，b的next应该指向
merge(a, b->next)的结果
翻译成C语言：
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { if (!list1) return list2; if (!list2) return list1; if (list1->val <= list2->val) { list1->next = mergeTwoLists(list1->next, list2); return list1; } else { list2->next = mergeTwoLists(list1, list2->next); return list2; } }这段代码的递归深度是O(m+n)。每次递归调用时会把当前比较较小值的函数状态压入调用栈，等递归返回后再一层层释放。链表长度几百个节点根本感觉不到，但如果你在真实项目里合并一个十万节点的链表，就很容易把栈空间打爆，导致程序崩溃。这就是为什么我在生产代码里几乎不用递归写法，但在笔试、面试的时候，我仍然建议你先把递归版本写出来。
4.2 为什么很多教材推荐递归写法
因为代码短、和自然语言描述几乎一一对应，便于阅卷老师快速看懂你的思路。很多考研真题的标准答案就是递归写法，你不背下来，考试时临时想迭代版本虽然也能写，但代码长度更长，出错概率更高。
而且递归写法的核心逻辑非常漂亮：它把"合并两个链表"的问题，不断化简成"合并更小的链表"的问题。每递归一层，至少有一个链表往前推进一个节点，所以总能在有限层数内结束。
4.3 递归的三个坑
第一个坑：忘记终止条件。如果不在函数开头判断list1或list2为空就返回另一个，递归永远不会结束，直接栈溢出。
第二个坑：没有把返回值接好。很多人写递归时，只做了if (list1->val <= list2->val) return list1;，忘了把list1->next指向递归结果。这样合并不完整，后面所有节点都丢了。
第三个坑：递归深度。前面说了，深度是O(m+n)。实际开发中，如果一个链表有几万甚至几十万个节点，我强烈建议你用迭代版本。写递归版本前，先问自己一句话：这个链表的长度会不会超过栈空间能承受的规模？如果会，别用递归。
5. 测试用例设计：把边界情况一次测透
5.1 为什么功能对了还要专门设计测试
很多同学写完代码，拿题目给的示例一跑，输出对了，就觉得完成了。问题在于，题目给的示例通常只有一两个，覆盖不到空链表、长度不一致、值全部相等这些边界场景。我在实际写这道题的时候，吃过一次亏：核心逻辑没问题，但忘了处理list1和list2都为空的场景，运行到if (list1->val <= list2->val)时直接段错误。
从那以后，我给自己定了一个规矩：凡是写链表类题目，必须设计一套覆盖主要边界的测试用例。与其说这是为了考试，不如说是在培养一种工程思维——你写的代码最终是要被别人调用的，调用者不一定会按你的假设传参。
5.2 六组经典边界用例
我建议按下面这个表格来清点测试用例：
| 用例编号 | 链表A | 链表B | 预期合并结果 | 为什么值得测 |
|---|---|---|---|---|
| 1 | 空 | 空 | 空 | 验证空指针处理 |
| 2 | 空 | 5 | 5 | 验证一空一非空 |
| 3 | 1 | 2 | 1, 2 | 基本比较逻辑 |
| 4 | 1 | 1 | 1, 1 | 相等值是否保留 |
| 5 | 1, 3, 5 | 2, 4, 6 | 1, 2, 3, 4, 5, 6 | 交替交叉，核心场景 |
| 6 | 1, 2 | 3, 4, 5 | 1, 2, 3, 4, 5 | 一个链表全部小于另一个 |
第六组尤其容易被忽略。很多人测试时只想到交替插入，没想到一个链表整体小于另一个。如果主循环结束后你没有拼接剩余节点的代码，这种情况会丢数据。测试用例设计得越全面，你代码里的bug被强行暴露得越早，这是省时间的策略。
5.3 一个可以直接拿来用的测试骨架
我平时写链表题，都会先写三个工具函数：buildList构造链表、printList打印链表、freeList释放链表。这几个函数几乎不会变，写完一次可以到处复用。下面是一个C语言写的完整测试骨架：
#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node* buildList(int arr[], int n) { Node dummy; dummy.next = NULL; Node* tail = &dummy; for (int i = 0; i < n; i++) { Node* node = (Node*)malloc(sizeof(Node)); node->data = arr[i]; node->next = NULL; tail->next = node; tail = node; } return dummy.next; } void printList(Node* head) { while (head) { printf("%d -> ", head->data); head = head->next; } printf("NULL\n"); } void freeList(Node* head) { while (head) { Node* tmp = head; head = head->next; free(tmp); } } int main() { int a[] = {1, 3, 5}; int b[] = {2, 4, 6}; Node* listA = buildList(a, 3); Node* listB = buildList(b, 3); Node* merged = mergeTwoLists(listA, listB); printList(merged); // 期望输出: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL freeList(merged); // 合并后原链表节点已混在一起，统一释放合并链表即可 return 0; }注意最后一行的注释：因为你复用了原节点，合并后listA和listB里的所有节点都串到了merged上，所以不能再单独freeList(listA)和freeList(listB)，否则同一个节点被释放两次。要么你只释放merged，要么你压根别调用freeList。这是链表题里特别常见的内存管理陷阱。
5.4 断言帮你自动检查结果
上面用printList肉眼核对结果，终归是人工的。我更推荐在测试里加上断言，让程序自己判断合并结果对不对。尤其当你后面要写更复杂的变体（比如k路归并）时，断言能节省大量人力。
int checkResult(Node* head, int expected[], int n) { for (int i = 0; i < n; i++) { if (!head || head->data != expected[i]) return 0; head = head->next; } return head == NULL; }然后在main里写：
int expected[] = {1, 2, 3, 4, 5, 6}; if (checkResult(merged, expected, 6)) { printf("test passed\n"); } else { printf("test failed\n"); }这比肉眼盯着终端强多了。代码一旦改动，跑一遍测试就能立刻发现问题。
6. 最容易踩的坑和我的调试经验
6.1 五个真实的翻车现场
这道题代码短，但坑很密集。我把自己踩过、以及帮别人排查过的常见问题整理成下面几类：
忘记移动tail指针。很多人写完
tail->next = p或者tail->next = q后，没有执行tail = tail->next。结果就是：结果链表永远只有最后一个被接进去的节点，前面的节点全部丢了。这个错误的隐蔽之处在于，如果两个链表只有一个节点，你根本看不出来问题——因为每次接完节点后tail本来就指向结果链表的最后一个节点，不需要再移动。但节点一多，立刻出bug。循环结束后没拼接剩余链表。如果在
while (p && q)结束后直接返回head，链表较长时大概率丢数据。正确写法我已经强调过，tail->next = p ? p : q这一行必须加。带头结点时没有跳过数据节点。有人写
p = La而不是La->next，把带头结点的头结点data也当作数据参与比较。头结点data通常没初始化，是个无意义的值，结果链表里会出现一个脏数据节点。递归版本没有处理空链表终止条件。开头就判断
if (!list1) return list2;和if (!list2) return list1;，不能少，顺序也不能颠倒。没有意识到原链表结构被改变。函数执行完，你拿着原来的listA头指针去遍历，会发现链表变短了，甚至节点顺序也乱了。这不是bug，而是"复用原节点"这种设计本身的副作用。如果你希望合并后原链表还能用，唯一办法是复制节点，新分配内存。面试时最好主动说明这一点。
6.2 调试链表问题的杀手锏：指针快照
链表出问题时，靠脑子想象很难定位。我教你一个土办法：在关键步骤打印当前三个指针各自指向的节点，以及结果链表已经连好的部分。不需要什么复杂工具，printf就够了。
void debugSnapshot(Node* p, Node* q, Node* tail) { printf("p=%d, q=%d, tail=%d\n", p ? p->data : -1, q ? q->data : -1, tail ? tail->data : -1); }在tail->next = ...这一行前后各调用一次，你能清楚看出每次循环里p、q、tail的移动是否符合预期。如果tail的值连续两次一样，说明你忘了移动tail。
另外，我建议在打印链表时不要只打印data，最好把节点的地址也打出来。比如：
void printListWithAddr(Node* head) { while (head) { printf("%d(%p) -> ", head->data, head); head = head->next; } printf("NULL\n"); }为什么要打地址？因为链表是靠指针连接的结构，你光看值看不出有没有形成环。如果出现死循环，多半是某个节点的next指回了自己或者之前的节点。打印地址后，你一眼就能看出有没有重复的节点地址出现。
6.3 内存泄漏和重复释放的检测
C语言链表题最常见的隐藏问题就是内存泄漏和重复释放。一次合并泄漏一个头节点，看似无伤大雅，但如果这个函数在一个循环里被调用十万次，就是一个大瓶颈。
如果你用Linux，可以拿valgrind跑一下测试程序：
gcc -g merge.c -o merge valgrind --leak-check=full ./merge如果有泄漏，valgrind会明确告诉你哪一行malloc的节点没有被free。如果是重复释放，valgrind会直接报"Invalid free"。
如果环境是macOS，不习惯装valgrind，也可以用clang的地址消毒器（AddressSanitizer）编译：
clang -fsanitize=address -g merge.c -o merge ./merge地址消毒器会实时检测到堆缓冲区溢出、重复free、内存泄漏这类问题，比valgrind更快、更直观。我强烈建议你在本地练这道题时默认开启ASan，它能帮你避免很多隐性内存错误。
6.4 一个小习惯：写函数前先回答三个问题
我现在每次写这种"改链表结构"的函数，都强迫自己在脑子里回答三个问题：
- 函数的返回值是什么？新链表的头节点还是原链表的头节点？
- 函数会不会修改输入链表？如果会，调用方是否允许？
- 虚拟头节点/辅助节点应该在栈上创建，还是堆上创建？谁负责释放？
这三个问题答案想清楚，写出来的代码基本不会出现重大方向性错误。这道题尤其适用。很多同学写错不是因为语法不熟，而是没想清楚这三个问题就开始动笔，写着写着就乱了。
7. 从两路合并到K路归并：一题带出整个归并家族
7.1 归并排序的链表版本离不开它
归并排序的核心步骤就两个：分割和合并。数组版本的分割靠索引，链表版本的分割用快慢指针找中点。找到中点后，把左右两半分别排序，最后就是你写的这道题的合并操作。
所以，如果你能把这道题练得炉火纯青，再去写链表的归并排序，只是多写了"快慢指针找中点"和"递归排序两个子链表"这两个部分，merge部分直接复用。这也是我把这道题当成归并家族的地基来对待的原因。
7.2 两路扩展到K路的思路
真实场景中，往往不是合并两个有序链表，而是合并K个。比如外部排序里，内存读不下所有数据，就把数据分成K个有序段，每次从每个段里取最小的记录，合并成一个更大的有序结果。这种场景下，两路合并的思路可以推广。
朴素做法是：每次比较K个头节点，选出最小值接上去。这样选出N个节点，每次比较K次，总复杂度O(NK)。当K很大时，效率明显变差，于是就要用最小堆：把K个头节点的值都塞进一个小顶堆，每次弹出堆顶元素代表的最小值，然后从它所在的链表拉下一个新节点进堆，直到堆空。选最小值从O(K)降到O(logK)，总体复杂度O(N logK)。
这里面的核心思路和两路合并一脉相承：你还是一遍遍从候选节点头里选最小的那个，只是选择工具从"直接比较两个"换成了"堆"。掌握了这道题的基本逻辑，学习K路归并时你理解得会快得多。
7.3 实际项目里我还用它做过什么
除了算法题，我在业务代码里也用过类似的合并逻辑。有一段时间做数据导入功能，需要把两个不同来源但都已经排好序的文件合并成一个升序文件。文件太大，不能全部读进内存，我就是用这种"双路归并"的方式，分别打开两个文件，每次读取当前行，比较后写入结果文件，谁小谁前进。这就是这道题从链表形态迁移到IO流形态的样子。
还有一次处理多个独立时间段列表的合并，每个列表内部按开始时间排好序，需要合并成一个总时间线。当时的实现逻辑和链表合并几乎一一对应，只是节点换成了结构体对象，指针换成了数组下标。所以不要小看这道小题，它的思想真的会渗透到各种看起来八竿子打不着的地方。
最后分享一个我个人的习惯：每学一道经典算法题，我都会把两个版本（迭代版和递归版）都写一遍，并配上一套边界测试用例。这个习惯帮我省下过大量面试前临时抱佛脚的时间。这道题是我练习清单里出现频率最高的一道，也希望它成为你的工具箱里顺手的那把好工具。
