链表题里“合并两个有序链表”属于那种第一眼看过去毫无门槛、真动手写又总有地方要返工的题。我从最早用 C 语言啃数据结构课本到后来在工程里写归并排序、写多路有序日志的合并这道题前前后后写过不下几十遍每次重写都能发现自己上一次留下的毛病有时候是忘了把剩下那半条链挂上去有时候是返回了一个指向栈上哑结点的指针。这篇文章把我用 C 实现合并两个有序链表的三种思路完整摊开——递归、迭代加哑结点、新建结点拷贝逐行讲清楚指针是怎么流动的也把上机时最容易踩的几个坑一次说透。正在啃 C 语言链表基础操作、准备面试、或者需要在项目里写归并逻辑的人可以直接照着改。1. 先把“有序链表合并”还原成真实场景很多人刷到第 21 题的第一反应是“这也能单独成题”因为逻辑看起来就是两个指针比大小、谁小拿谁。但它在工程里出现得远比想象中频繁而且每次出现时的约束条件都不一样这才是值得认真过一遍的原因。1.1 它本质上是归并排序的那一步归并排序的核心动作就是把两个已经有序的序列合并成一个有序序列。数组版本你需要开一块和原数组等大的临时空间然后把元素一个个搬过去链表版本的优势在于你只需要改指针不需要搬任何数据。同样是合并 n 个元素数组是 O(n) 的额外空间链表原地串接就是 O(1) 的额外空间。这个差别在做外部排序、做大规模日志按时间戳合并的时候非常值钱。比如你有两个日志文件各自按时间戳递增写好了现在要合成一条时间线输出如果日志条目以链表形式常驻内存那你只要重排指针不需要为整个结果再申请一遍内存。1.2 结点的结构定义本文所有代码都基于这个最朴素的定义和教科书、面试题里的一致typedef struct ListNode { int val; struct ListNode *next; } ListNode;这里有两个细节值得提前说清楚。第一next的类型是struct ListNode *而不是ListNode *因为typedef的作用域要等整个声明结束才生效在结构体内部还不能用别名引用自己。这个坑在 C 语言链表初学者里出现率极高编译器报的错通常是unknown type name ListNode。第二我习惯把val放成int但真实项目里这里往往是一个结构体或者一个指针理解原理的时候把val想象成“任意可比较的载荷”会更有帮助。1.3 题目隐含的四条约束不管后面用哪种写法都必须同时满足下面四条缺一条结果就是错的两条输入链各自按升序排列这是前提不做这个假设的话问题会退化成排序问题合并后整体仍然升序原有结点应该被复用而不是复制一份数据出来除非明确要求不动原链表这点在第 4 节展开不能产生新的环也就是合并完的链必须是一条干净的、以NULL结尾的单链。最后一条特别容易被忽略。指针操作一旦写错比如把tail-next指向了已经遍历过的结点程序在打印结果的时候会直接死循环调试起来非常费劲因为打印函数本身就是死循环的地方。2. 思路一递归——代码最短但代价藏在栈里递归是这道题在教科书上出现最多的写法因为它的逻辑和“有序”这个性质贴合得近乎完美两条链的头结点谁小谁就一定是合并结果的第一个结点剩下的事情就是把“较小的那条链的后续部分”和“另一条链”再合并一次。2.1 递归的分解逻辑设两条链分别是l1和l2两者都非空时比较l1-val和l2-val如果l1-val l2-val那么l1必定是结果的头结点于是把l1-next改成merge(l1-next, l2)的返回值然后返回l1否则l2是结果头结点把l2-next改成merge(l1, l2-next)返回l2。递归的终止条件有两个而且必须写在最前面任意一条链为空时直接返回另一条。这一步同时处理了输入本身就是空链表的情况——如果l1是NULL返回l2哪怕l2也是NULL返回的仍然是NULL逻辑自洽。2.2 完整实现ListNode* mergeTwoListsRecur(ListNode* l1, ListNode* l2) { /* 递归出口任意一条链走完剩下的整条链直接作为结果 */ if (l1 NULL) return l2; if (l2 NULL) return l1; if (l1-val l2-val) { l1-next mergeTwoListsRecur(l1-next, l2); return l1; } else { l2-next mergeTwoListsRecur(l1, l2-next); return l2; } }四行有效代码没有任何临时变量没有任何循环变量这是它最大的优点。面试里手写的时候只要出口条件没写反基本不会出错。2.3 递归的三个真实隐患第一是栈深度。递归调用的层数等于两条链长度之和链长为 n 和 m 时最坏情况下函数会嵌套 nm 层。每层栈帧在这个函数里大概几十个字节链长上万的时候可能逼近默认栈大小链长十万以上就大概率栈溢出崩溃。这不是理论问题我在处理真实数据时确实遇到过——一次合并两条各含十几万条记录的链递归版本直接段错误换成迭代版就没事。第二是栈帧开销。每次调用都要保存返回地址、参数、局部变量函数调用的开销比一次循环判断大得多。虽然归并的复杂度量级没变但常数因子明显偏大。第三是调试困难。递归出错时栈回溯里全是同名函数很难一眼看出是第几层出了问题。相比之下迭代版可以直接打日志看每一轮的状态排查效率高得多。提示递归写法适合链长可控、并且编译器支持尾递归优化的场景。但这个函数并不是严格的尾递归递归调用之后还有return l1和对next的赋值所以不能指望编译器把它优化成循环。3. 思路二迭代加哑结点——工程里我最常用的写法如果只允许我保留一种写法我会留迭代加哑结点这一版。它的代码量比递归略多但没有任何栈风险指针流转过程可以完整打日志观察出问题时定位成本极低。3.1 哑结点到底解决了什么问题不借助哑结点的迭代写法第一步必须先比较两个头结点单独确定新链的头是谁然后才能进入循环。这意味着“确定头结点”和“往后接结点”是两段逻辑代码会重复一遍比较动作。哑结点也叫哨兵结点、dummy head的作用就是在真正的结果链前面放一个占位结点让每一个真实结点都走同一条“挂到 tail 后面”的路径头结点的特殊情况被消灭掉了。代价是最后必须返回dummy.next而不是dummy本身这是这套写法的唯一记忆点。3.2 完整代码与指针流转ListNode* mergeTwoListsIter(ListNode* l1, ListNode* l2) { ListNode dummy; /* 栈上的哨兵结点只借用它的 next 域 */ dummy.next NULL; ListNode *tail dummy; /* tail 始终指向结果链的最后一个结点 */ while (l1 ! NULL l2 ! NULL) { if (l1-val l2-val) { tail-next l1; /* 把 l1 当前结点接到结果链尾部 */ l1 l1-next; /* l1 前移注意顺序不能反 */ } else { tail-next l2; l2 l2-next; } tail tail-next; /* tail 前移到新接上的结点 */ } /* 循环结束时至少有一条链为空把剩下那条整体挂上去 */ tail-next (l1 ! NULL) ? l1 : l2; return dummy.next; }这段代码有四处是新手最容易写错的我逐条解释tail-next l1;和l1 l1-next;的顺序绝对不能反。如果先写l1 l1-next那么l1已经指向下一个结点了tail-next l1挂上去的就变成了“跳过当前结点之后的那一段”当前结点直接丢失同时因为l1-next仍指向后续结果链会从中间接上一整条尾巴长度明显不对。tail tail-next;必须放在if外面。因为不管走哪个分支结果链都增加了一个结点tail都要前移。放进分支里就会出现一条分支忘了移动tail导致后面的结点把前一个覆盖掉。dummy.next NULL;建议显式写上。栈上的结构体不清零虽然tail一开始指向dummy并且随后就被赋值覆盖但显式初始化能避免在调试时看到随机值产生误判。返回dummy.next不是dummy更不是dummy。dummy是函数栈上的局部变量函数返回后这块内存失效返回它的地址是典型的悬空指针调用方一访问就是未定义行为表现为偶发崩溃或者打印出乱七八糟的值。3.3 收尾那一步为什么可以直接挂很多人对tail-next (l1 ! NULL) ? l1 : l2;这一行不放心觉得“剩下的链里会不会有比已经接上的结点更小的值”。这个担心在本题里是多余的原因在于保持的不变式每次循环结束后l1和l2都指向各自链中尚未被合并的第一个结点且这两个结点的值都大于等于结果链尾部结点的值。因为两条输入链各自有序被跳过的那条链剩余部分的第一个结点一定是该链剩余部分里最小的而它之所以没被选中恰恰是因为它比另一条链当前的结点大。所以收尾时剩下的那条链整体都比结果链尾部大直接挂上去即可。这个推理建议自己拿纸推一遍推过之后这一行就再也不会写错了。3.4 哑结点放栈上还是堆上上面我放在栈上这是最常见也最高效的做法。如果你习惯用malloc分配哨兵ListNode *dummy (ListNode *)malloc(sizeof(ListNode)); dummy-next NULL; /* ... */ ListNode *head dummy-next; free(dummy); /* 必须记得释放否则每次调用漏一个结点 */ return head;堆版本多了一次malloc和一次free好处只是风格统一性能上是净亏的。栈版本唯一的心理负担是“返回了一个内部指针”但dummy.next指向的是堆上的真实结点dummy本身只有一个next域被读过函数返回后那块栈内存失效不影响已经取出的指针值。所以栈版本是安全的不用纠结。4. 思路三新建结点拷贝——原链表不能动时的唯一出路前两种写法都在做同一件事改指针复用原结点。这样做的前提是调用方不再需要原来那两条链了。现实里这个前提经常不成立。4.1 什么时候必须拷贝我遇到过几次典型的场景一份有序配置项链被三个模块共享某个模块需要一份“全局按优先级排序的总视图”但其他模块还要按原样遍历自己那份又比如缓存里的有序桶和临时计算结果合并原桶不能在合并过程中被拆散。这时候如果直接改指针等于把别人的数据结构给改坏了属于典型的隐蔽 bug——调用方可能过很久才发现自己的链莫名其妙短了一截。遇到这种情况只有两条路要么先深拷贝输入要么在合并过程中直接生成新结点。后者更省事一次遍历就完成。4.2 实现与内存细节ListNode* mergeTwoListsCopy(ListNode* l1, ListNode* l2) { ListNode dummy; dummy.next NULL; ListNode *tail dummy; while (l1 ! NULL l2 ! NULL) { int take; /* 记录这一轮要取哪个值 */ if (l1-val l2-val) { take l1-val; l1 l1-next; } else { take l2-val; l2 l2-next; } ListNode *node (ListNode *)malloc(sizeof(ListNode)); if (node NULL) { /* 分配失败要做善后 */ freeList(dummy.next); /* 释放已经建出来的半条链 */ return NULL; } node-val take; node-next NULL; tail-next node; tail node; } /* 把剩余链的值逐个复制过来同样不能直接挂原结点 */ ListNode *rest (l1 ! NULL) ? l1 : l2; while (rest ! NULL) { ListNode *node (ListNode *)malloc(sizeof(ListNode)); if (node NULL) { freeList(dummy.next); return NULL; } node-val rest-val; node-next NULL; tail-next node; tail node; rest rest-next; } return dummy.next; }和思路二相比这里多了三件事每次接结点都要malloc返回的链是完全独立的调用方负责整条释放收尾不能偷懒思路二那一行“直接挂”的优化在这里失效了剩余部分必须逐个复制因为原结点不能被共享必须处理malloc失败而一旦中途失败前面已经建出来的结点就成了垃圾所以要有一个统一的freeList把半成品清掉再返回NULL。这一点在面试里手写时经常被省略但真正上线跑在内存吃紧的嵌入式环境里漏掉就是内存泄漏。配套的释放函数很朴素但要注意它和思路二的配合关系void freeList(ListNode *head) { while (head ! NULL) { ListNode *tmp head-next; free(head); head tmp; } }注意freeList只能用在思路三返回的链上或者用在真正由malloc逐个建立的输入链上。如果你先调了思路二的合并函数两条原链的结点已经被混进结果链里了这时候再去freeList(l1)或freeList(l2)会产生重复释放double free并直接导致程序异常退出。这是链表程序最常见的崩溃来源之一排查时优先怀疑它。5. 三种写法放在一起跑实测对比与选择建议为了不让讨论停留在纸面上我给几种写法都配了同一套测试用例用一个简单的主函数手动构造输入并打印结果。5.1 测试脚手架#include stdio.h /* 从数组构造链表返回头指针 */ static ListNode* buildFromArray(const int *arr, int n) { ListNode dummy; dummy.next NULL; ListNode *tail dummy; for (int i 0; i n; i) { ListNode *node (ListNode *)malloc(sizeof(ListNode)); node-val arr[i]; node-next NULL; tail-next node; tail node; } return dummy.next; } /* 打印链表最多打印 limit 个防止环形链把屏幕刷爆 */ static void printList(const ListNode *head, int limit) { int cnt 0; while (head ! NULL cnt limit) { printf(%d%s, head-val, head-next ? - : \n); head head-next; cnt; } if (cnt limit) printf(... (超过 %d 个疑似成环)\n, limit); } int main(void) { int a[] {1, 3, 5, 7}; int b[] {2, 4, 6, 8, 10}; ListNode *l1 buildFromArray(a, 4); ListNode *l2 buildFromArray(b, 5); ListNode *r mergeTwoListsIter(l1, l2); printList(r, 100); freeList(r); return 0; }那个limit参数不是多余设计。我早期调链表题时不止一次被环形链坑过——printList没有出口条件程序卡在打印循环里看起来像“运行超时”实际是指针接错了。加上计数上限之后第一眼就能从输出里看出“链长不对多半成环了”。5.2 复杂度与适用场景对照维度递归法迭代加哑结点新建结点拷贝有效代码行数约 4 行约 12 行约 25 行时间复杂度O(nm)O(nm)O(nm)额外空间O(nm) 栈帧O(1)O(nm) 新结点是否修改原链表是是否栈溢出风险有链长越大越危险无无调用方是否负责释放否沿用原结点否沿用原结点是典型使用场景教学演示、链长小的场景工程默认选择原数据需保留、多模块共享5.3 一次完整的手工推演拿l1 1 - 3 - 5、l2 2 - 4走一遍迭代版方便对照代码理解tail的移动。初始时tail指向dummy轮次l1当前值l2当前值取谁结果链tail指向起始12-空dummy112l11结点 1232l21 - 2结点 2334l11 - 2 - 3结点 3454l21 - 2 - 3 - 4结点 455NULL循环退出1 - 2 - 3 - 4 - 5结点 5第 5 轮l2变成NULLwhile条件不成立跳出执行收尾把l1剩下的5整体挂上。注意这时候5这个结点本来就是原链上的结点next已经是NULL所以不需要额外置空——这也是复用结点写法的一个隐含优势。6. 踩坑清单上机最容易翻车的六个地方前面几节已经零散提到不少问题这里集中成一份清单。这些都是我自己或者身边同学实际踩过的不是从文档里抄的。6.1 返回了栈上哨兵的地址症状是程序有时正常、有时打印出垃圾值换台机器或者换个编译器行为还不一样。根因就是return dummy;或者return dummy;类型不对编译不过。只要记住“哨兵是工具不是结果”返回dummy.next就行。识别方法很简单如果合并两条非空链结果链的第一个值不是两条链头结点中较小的那个而是个莫名其妙的大数基本可以确定指针指到了失效的栈内存。6.2 忘记接剩余部分症状是结果链长度等于2 * min(n, m)或者刚好等于较短那条链长度的两倍。这个错误在调试时非常显眼因为后面一整段数据凭空消失了。修复方式就是在循环后加那一行三元表达式。我见过有人用两个if分别处理l1剩余和l2剩余逻辑也对但没必要——同一时刻至少有一方为空用三元表达式更简洁。6.3 比较符写成了而不是对int类型来说和的最终结果是一样的值相等时取谁都行。但如果结点携带的是“值 序号”这类复合载荷并且业务要求相同键值时保持原有的先后顺序也就是要求归并是稳定的那么必须用让l1优先。这时候如果用两条链里键值相同的结点会被交换顺序稳定性被破坏。归并排序要求稳定所以这一处细节直接决定排序结果是否符合预期。6.4 先移动指针再挂链前面 3.2 节讲过顺序问题这里再强调一次因为它是新手最高频的错误。记忆口诀先接线后走线。也就是先tail-next 当前结点再让来源链的指针前移。写的时候如果发现自己在同一行里既挂链又移动最好拆成两行可读性也比省行数重要。6.5 空链表与单结点边界必须测到的边界至少有四种两条都空、一条空一条非空、两条各一个结点且值相等、两条长度悬殊比如 1 个结点对 100 个结点。这四种覆盖了所有特殊分支。只测“长度接近且值不相等”这一种情况很容易漏掉收尾逻辑和相关的判断。6.6 释放时机搞混这是最危险的一类。思路二复用原结点合并完成后结果链的结点就是原来两条链的结点此时绝对不能再去释放l1或l2的头指针。因为合并后l1变量通常已经走空了变成NULL但如果你在函数里缓存了原始头指针并在外部释放就会把结果链里的结点提前释放掉后续访问全是悬空指针。安全的做法是思路二只释放结果链思路三才需要分别释放输入和输出。7. 从两路合并延伸到 K 路归并与链表排序把两路合并写熟之后最有价值的延伸方向有两个都是这道题的直接放大版。7.1 链表归并排序的自底向上写法链表的归并排序核心就是这道题。传统自上而下的递归写法需要找中点用快慢指针走一遍递归深度是 O(log n)比单纯合并安全得多。但如果你想彻底避开递归可以写自底向上的版本先用一个循环按步长 1、2、4、8……把链切成一段段长度为step的子链两两调用合并函数串起来。每一轮结束链的局部有序长度翻倍直到步长超过链长。这个写法的好处是没有递归、没有快慢指针纯迭代非常适合嵌入到对栈空间敏感的环境里。我当初写这个版本调了整整一个下午最后发现 bug 出在“切链”那一步——切完之后忘了把子链的尾部next置为NULL导致两个子链还是连在一起的合并时先把整条链遍历完才轮到第二条结果完全乱套。这个坑值得提前记下来。7.2 K 路归并的两种典型解法当你面对的不再是两条链而是 K 条有序链时直接两两合并也能做复杂度是 O(K * N)K 大了就吃不消。更常见的做法是用一个小顶堆维护每条链当前的头部结点每次弹出最小值接到结果链然后从被弹出结点所属的那条链里再取一个补进堆。这样复杂度降到 O(N log K)其中 N 是结点总数。还有一种从两路合并自然推导出来的分治写法把所有链两两配对合并一轮下来链的数量减半重复到只剩一条。它的复杂度和堆写法同阶但代码复用了本文的两路合并函数几乎不用额外写逻辑而且在链表这种不支持随机访问的结构上分治写法的实际表现往往比堆更好因为堆里存的是指针比较时要反复解引用。7.3 一个容易被忽略的性能细节如果输入链里的数据体积很大比如每个结点挂着一个 4KB 的缓冲区那么“复用结点”和“拷贝结点”的性能差距会被放大到几十倍。原因是复用只改指针而拷贝要走一遍内存分配和数据复制。这也解释了为什么工程里默认选迭代加复用结点——省下来的不是代码行数是实实在在的内存带宽和分配开销。我自己在实际操作中的体会是凡是输入数据可能很大的场合都优先用迭代加哑结点把递归版本只留在注释里当参考。递归版本真正的价值是帮你把“有序”这个性质想清楚一旦想清楚了落到代码上就该换成迭代。另外提一句写完合并函数后别急着丢掉输入链的原始头指针先确认一下调用方还要不要用——这个习惯能帮你避开第 6.6 节里最危险的那种崩溃。