我拿这道题去面过不少应届生也看大家刷题打卡提到过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(mn)完全违背了题目考察的本意。在LeetCode上这题默认允许复用原有节点面试时也默认可以原地修改输入链表。搞清楚这个前提思路就顺了。1.2 三个最容易暴露功底的方向以我旁观面试和刷题群反馈的经验这题真正筛选人的点有三个头节点会不会处理。两个链表的头节点不一定是最终结果的头因为较小的那个才应该排在前面。很多人写循环时先判断head NULL再单独处理第一个节点代码瞬间长出三条分支。指针移动的节奏。接一个节点、往前走一步这个一步写到哪个位置很讲究。写错位置要么死循环要么反复接同一个节点。空指针判断的顺序。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 循环体内四步的脑内模拟很多人代码背得下来但被问循环里到底发生了什么就卡壳。这里把每一步拆开比较list1-val list2-val决定当前应该取谁接线tail-next list1把结果链表的尾巴接上当前更小的节点前进源指针list1 list1-next被取走的那个链表的指针向前移动前进尾指针tail tail-next让tail重新指向结果链表的最后一个节点。第四步最容易漏。如果忘了tail tail-next下一轮循环会再次接到同一个位置把已经接好的节点覆盖掉最终结果变成只含有最后一个节点的断链链表。我用一个简单例子模拟前两次循环初始list1 - 1 - 2 - 4list2 - 1 - 3 - 4dummy.next NULLtail dummy。第一轮1 1成立tail-next list1list1移动到2tail移动到1节点。此时结果链是dummy - 1但注意这1来自list1它的next还指向原来的2。第二轮list1现在是2list2是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(mn)。空间上除了dummy这个栈上的哨兵和几个指针没有额外分配所以是 O(1)。正确性可以通过不变量证明每次循环结束后tail指向的节点都是当前已处理的所有节点中最后一个且结果链表从dummy.next到tail一直是升序的。循环结束时把剩余的整段有序链表接上去升序性质保持。这个过程和数学归纳法是一回事面试时能说清楚这个不变量比背代码强得多。4. 换用递归视角把两个链表头取最小当整体4.1 递归式子怎么归纳出来递归解法的核心可以写成一句话merge(l1, l2) 较小的头节点 merge(较小头节点的下一个节点, 另一个链表的头节点)举例l1 1-2-4l2 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。最坏情况下递归深度是mn比如两个链表交叉取值时每个节点都要多一层调用。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-4B1 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.nextA2是值为2的节点。第四次调用4 3不成立调用merge(4, 4)返回值接到B3.nextB3是值为3的节点。第五次调用4 4成立调用merge(NULL, 4)此时l1 NULL返回l2。然后逐层往上返回最终形成的链表就是1 - 1 - 2 - 3 - 4 - 4。注意这里有个关键点递归返回时通过l1-next ...把子问题的结果挂在后面每次返回的节点正好是当前两个头节点中较小的那个。整个调用过程没有创建任何新节点和迭代版一样是原地修改。4.4 递归的栈代价与生产环境的选择递归版代码非常短理解起来也很数学但代价是空间。每次递归调用都要在调用栈上压一帧深度最大可达mn。如果两个链表各有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;。要理解为什么不能返回dummydummy定义在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 不会告诉你它有哪些隐藏用例但你自己可以先列一份等价类表。边界用例的意义是强迫自己确认代码对每一类分支都正确场景输入期望输出主要验证点两个空链表[][][]循环不进tail-next被赋NULL一个空链表[][1,2][1,2]直接返回非空链表单节点互比[1][2][1,2]基本接线等值节点交错[1,1,1][1,1,1][1,1,1,1,1,1]等值分支的稳定性一个链表完全大于另一个[1,2][5,6][1,2,5,6]循环后整段拼接负数和零[-5,0][-1,2][-5,-1,0,2]值比较与负数排序极端值[-100][100][-100,100]min/max 边界其中一个链表完全大于另一个这个用例很值得跑。假设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 提交前自查清单我每次提交链表题之前都会在心里过一遍这张清单你可以直接抄走两个入参里有没有NULL代码第一行就处理了吗循环条件写的是while (l1 l2)还是while (l1 || l2)后者会让循环体内出现空指针访问。tail tail-next;是否存在位置在循环体最后吗最后返回的是dummy.next还是dummy收尾时接的是非空的那条链表吗有没有写反如果要求不修改原链表这份代码是否违反了约定有没有malloc却没free的节点这些点每一条都是真实提交里高频出现的编译错误或运行错误来源。7. 面试追问的四种变形从这道题延伸到更广的归并体系7.1 变形一K个有序链表合并面试官把两个链表变成K个最常用的解法是分治先把K个链表两两合并再把结果两两合并重复直到只剩一个。单次mergeTwoLists是 O(mn)分治的总复杂度是 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永远会在环里打转。处理思路是先用快慢指针检测环或者约束只能走mn步。LeetCode 21 的原始输入约定无环但它背后的思考是在提醒你任何依赖链表有尾的归并算法前提都是无环。7.5 变形五这道题在归并排序与外部排序里的影子归并排序的merge步骤是它的数组版本。链表版本的经典题 LeetCode 148 排序链表要求对链表做 O(n log n) 排序实现里就是链表找中点 递归两半 mergeTwoLists。外部排序的大致思路则是内存放不下全部数据把大文件切成多个有序块每块被读入内存后用多路归并合并成最终有序文件。它的很多实现细节和两个有序链表合并是一个思想体系。所以这道简单题真不是刷完就完事的点。它处在链表、排序、归并三条知识线的交汇处值得你反复写、反复讲。我在刷题阶段把这道题写了不下十遍迭代版、递归版、二级指针版各练过。真正常用的还是哨兵节点加尾插的迭代版——它逻辑直观不容易写错空间最优面试时也最容易向考官解释。如果你正卡在链表题上别急先把这道题的指针移动节奏练成肌肉记忆后面的链表题会顺畅很多。再分享一个小技巧刷链表题尽量别用 IDE 自动补全手写完整结构体和指针操作你的印象会深得多面试时也不会因为换了环境而手生。