LeetCode 21 合并两个有序链表：C语言指针操作与哨兵节点详解

我拿这道题去面过不少应届生，也看大家刷题打卡提到过LeetCode 21。每次看到"合并两个有序链表"被标记成简单题，我都想说：简单是简单，但能把C语言版本一次写对的人，确实不多。本质原因很简单——这题考的不是递归或迭代谁更聪明，而是你的指针操作节奏、对NULL的敏感度、以及"这是接节点不是造节点"的意识。这篇就用C语言从头到尾把这道题拆开：从思路推导、代码逐行拆解、递归与迭代两版实现，到调试技巧、边界用例、面试变形题，一次讲透。适合正在刷链表专题、准备校招笔试面试、或者刚学完单链表想找一道经典题练手的读者。

1. 一道"简单题"刷出三道坎：先看清题目在考什么

1.1 题目原样：升序合并到底在说哪件事

题目原文不复杂：给定两个升序链表list1和list2，把它们合并成一个新的升序链表并返回。两个链表的节点数目范围是[0, 50]，节点值范围是[-100, 100]。举例：输入1->2->4和1->3->4，输出1->1->2->3->4->4；如果其中一个为空，直接返回另一个。

很多人在第一句话就理解偏了。题目说的是"合并成一个新的升序链表"，但并不是让你malloc出一堆新节点，而是把已有节点的 next 指针重新接起来。这一点在C语言里特别容易走偏：有人一上来就struct ListNode* node = (struct ListNode*)malloc(...)循环分配新节点，最后两个旧链表还留在内存里。虽然结果对了，但空间复杂度变成 O(m+n)，完全违背了题目考察的本意。

在LeetCode上这题默认允许复用原有节点，面试时也默认可以原地修改输入链表。搞清楚这个前提，思路就顺了。

1.2 三个最容易暴露功底的方向

以我旁观面试和刷题群反馈的经验，这题真正筛选人的点有三个：

1. 头节点会不会处理。两个链表的头节点不一定是最终结果的头，因为较小的那个才应该排在前面。很多人写循环时先判断head == NULL，再单独处理第一个节点，代码瞬间长出三条分支。
2. 指针移动的节奏。接一个节点、往前走一步，这个"一步"写到哪个位置很讲究。写错位置要么死循环，要么反复接同一个节点。
3. 空指针判断的顺序。l1->val <= l2->val这行代码之前，必须保证l1和l2都非空。顺序反了，LeetCode直接给你一个AddressSanitizer: heap-buffer-overflow。

这三个方向，正好对应后面要展开的哨兵节点、尾插法和收尾处理。

1.3 这道题是所有归并类问题的地基

为什么叫"链表经典题"？因为它本质上是归并排序中merge步骤的链表版本。数组版本的归并需要一个临时数组，链表版本却可以做到原地连接——这正是链表指针操作的核心优势。这道题吃透之后，下面这些题都只是它的变体：

• LeetCode 88 合并两个有序数组：同样的双指针，从后往前填；
• LeetCode 23 合并K个升序链表：两两归并的分治用法；
• LeetCode 148 排序链表：链表归并排序里就有一句mergeTwoLists(left, right)直接复用本题代码；
• 面试里常问的"外部排序"多路归并，本质也是这个思路。

所以我一直觉得，LeetCode 21不值得只当一道简单题匆匆刷完。它值得你把迭代版、递归版、边界用例、易错点全部过一遍，因为这些知识在后面的归并类题目里全部用得上。

2. 核心理念三步走：哨兵节点、尾插法、谁小接谁

2.1 为什么没有哨兵节点，代码会丑一半

先看C语言链表的标准节点定义，这题和LeetCode 21的默认结构一致：

struct ListNode { int val; struct ListNode *next; };

我们的目标是把两个有序链表合并成一个。最朴素的想法：两个指针分别指向l1和l2，每次比较当前节点的val，把较小的那个"接"到结果链表末尾。

