企业官网建设流程全解析

链表题里，“合并两个有序链表”属于那种第一眼看过去毫无门槛、真动手写又总有地方要返工的题。我从最早用 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 时，最坏情况下函数会嵌套 n+m 层。每层栈帧在这个函数里大概几十个字节，链长上万的时候可能逼近默认栈大小，链长十万以上就大概率栈溢出崩溃。这不是理论问题，我在处理真实数据时确实遇到过——一次合并两条各含十几万条记录的链，递归版本直接段错误，换成迭代版就没事。

第二是栈帧开销。每次调用都要保存返回地址、参数、局部变量，函数调用的开销比一次循环判断大得多。虽然归并的复杂度量级没变，但常数因子明显偏大。

第三是调试困难。递归出错时，栈回溯里全是同名函数，很难一眼看出是第几层出了问题。相比之下迭代版可以直接打日志看每一轮的状态，排查效率高得多。

提示：递归写法适合链长可控、并且编译器支持尾递归优化的场景。但这个函数并不是严格的尾递归（递归调用之后还有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; }

这段代码有四处是新手最容易写错的，我逐条解释：

1. tail->next = l1;和l1 = l1->next;的顺序绝对不能反。如果先写l1 = l1->next，那么l1已经指向下一个结点了，tail->next = l1挂上去的就变成了“跳过当前结点之后的那一段”，当前结点直接丢失，同时因为l1->next仍指向后续，结果链会从中间接上一整条尾巴，长度明显不对。
2. tail = tail->next;必须放在if外面。因为不管走哪个分支，结果链都增加了一个结点，tail都要前移。放进分支里就会出现一条分支忘了移动tail，导致后面的结点把前一个覆盖掉。
3. dummy.next = NULL;建议显式写上。栈上的结构体不清零，虽然tail一开始指向dummy并且随后就被赋值覆盖，但显式初始化能避免在调试时看到随机值产生误判。
4. 返回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 复杂度与适用场景对照

5.3 一次完整的手工推演

拿l1 = 1 -> 3 -> 5、l2 = 2 -> 4走一遍迭代版，方便对照代码理解tail的移动。初始时tail指向dummy：

第 5 轮l2变成NULL，while条件不成立跳出，执行收尾把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 节里最危险的那种崩溃。