说实话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 nodestruct ListNode dummy; dummy.next NULL; struct ListNode* tail dummy;哑节点本身不存储有效数据它的唯一作用是提供一个“虚拟头”让第一个真实节点也能通过tail-next ...的方式接入代码里就不需要单独处理“当前链表是否为空”的分支了。最后返回dummy.next这才是真实链表的头节点。迭代法的时间复杂度是 O(mn)因为两个链表每个节点都会被遍历一次额外空间复杂度是 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(mn)空间复杂度则是 O(mn)因为递归栈的深度取决于节点总数。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 新手最容易犯的五个错误我在带人和面试过程中反复见过下面几种错误列成一张表方便你自查。典型错误错误原因正确做法返回tail或dummy本身没搞清楚谁才是合并后的头节点返回dummy.nextwhile 条件写成l1 ! NULL || l2 ! NULL想在循环里同时处理两个链表用循环结束后再接剩余部分比较后忘记移动l1或l2指针认为自己已经接到新链表里了每次接入后对应链表游标必须后移递归出口只写了一个if (l1 NULL) return l2;但漏了l2 NULL边界意识不够两个空指针出口都写上修改了节点的next导致丢链接线顺序有误先保存下一个节点再改指针这道题里只需先移动游标即可还有个比较隐蔽的坑本地测试时如果链表是手动malloc创建的测完不freeLeetCode 不管但你在本地跑内存检测工具时会看到泄漏。链表题虽然不要求释放作为 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) 空间意味着什么。从那以后凡是写链表合并我基本默认迭代法递归只用来解释思路。这个选择标准我现在也推荐给你平时练习两种都写但上了考场或者写工程代码先想想调用栈会不会成为你的短板。