问题来了：结果链表的头指针指向哪里？一开始没有节点，是NULL。第一次接入节点时，头指针要从NULL变成某个l1或l2的节点；后续接入时，头指针又不能动，得靠一个tail指针去追末尾。这导致每次判断"这是不是第一个节点"，代码就成了这样：

struct ListNode* head = NULL; struct ListNode* tail = NULL; if (l1 == NULL) return l2; if (l2 == NULL) return l1; while (l1 && l2) { struct ListNode* cur; if (l1->val <= l2->val) { cur = l1; l1 = l1->next; } else { cur = l2; l2 = l2->next; } if (head == NULL) { head = cur; } else { tail->next = cur; } tail = cur; }

这代码能跑，但每轮循环都要判断一次head == NULL，不仅丑，还容易在后续修改时漏掉分支。解法就是哨兵节点。

struct ListNode dummy; dummy.next = NULL; struct ListNode* tail = &dummy;

dummy是一个真正存在于栈上的节点，它不存业务数据，只提供一个恒定的"伪头"。所有新节点都统一接到tail->next，最后返回dummy.next就是合并后的真实头节点。第一个节点和第五百个节点的处理逻辑完全一致，少掉一整类分支判断。

2.2 用尾插而不是头插的另一个理由：序的方向

有人可能问：能不能用头插法？每次把较小的节点插到结果链表头部，多省事。

省事是省事，但头插法天然构造的是逆序链表。你每次把当前最小值插到头部，完了得到的是从大到小的序列，最后还得反转一遍。反转链表也是 O(n) 的操作，白白多一轮遍历。而尾插法是顺着"每次拿到当前剩余节点中最小值"的顺序走的，正好落在升序上。推导一下就能明白：两个输入链表本身有序，当前l1->val和l2->val中较小的那个，一定是两个链表剩余所有节点中最小的，接在结果末尾不会破坏升序。这个不变量是尾插法正确性的根基。

2.3 用二级指针代替哨兵：另一种可行写法

哨兵节点不是唯一消除"首节点特殊处理"的方案。熟悉C语言的也可以用二级指针来维护tail，写法如下：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { struct ListNode* head = NULL; struct ListNode** tail = &head; while (l1 && l2) { if (l1->val <= l2->val) { *tail = l1; l1 = l1->next; } else { *tail = l2; l2 = l2->next; } tail = &((*tail)->next); } *tail = (l1 != NULL) ? l1 : l2; return head; }

这个写法其实很漂亮：tail指向"结果链表最后一个节点的 next 指针的地址"，通过二级指针修改它，等于一直在链尾追加。它避免了哨兵节点，也没有首节点特殊判断。缺点是对初学者不太友好——tail = &((*tail)->next)这句需要好好想两遍。面试时用哨兵节点最稳，可读性最强；用二级指针能显得你对指针理解更深。两种我都建议写一遍。

3. 迭代版全量代码与逐行拆解：指针的四次关键操作

3.1 完整可运行的C代码

把哨兵节点和尾插法组合起来，给出完整代码。这里我连测试辅助函数一起写出来，方便你在本地直接跑：

#include <stdio.h> #include <stdlib.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { struct ListNode dummy; dummy.next = NULL; struct ListNode* tail = &dummy; while (list1 != NULL && list2 != NULL) { if (list1->val <= list2->val) { tail->next = list1; list1 = list1->next; } else { tail->next = list2; list2 = list2->next; } tail = tail->next; } if (list1 != NULL) { tail->next = list1; } else { tail->next = list2; } return dummy.next; } struct ListNode* createNode(int val) { struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode)); node->val = val; node->next = NULL; return node; } struct ListNode* createList(int* arr, int n) { if (n == 0) return NULL; struct ListNode* head = createNode(arr[0]); struct ListNode* cur = head; for (int i = 1; i < n; i++) { cur->next = createNode(arr[i]); cur = cur->next; } return head; } void printList(struct ListNode* head) { while (head != NULL) { printf("%d -> ", head->val); head = head->next; } printf("NULL\n"); } int main() { int a[] = {1, 2, 4}; int b[] = {1, 3, 4}; struct ListNode* l1 = createList(a, 3); struct ListNode* l2 = createList(b, 3); struct ListNode* merged = mergeTwoLists(l1, l2); printList(merged); return 0; }

