说实话，LeetCode 21 的合并两个有序链表，是我面试别人时几乎每次都会拿出来的一道题。它代码量不大，理论上十分钟内写完，可它能把一个人对链表遍历、指针修改、边界处理和递归思维的真实水平看得明明白白。这篇文章我就用 C 语言把这个经典链表题彻底拆开，从题目本身的隐含条件，到迭代、递归两种解法，再到实际操作里最常见的错法和排查方式，全部过一遍。无论你刚开始学链表、正在准备数据结构期末考试，还是马上要面技术岗，都值得花点时间把这篇读完，因为这些坑都是真实存在的。

1. 读懂题目：合并两个有序链表到底在考什么

1.1 题面拆解：输入、输出与默认条件

LeetCode 21 的题面很短：给定两个升序链表l1和l2，把两个链表合并成一个新的升序链表，并返回新链表的头节点。

需要注意几个隐含条件。第一个是“升序”，而且是非递减序，也就是说链表里允许出现相等的值，比如[1, 2, 4]和[1, 3, 4]合并结果是[1, 1, 2, 3, 4, 4]，两个 1 都要保留，两个 4 也都要保留。第二个关键点是合并后的链表必须由原节点拼接而成，不能去malloc一堆新节点然后复制 val。这一点题目里没有明说，但所有主流题解和面试官默认要求都是这样：你要做的是重新组织节点之间的next指针，而不是复制数据。因为一旦允许复制，这道题就退化成了“把两个数组排序”的问题，完全失去了链表操作的考察价值。

在 C 语言里，LeetCode 已经帮你定义好了节点结构体：

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */

也就是说你要实现的函数签名是：

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2);

输入有可能为空链表，一个节点都没有；也有可能一个链表已经空了，另一个链表还有一长串。这些边界情况不是题目附加的刁难，而是链表问题里真正会决定代码对错的地方。

1.2 为什么这道题能成为链表界的“必考题”

被选为经典题不是没有原因的。合并两个有序链表几乎覆盖了链表操作所有的基本功：遍历链表的基本功、修改next指针的基本功、处理“头节点不确定”的基本功，还有递归思想的基本功。一道题同时考这几样，而且每一样都是后续复杂链表题的地基。

我面过不少候选人，很多人二叉树的遍历背得很熟，但一写这道题就卡住，卡住的位置往往不是算法思路，而是“第一个节点怎么接”和“一个链表走完了怎么办”。这说明他对链表底层结构没有形成直觉，只是在背模板。另外，这道题也是很多复杂题目的构成零件，比如 LeetCode 23 合并 K 个有序链表，本质上就是反复调用这道题的合并逻辑；LeetCode 148 链表排序，也会用到两个有序链表的合并。把这一道题吃透，后面再刷链表题目会顺很多。

2. 链表基础与 C 语言解法选型

2.1 单链表的结构定义：节点只是“数据 + 指针”

链表在 C 语言里就是一组动态分配的节点，每个节点通过指针串联起来。你可以把节点想象成火车车厢：每节车厢里装着货物（val），车厢后面有一个挂钩（next）连着下一节车厢。找到火车头，就能沿着一节一节车厢走下去。

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

这里val是当前节点存的值，next是指向下一个节点的指针。最后一个节点的next必须是NULL，这是链表遍历的终止标志。

理解了这一点，你再看“合并两个有序链表”，本质上就是手里有两列已经排好序的火车，现在要重新挂钩，把它们拼成一列依然有序的火车。每节车厢的货物不能换，能动的只有挂钩指向谁。

2.2 为什么要用 C 语言写链表题

有人问，用 Java、Python 写链表不更简单吗？确实，Java 有ListNode类，Python 有对象引用，写起来更省心。可 C 语言把所有细节都暴露在明面上，你被迫去面对指针本身：谁指向谁、什么时候该移动指针、空指针能不能解引用。这种被迫的“痛感”恰恰是建立底层直觉最快的路径。