输出结果：1 -> 1 -> 2 -> 3 -> 4 -> 4 -> NULL。

3.2 循环体内四步的脑内模拟

很多人代码背得下来，但被问"循环里到底发生了什么"就卡壳。这里把每一步拆开：

1. 比较：list1->val <= list2->val，决定当前应该取谁；
2. 接线：tail->next = list1，把结果链表的尾巴接上当前更小的节点；
3. 前进源指针：list1 = list1->next，被取走的那个链表的指针向前移动；
4. 前进尾指针：tail = tail->next，让tail重新指向结果链表的最后一个节点。

第四步最容易漏。如果忘了tail = tail->next，下一轮循环会再次接到同一个位置，把已经接好的节点覆盖掉，最终结果变成只含有最后一个节点的断链链表。我用一个简单例子模拟前两次循环：

初始：list1 -> 1 -> 2 -> 4，list2 -> 1 -> 3 -> 4，dummy.next = NULL，tail = &dummy。

第一轮：1 <= 1成立，tail->next = list1，list1移动到2，tail移动到1节点。此时结果链是dummy -> 1，但注意这1来自list1，它的next还指向原来的2。

第二轮：list1现在是2，list2是1，因为2 <= 1不成立，所以取list2的1。tail->next = list2，这会把之前在1后面的链条重新接到list2的1，看起来像是把list1的1的next改成了list2的1。于是结果链是list1的1 -> list2的1 -> 3 -> 4。这就完成了"跨链表拼接"。

每一轮操作的本质，都是从某个原链表上摘下头节点，挂到结果链表的尾巴上。所以不需要malloc，也不需要单独释放，节点地址始终没变，变的是next的指向。

3.3 循环结束后的收尾为什么只有一句

循环结束的原因只有两种：list1空了，或者list2空了。因为两个输入链表都是有序的，剩余的那个链表整体上依然有序，且它剩余所有节点的值都不小于结果链表末尾节点的值——这是上一节说的不变量保证的。所以不需要再逐个比较，直接把剩余链表整段挂上去：

if (list1 != NULL) { tail->next = list1; } else { tail->next = list2; }

更简洁的写法是：

tail->next = (list1 != NULL) ? list1 : list2;

这段代码还有一个隐藏作用：处理了list1和list2其中一个为空的情况。假设list1一开始就是NULL，循环一次都不进，tail->next直接指向list2，返回dummy.next就是list2，完全符合题意。

3.4 复杂度与正确性简单论证

时间上，每轮循环消耗一个节点，两个链表合计m + n个节点，所以是 O(m+n)。空间上，除了dummy这个栈上的哨兵和几个指针，没有额外分配，所以是 O(1)。

正确性可以通过不变量证明：每次循环结束后，tail指向的节点都是"当前已处理的所有节点中最后一个"，且结果链表从dummy.next到tail一直是升序的。循环结束时，把剩余的整段有序链表接上去，升序性质保持。这个过程和数学归纳法是一回事，面试时能说清楚这个不变量，比背代码强得多。

4. 换用递归视角：把"两个链表头取最小"当整体

4.1 递归式子怎么归纳出来

递归解法的核心可以写成一句话：

merge(l1, l2) = 较小的头节点 + merge(较小头节点的下一个节点, 另一个链表的头节点)

举例：l1 = 1->2->4，l2 = 1->3->4。较小的头节点是l1的1，那merge的结果就是1 + merge(2->4, 1->3->4)。后面这一步又是一个相同的合并问题，只是问题规模缩小了一个节点。

这个归纳非常干净。每次调用只解决"当前两个头节点谁最小"这一个问题，剩下的交给递归。

4.2 终止条件为什么是两个空判断

递归必须回答"什么时候不再递归"。对这道题，最简单的情形就是某个链表为空：

• 如果l1 == NULL，合并结果直接就是l2，因为l2已经有序且所有节点都大于等于之前接好的节点；
• 如果l2 == NULL，同理返回l1。

两个都为空也覆盖在l1 == NULL这个分支里，返回NULL。最坏情况下递归深度是m+n，比如两个链表交叉取值时，每个节点都要多一层调用。

4.3 用1->2->4和1->3->4推演调用过程

完整递归代码如下：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) { if (l1 == NULL) return l2; if (l2 == NULL) return l1; if (l1->val <= l2->val) { l1->next = mergeTwoLists(l1->next, l2); return l1; } else { l2->next = mergeTwoLists(l1, l2->next); return l2; } }

我用前面那个例子推演一遍。设A1 = 1->2->4，B1 = 1->3->4。

第一次调用：A1.val (1) <= B1.val (1)成立，于是要计算merge(A1.next, B1)，即merge(2->4, 1->3->4)，等这个结果返回后接到A1.next上。

第二次调用：2 <= 1不成立，走else，调用merge(2->4, 3->4)，返回值接到B1.next上。

第三次调用：2 <= 3成立，调用merge(4, 3->4)，返回值接到A2.next（A2是值为2的节点）。

第四次调用：4 <= 3不成立，调用merge(4, 4)，返回值接到B3.next（B3是值为3的节点）。

第五次调用：4 <= 4成立，调用merge(NULL, 4)，此时l1 == NULL，返回l2。

然后逐层往上返回，最终形成的链表就是1 -> 1 -> 2 -> 3 -> 4 -> 4。

注意这里有个关键点：递归返回时通过l1->next = ...把子问题的结果挂在后面，每次返回的节点正好是当前两个头节点中较小的那个。整个调用过程没有创建任何新节点，和迭代版一样是原地修改。

4.4 递归的栈代价与生产环境的选择

递归版代码非常短，理解起来也很"数学"，但代价是空间。每次递归调用都要在调用栈上压一帧，深度最大可达m+n。如果两个链表各有10000个节点且值交错分布，递归深度会接近20000层，C语言默认栈空间下非常容易栈溢出。LeetCode的测试数据一般不会这么极限，所以递归版能通过，但面试官如果追问"生产环境你选哪个"，答案应该是迭代版。

我个人更喜欢这样向候选人解释：递归版是"从结果倒着想"，迭代版是"从过程正着做"。两者时间复杂度一样，迭代版空间更优，递归版代码更短。面试回答时可以先给递归版展示思路，再主动补一句"如果数据规模大我更倾向迭代版，因为栈深度可控"，这个加分点比多背一个解法更实在。

5. 最容易翻车的四个C语言细节：野指针、断链、死循环、泄漏

5.1 死循环的元凶：tail没动

最常见的错误版本长这样：