C 语言写链表还有一个特点：内存管理全在自己手里。合并链表时如果只用原节点，就基本不涉及malloc和free的配对问题；但如果某些题解里用malloc创建哑节点，你就需要考虑它要不要释放。这些细节在其他语言里都被垃圾回收器藏起来了，只有在 C 里你才会真正意识到：一个节点到底活在栈上还是堆上，生命周期归谁管。

从实际面试角度看，C 语言写链表也是很多国内技术岗的默认要求。因为面试官想确认你不是只会在 LeetCode 编辑器里写代码，而是真的能在裸环境下把指针操作写对。如果这一题你能用 C 写利索，面试官对你的 C 功底信任度会提升一大截。

2.3 边界条件才是链表题的隐藏考点

链表题有个特点：主流程逻辑通常不难，难的是边界。对于合并两个有序链表，边界大概有三类。

第一类是空链表：l1或l2本身就是NULL，这时候不需要任何比较，直接返回另一个链表即可。第二类是合并过程中某一个链表先走到头：比如l1所有节点都比l2小，遍历完l1后l2还剩一批节点，这时候要把剩余部分整体接上去，而不是继续一个个比较，因为剩下的节点本来就是有序的。第三类是头节点：合并后的链表头到底是谁，是l1的头还是l2的头？如果不做处理，每次接入节点时都要单独判断head是否为 NULL，代码会很啰嗦。

这第三类边界就是后面要讲的“哑节点”技巧要解决的问题。

3. 两种核心解法：迭代法和递归法

3.1 迭代法：双指针加哑节点，思路最直观

迭代法的核心思想是维护两个“游标指针”，分别指向两个链表当前待比较的节点，再维护一个tail指针，指向已合并链表的最后一个节点。每一轮比较l1->val和l2->val，把值更小的节点接到tail->next上，然后让对应链表的游标前进一步，同时tail也要前进一步。

这个过程很像两个有序队列的出队：谁的值小，谁就“出队”进入新链表。直到某一个链表为空，剩下那个链表整条接上来就行。

那头节点的问题怎么解决？最优雅的方式是设置一个哑节点（dummy node）：

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

哑节点本身不存储有效数据，它的唯一作用是提供一个“虚拟头”，让第一个真实节点也能通过tail->next = ...的方式接入，代码里就不需要单独处理“当前链表是否为空”的分支了。最后返回dummy.next，这才是真实链表的头节点。

迭代法的时间复杂度是 O(m+n)，因为两个链表每个节点都会被遍历一次；额外空间复杂度是 O(1)，只用了几个指针变量，非常干净。

3.2 递归法：每层只解决一个节点的问题

递归法换了一种看待问题的角度。你不需要一层层循环，而是相信这样一个定义：合并l1和l2，就是看当前l1和l2谁的头更小，较小的那个节点指向“合并剩下部分”的结果。

用公式表达就是：

merge(l1, l2) = if l1 == NULL: return l2 if l2 == NULL: return l1 if l1->val <= l2->val: l1->next = merge(l1->next, l2) return l1 else: l2->next = merge(l1, l2->next) return l2

这个过程很像接力赛：第一个人只负责把自己这一段跑好，跑完把接力棒交给下一个递归调用，由下一层继续处理剩下的节点。

递归法的代码非常短，可读性也好，但有一个代价：每层递归都会占用函数调用栈空间。极端情况下，如果两个链表都特别长，递归深度等于两个链表的总节点数，有栈溢出的风险。LeetCode 原题节点数不超过 50，所以递归没问题；但如果放到生产环境或者扩展题里，就必须警惕这个问题。递归版本的时间复杂度同样是 O(m+n)，空间复杂度则是 O(m+n)，因为递归栈的深度取决于节点总数。

3.3 实际题解中应该选哪种写法

如果这是我面试现场写，我会毫不犹豫选迭代法。原因很简单：空间 O(1)，逻辑也不复杂，不容易被追问“你递归栈会不会爆”。而递归法更适合用来跟面试官展示你对问题的分解能力，或者作为写完迭代法之后的“加分项”补充说明一下。