while (l1 && l2) { if (l1->val <= l2->val) { tail->next = l1; l1 = l1->next; } else { tail->next = l2; l2 = l2->next; } // 漏了 tail = tail->next; }

tail->next每轮都被重新赋值，覆盖掉上一轮接好的节点，但tail自己始终指向哨兵。从外面看，结果链表永远只有一个节点；更麻烦的是，由于tail->next一直指向某个旧节点，链路并没有真的断开，某些编译器下可能表现为死循环或输出异常。排查方法很简单：在循环末尾打一行printf("tail now: %p, val: %d\n", (void*)tail, tail->val);，如果每次打印的地址都一样，就可以确认tail没动。

5.2 断链的顺序：先接后走，顺序不能反

循环体内还有一个容易被忽略的顺序问题：如果先把tail->next = list1，再执行list1 = list1->next，这没问题，因为list1->next在赋值前后没有变化。但如果你习惯先写list1 = list1->next，再写tail->next = list1，那效果就变成"把 list1 的下一个节点接到了结果链表上"，而不是当前节点。这个 bug 非常隐蔽，因为代码看起来语法完全正确，结果却会跳过一个节点。

正确的心理模型是：先确定要接谁，接上去，然后再让源指针往前走。三步之间是严格顺序关系。

5.3 返回错东西：dummy.next vs dummy

用哨兵节点时，有人最后写return dummy;。这里dummy是一个结构体，不是指针，编译就会报类型错误。也有人写return &dummy;，这在 LeetCode 的判题环境里基本等于返回了一个指向栈上的悬垂指针，行为未定义。正确写法一定是return dummy.next;。

要理解为什么不能返回&dummy：dummy定义在mergeTwoLists函数的栈帧上，函数返回后这块内存就无效了。这也是为什么有人习惯把哨兵节点malloc出来——但那样你就必须记得free(dummy.next)？不对，free哨兵和释放链表是两回事，很容易搞出双重释放。所以我的建议是：栈上定义哨兵，不需要释放，最后返回dummy.next完事。

5.4 堆上的哨兵节点泄漏

如果用了下面这种写法：

struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode)); dummy->next = NULL; struct ListNode* tail = dummy; ... return dummy->next;

注意：dummy本身从堆上分配，但返回的链表中并不包含它。调用者拿到合并后的链表，却没有任何指针指向dummy，这块内存就泄漏了。功能上 LeetCode 不会查泄漏，但本地长期跑或者代码评审时一定会被提出来。解决办法就是把dummy放到栈上，或者在使用完哨兵后free(dummy)，但后者容易把真正的链表头也释放掉，我建议就别用malloc做哨兵。

5.5 调试锦囊：gdb里怎么看链表

本地调这个题，最省事的调试方式是用 gdb 配合一个短测试程序。在mergeTwoLists的while循环里打断点，然后：

• p list1->valp list2->val看当前比较值；
• p tail->next看尾指针指向谁；
• p *list1查看整个节点结构体；
• set print pretty on之后，p *list1会结构化显示val和next。

想快速确认链表形态，也可以在每次接线后打一行：

printf("l1=%p(%d) l2=%p(%d) tail=%p\n", (void*)l1, l1 ? l1->val : -1, (void*)l2, l2 ? l2->val : -1, (void*)tail);

指针地址配合值，能立刻看出是谁没动、谁跑了、谁被重复接上了。这类链表的指针 bug，肉眼检查不如打印一行地址来得快。

6. 提交之前跑完这些边界用例：一份可复现的自测清单

6.1 等价类测试表

LeetCode 不会告诉你它有哪些隐藏用例，但你自己可以先列一份等价类表。边界用例的意义是强迫自己确认代码对每一类分支都正确：

其中"一个链表完全大于另一个"这个用例很值得跑。假设list1 = [1,2]，list2 = [5,6]，循环里把1、2都取走，list1变空，这时tail->next = list2，直接把5->6整段挂上。如果收尾代码写的是tail->next = list1而不是list2，输出就会变成[1,2]，少了一整段。

6.2 自测main函数的组织方式

自己刷题不要只在 LeetCode 网页里点运行，建议本地建一个test.c，把上一章的完整代码放进去，再补一个最简断言。C语言没有内置测试框架，可以自己写一个简单的check函数：

int getLength(struct ListNode* head) { int len = 0; while (head) { len++; head = head->next; } return len; } int checkMerged(struct ListNode* head) { if (head == NULL) return 1; while (head->next) { if (head->val > head->next->val) return 0; head = head->next; } return 1; }

在 main 里跑完所有用例后调用checkMerged，再配合getLength验证节点总数等于两个输入链表长度之和。这一步能抓住 "节点少一个" 这类问题——它们是断链和跳节点的典型症状。

6.3 提交前自查清单

我每次提交链表题之前都会在心里过一遍这张清单，你可以直接抄走：

1. 两个入参里有没有NULL？代码第一行就处理了吗？
2. 循环条件写的是while (l1 && l2)还是while (l1 || l2)？后者会让循环体内出现空指针访问。
3. tail = tail->next;是否存在？位置在循环体最后吗？
4. 最后返回的是dummy.next还是dummy？
5. 收尾时接的是"非空的那条链表"吗？有没有写反？
6. 如果要求不修改原链表，这份代码是否违反了约定？
7. 有没有malloc却没free的节点？

这些点每一条都是真实提交里高频出现的编译错误或运行错误来源。

7. 面试追问的四种变形：从这道题延伸到更广的归并体系

7.1 变形一：K个有序链表合并

面试官把两个链表变成K个，最常用的解法是分治：先把K个链表两两合并，再把结果两两合并，重复直到只剩一个。单次mergeTwoLists是 O(m+n)，分治的总复杂度是 O(N log K)，其中 N 是所有节点的总数。这道题代码可以直接复用。另一种思路是维护一个小顶堆，每次从K个头里取最小，适合节点特别多的情况。K个链表合并本质上是"多路归并"，也是外部排序的核心概念，能主动提出来会很加分。

7.2 变形二：值相等时的取舍与稳定性

我的代码里比较用的是<=，这意味着l1和l2值相等时优先取l1。LeetCode 的判断只关心最终链表有序，不关心稳定性和来源，所以用<和<=都能通过。但如果面试官追加一句"如果要求相同值的节点保持原相对顺序，你的代码还成立吗"，你要能回答：<=保持了l1的相对顺序，l2中与l1等值的节点会被放到后面，只要两个原链表内部有序，合并结果依然稳定。面试中讨论到这个层面，说明你真的理解代码而不只是背答案。

7.3 变形三：要求深拷贝不修改原链表

有些题目或面试变体不允许改动传入的链表，这时候你必须在合并时malloc新节点，逐个复制val。思路一样，差异在于每次取节点时不是直接tail->next = l1，而是：

tail->next = (struct ListNode*)malloc(sizeof(struct ListNode)); tail->next->val = l1->val; tail->next->next = NULL;

别忘了最后遍历释放旧链表，并注意malloc的失败检查。

7.4 变形四：链表里有环怎么办

面试官有时会故意把话题引向"如果链表中有环，你的代码会怎样"。答案是：会死循环，因为tail->next永远会在环里打转。处理思路是先用快慢指针检测环，或者约束只能走m+n步。LeetCode 21 的原始输入约定无环，但它背后的思考是在提醒你：任何依赖"链表有尾"的归并算法，前提都是无环。

7.5 变形五：这道题在归并排序与外部排序里的影子

归并排序的merge步骤是它的数组版本。链表版本的经典题 LeetCode 148 排序链表，要求对链表做 O(n log n) 排序，实现里就是"链表找中点 + 递归两半 + mergeTwoLists"。外部排序的大致思路则是：内存放不下全部数据，把大文件切成多个有序块，每块被读入内存后，用多路归并合并成最终有序文件。它的很多实现细节和"两个有序链表合并"是一个思想体系。

所以这道简单题真不是刷完就完事的点。它处在链表、排序、归并三条知识线的交汇处，值得你反复写、反复讲。

我在刷题阶段把这道题写了不下十遍，迭代版、递归版、二级指针版各练过。真正常用的还是哨兵节点加尾插的迭代版——它逻辑直观，不容易写错，空间最优，面试时也最容易向考官解释。如果你正卡在链表题上，别急，先把这道题的指针移动节奏练成肌肉记忆，后面的链表题会顺畅很多。再分享一个小技巧：刷链表题尽量别用 IDE 自动补全，手写完整结构体和指针操作，你的印象会深得多，面试时也不会因为换了环境而手生。