我在实际教学里看到的现象是：新手用递归法写这道题，经常在递归出口上栽跟头。很多人会把return l1和return l2写反，或者在比较大小之后忘了更新next指向。相比之下，迭代法的 while 循环结构更贴近人类的顺序思维，出错的概率小一些。所以我建议学这道题时，先把迭代法练到闭着眼能写，再琢磨递归法。两个都会了，这道题才算真正掌握。

4. 完整 C 语言代码与逐行详解

4.1 迭代版本完整代码

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

这段代码很短，但每一行都有讲究。dummy定义在栈上，不需要malloc，也就少了一次内存管理负担。tail指向dummy，初始状态下 dummy 是合并后链表的哨兵节点。循环条件用的是l1 != NULL && l2 != NULL，也就是说只要有一个链表遍历完了，循环立即结束。接尾时判断哪个链表还有剩余，直接整段接上。

最后返回dummy.next，这才是合并后的真实头节点。你如果返回tail或者&dummy，那都是错的——tail指在最后一个节点，不是头；&dummy指向栈上的哨兵，不是链表的实际内容。

4.2 递归版本完整代码

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; } }

递归版本的核心是：每次比较后，把较小节点的next指向“合并剩下节点”的结果，然后返回较小节点本身。这里要注意，l1->next = mergeTwoLists(l1->next, l2)这行代码不是简简单单的赋值，它会在返回时层层把指针关系补全。你可以用一个小例子手动走一遍，比如l1 = [1, 2]、l2 = [3, 4]，先在纸上写出每次递归调用的参数，再逆向看返回值，很快就能理解递归的“回溯”过程。

4.3 代码里容易被追问的细节

面试官最喜欢追问几个点，这里提前讲清楚。

第一个是：为什么dummy用栈上变量而不是malloc？因为dummy.next最后被赋值为真实链表的头节点，返回这个指针完全合法；而dummy本身出了函数就失效了，我们也不需要它继续存在。如果写成struct ListNode* dummy = malloc(...)，用完后还得记得free(dummy)，多一步操作，容易泄漏。栈上哑节点是更干净的写法。但要记住，绝不能返回&dummy或dummy.next之外的、指向 dummy 内部的指针，否则就是经典的使用栈地址错误。

第二个问题是：接尾时为什么可以直接tail->next = l1或者tail->next = l2？因为l1、l2指向的剩余部分本身就是有序的，它们内部的连接关系没有被打乱。你只需要把已合并链表的尾部接上这个剩余子链表的头部，整个链表就仍然是升序的。

第三个问题是：如果两个值相等，取哪个？我的代码里用的是<=，所以相等时取l1。换成<也可以，不会影响最终链表的有序性。这只是约定，不是坑，但如果你在写的时候犹豫，说明你对比较逻辑还不够熟。

5. 常见错误、边界测试与本地调试

5.1 新手最容易犯的五个错误

我在带人和面试过程中，反复见过下面几种错误，列成一张表方便你自查。

还有个比较隐蔽的坑：本地测试时如果链表是手动malloc创建的，测完不free，LeetCode 不管，但你在本地跑内存检测工具时会看到泄漏。链表题虽然不要求释放，作为 C 语言程序员还是应该养成随手释放的习惯。

5.2 边界条件的测试用例怎么准备

我自己在验证这类链表题时，会准备一组覆盖各种情况的用例，最少包括下面这些：

• 空链表 + 空链表：应该返回NULL
• 空链表 + 非空链表：应该返回非空链表本身
• 单节点 + 单节点：比如[1]+[2]和[2]+[1]
• 全相等：比如[1, 1]+[1, 1, 1]
• 一个链表全是小值：比如[1, 2, 3]+[4, 5, 6]
• 一个链表全是大值：比如[4, 5, 6]+[1, 2, 3]
• 包含负数：比如[-3, 0]+[-5, 1]
• 长链表：长度 50 左右，验证有没有写出 O(n²) 的解法

这些用例不需要全写进代码里，只需要你在脑子里过一遍，或者在本地快速构造验证即可。我见过有人一上来就测很长的随机数据，结果错了还不好定位，其实小用例更容易暴露逻辑错误。

5.3 本地环境自测链表的完整套路

LeetCode 只测试函数，但本地调试链表题需要你自己搭建一个最小可运行环境。我常用的套路是写三个辅助函数：createNode、appendNode、printList。

#include <stdio.h> #include <stdlib.h> struct ListNode { int val; struct ListNode *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) { struct ListNode dummy; dummy.next = NULL; struct ListNode* tail = &dummy; for (int i = 0; i < n; i++) { tail->next = createNode(arr[i]); tail = tail->next; } return dummy.next; } void printList(struct ListNode* head) { while (head != NULL) { printf("%d -> ", head->val); head = head->next; } printf("NULL\n"); } void freeList(struct ListNode* head) { struct ListNode* tmp; while (head != NULL) { tmp = head; head = head->next; free(tmp); } }

然后 main 函数里构造两个数组，分别转成链表，调用mergeTwoLists，打印结果。如果输出不对，可以再打印每一轮循环中l1->val、l2->val、tail->val的中间状态，定位到底是哪一步接错了。用 gdb 单步跟踪也可以，但笔记本手写辅助函数的方式更快，而且能顺便检验你对链表创建和遍历的熟练度。

这里我提一句：很多人本地跑得好好的，一提交就报错，多半是因为只测了一两个正常用例，边界完全没覆盖。把这个自测套路固定下来，刷链表题会省很多时间。

6. 这道题之外的链表解题套路

6.1 哑节点套路：一条通用主线

如果你仔细回味迭代法里的dummy，会发现这个技巧适用范围远不止这一道题。凡是要“新建一个链表”或者“从头开始拼接结果”的题目，都可以先建一个哑节点，然后不断tail->next = 新节点，最后返回dummy.next。这样做的好处是：头节点永远不用单独判断。

典型的应用是 LeetCode 86 分隔链表、LeetCode 2 两数相加，以及很多需要拆链再重组的题。我练题的时候，只要看到“结果是一条新的链表”，第一反应就是先放一个哑节点。这个习惯帮我省下了大量 if 分支。

6.2 从 21 走向 23、148：进阶题目链路

这道题的最直接进阶路线有两条。一条是 LeetCode 23 合并 K 个有序链表：你可以把 K 个链表两两合并，也可以每次合并一个进最终链表，还可以用优先队列优化；无论哪种方案，内部的合并逻辑都还是 LeetCode 21。另一条是 LeetCode 148 排序链表：要求 O(n log n) 时间、O(1) 空间，标准做法是链表归并排序，先找中点拆成两半，递归排序，最后就是合并两个有序链表。也就是说，LeetCode 21 是这两个高级题的核心零件。

我建议的刷题顺序是：先把这个题做透，再用它当模板做 86、2，最后挑战 23 和 148。不要一上来就啃难题目，那只会让你觉得链表很难。

6.3 刷链表题时的几个长期习惯

最后分享几个我自己长期积累的习惯。一是在动手写代码前，先在纸上画出两个链表和几个关键指针的位置，标好每一步要怎么变。画图十分钟，写代码五分钟，远比你盯着屏幕空想要快。二是每写完一段指针操作，立刻反问自己“这个指针现在指向哪里？它的 next 原本是谁？被我改掉之后会不会丢链？”三是尽量保持代码风格稳定，比如统一用NULL而不是0，统一用l1 != NULL而不是l1，减少低级失误。

链表这个主题，说难不难，说简单也不简单，本质上就是“指针指向谁”的问题。合并两个有序链表作为这个领域最基础的题目，值得你多写几遍，写到不假思索为止。

最后说一点我个人的体会。我最早刷这道题的时候，也用递归法，觉得代码短很优雅。后来有一次在本地生成了一条十万个节点的链表，递归版直接栈溢出，我才真正意识到 O(1) 空间意味着什么。从那以后，凡是写链表合并，我基本默认迭代法，递归只用来解释思路。这个选择标准，我现在也推荐给你：平时练习两种都写，但上了考场或者写工程代码，先想想调用栈会不会成为你的短板。