企业官网建设流程全解析

在MOOC《数据结构》这门课里，“02-线性结构1 两个有序链表序列的合并”几乎是每个学C语言的人都会撞上的一道经典题目。不管你是正在期末复习的数据结构初学者，还是准备面试要刷LeetCode的求职党，这道题带来的核心价值都不只是“把两个链表接起来”那么简单。它背后藏着的指针操作、边界条件处理、原地合并的思路，会直接决定你后面能不能顺畅地搞定更复杂的链表题。

这篇博文我会从题目本身出发，先把题目到底在考什么讲透，再把完整的可运行代码贴出来，逐行解释我为什么这么写，最后把我自己踩过的坑和调试经验一并整理出来。对于刚入门的读者，我会把结构体定义、malloc分配、指向指针的指针这些前置概念一并讲清楚；对于已经有一定基础的读者，可以直接跳到第3节看合并函数的实现细节和复杂度分析。这篇内容全部基于我实际写过的代码和反复调试的经历，可以直接拿去复现，也可以作为面试前的知识点回顾。

1. 题目到底在考什么——先看懂问题本质

1.1 两个有序链表的合并是什么场景

先还原一下题目要求：给定两个递增排列的整数单链表L1和L2，要求将它们合并成一个新的递增有序链表L3，并且不能额外申请新的节点空间，只能通过调整指针的指向来完成。

如果你之前只写过数组版本的归并排序，第一次看到这个题可能会有点懵：数组合并是直接申请一个新数组，然后把两个数组的元素按大小依次拷贝进去；但链表不一样，每个节点是malloc出来的独立内存块，如果“拷贝”就要新建节点，那复杂度会变高，也违背了题目“不申请额外空间”的约束。所以正确的做法是“摘节点”：每次从L1或L2中取出较小的那个节点，把它从原链表上拆下来，再接到一个新的结果链表的尾部，直到某一条链表被取空，再把另一条剩余部分整个接上去。

这个场景在现实里非常常见。举个例子，分布式系统中的有序日志合并、两个有序文件的归并、数据库归并排序的底层环节，核心思想都跟这个一模一样。也就是说，这道题表面上是在让你写链表操作，实际上是在帮你建立“归并思维”。

1.2 为什么这个题目值得反复刷

我在带学弟学妹的时候，见过不少人链表题刷了不少，但遇到这一类题目还是容易卡住。原因很简单：链表操作最核心的难点就是指针的移动和边界条件，而这恰恰是很多人不熟练的地方。

这个题目特别好的一点在于，它把链表题的两大高频考点全占了：

• 指针操作：需要维护头指针、尾指针、移动指针，搞错一个指向就全盘崩。
• 边界条件：L1为空、L2为空、两条链表长度不等、链表只有一个节点、所有节点都相等……每一种情况都需要单独验证。

换句话说，这道题就是链表操作的“试金石”。如果你能不看答案、自己独立把这道题写对，并且能够清清楚解释每一步为什么要这么处理，那你在指针和链表这一块的基本功基本就过关了。后面无论是反转链表、链表求交点、还是合并K个有序链表，学起来都会顺利很多。

2. 动手写之前，先把两个前置概念吃透

2.1 单链表的结构体定义与带头节点

写链表题的第一步是先把结构体定义写明白。国内的数据结构教材（比如严蔚敏老师的《数据结构（C语言版）》）里，单链表的节点一般定义成下面这样：

typedef struct LNode { int data; // 数据域，存放节点的值 struct LNode *next; // 指针域，指向下一个节点 } LNode, *List; // 说明：LNode是结构体类型名，List是指向LNode的指针类型名

注意这里的细节：struct LNode *next;不能写成LNode *next;，因为在结构体内部LNode这个typedef别名还没有定义完成。这一点很多人会忽略，编译报错的时候一脸懵。

有了节点定义之后，接下来要决定用“带头节点”还是“不带头节点”的链表。

在MOOC浙大版《数据结构》的这道题里，其实两种情况都出现过。但我个人强烈建议在练习的时候都用带头节点的链表，原因有三个：

• 带头节点后，空链表和非空链表的处理逻辑可以统一，不用为“首节点是否为NULL”单独写分支。
• 插入、删除、合并等操作不需要频繁修改头指针本身，代码写起来更省心。
• 面试时跟面试官聊思路也更容易讲清楚，因为带头节点是工业界最常见的写法。

带不带头节点的区别，就有点像你去排队：不带头节点时，队伍的第一个人就是“队首”，这个人走了你得重新指定谁是新队首；带头节点时，你可以理解为队伍前头永远站着一个标记员，不管队伍怎么变，只要找到标记员就能找到整个队伍。

2.2 有序链表合并的核心思路与空间复杂度

核心思路一句话版：用两个指针分别指向L1和L2的第一个有效节点，比较它们指向的数据大小，把较小的那个节点接到结果链表末尾，然后对应指针后移，直到某一条链表走完，再把另一条剩余的链条直接接上。

这里有一个很重要的设计点：结果链表L3本身也不需要新建节点，只需要一个头节点（或者说，利用一个空的头节点作为“哨兵”），然后通过尾插法把从原链表中摘下来的节点一个个接上去。这样做的空间复杂度是O(1)——除了结果链表的头节点外，不额外分配任何节点空间。

时间复杂度自然是O(n+m)，其中n和m分别是两条链表的长度，因为每个节点最多被访问一次。

提示：很多初学者会犯的一个错误是，在合并过程中申请了新节点去存放数据，然后再把新节点接到结果链表中。这样做虽然也能得到正确结果，但空间复杂度会变成O(n+m)，背离了题目考察“原地操作”的本意，在面试中会被扣分。

我还想特别强调一点，“比较后摘节点”和“把一个链表整个插入另一个链表”是有本质区别的。前者是按大小逐节点归并，后者更像是两个链表“粘连”。这道题要求的是前者，所以你必须逐节点比较，不能偷懒。

3. 完整实现：从伪码到可运行代码

3.1 工具函数：创建链表与打印链表

在写合并函数之前，先准备好两个工具函数，否则测试的时候还得手动一个个malloc节点，非常痛苦。第一个是CreateList，从数组创建链表；第二个是PrintList，把链表的值依次打印出来。

#include <stdio.h> #include <stdlib.h> // 节点定义 typedef struct LNode { int data; struct LNode *next; } LNode, *List; // 带头节点：头指针指向一个不存数据的头节点 void CreateList(List L, int arr[], int n) { // L是已经存在的头节点，arr是数组，n是数组长度 LNode *rear = L; // 尾指针，初始指向头节点 LNode *s; for (int i = 0; i < n; i++) { s = (LNode *)malloc(sizeof(LNode)); // 大头节点 s->data = arr[i]; s->next = NULL; rear->next = s; // 把新节点接到尾部 rear = s; // 尾指针后移 } } void PrintList(List L) { LNode *p = L->next; // 跳过头节点，从第一个有效节点开始 while (p != NULL) { printf("%d ", p->data); p = p->next; } printf("\n"); }

CreateList里用到了一个非常重要的技巧：尾插法。因为我们要保持链表的有序性（数组本身是递增的），所以新节点必须一直挂在链表的末尾，用一个rear指针始终指向最后一个节点，这样就能在O(1)时间内完成尾部插入。如果你忘了维护尾指针，每次都从头遍历到末尾再插入，创建链表的时间复杂度就会变成O(n²)，当数据量大的时候会慢到怀疑人生。

3.2 合并函数完整代码

接下来是整篇博文的重头戏——合并函数。我直接放出我最终调试通过的版本，然后逐段解释。

List Merge(List L1, List L2) { // L1和L2都是带头节点的递增有序链表 List L3 = (List)malloc(sizeof(LNode)); // 为结果链表创建头节点 if (L3 == NULL) { // 内存分配失败，直接返回空指针 return NULL; } L3->next = NULL; LNode *p1 = L1->next; // 指向L1的第一个有效节点 LNode *p2 = L2->next; // 指向L2的第一个有效节点 LNode *rear = L3; // 结果链表的尾指针 while (p1 != NULL && p2 != NULL) { if (p1->data <= p2->data) { // 摘下p1节点 rear->next = p1; p1 = p1->next; // p1后移 } else { // 摘下p2节点 rear->next = p2; p2 = p2->next; // p2后移 } rear = rear->next; // 尾指针始终指向结果链表的最后一个节点 } // 把剩余链表直接接入结果链表尾部 if (p1 != NULL) { rear->next = p1; } else { rear->next = p2; } // 重要：将L1和L2的头节点置空，避免后续误操作 L1->next = NULL; L2->next = NULL; return L3; }

这段代码看起来不长，但里面每一步都值得反复琢磨。我来给你拆开讲。

第一个关键点：为什么要用一个局部变量rear而不是直接操作L3->next？

因为L3->next只能表示链表当前的“头”，而合并需要一直把新节点接到“尾”。如果每次都从头找尾部，那时间开销没法接受。所以我用一个rear指针始终指向当前结果链表的最后一个节点，每接入一个新节点，就把它往后挪一位。这其实是链表操作里的标准套路：维护尾指针的尾插法。

第二个关键点：为什么比较条件用<=而不是<？

用<=可以保证当两个节点值相等时，优先取L1的节点，这样合并后的链表是稳定的。虽然题目没有明确要求稳定性，但“稳定归并”本身是个良好的习惯。在面试场景下，如果面试官追问“相等元素怎么处理”，你能说出“用<=保证稳定性”这个点，会是加分项。

第三个关键点：合并完之后为什么要L1->next = NULL; L2->next = NULL;？

这是很多教程不会讲、但实际工程中非常重要的细节。原来的L1和L2链表在合并后被“拆空”了，它们的节点已经全部挂到了L3上。如果你不把L1和L2的头节点的next置空，那么当你尝试再次遍历或打印L1时，你会遍历到一条内容不可预期的“脏链表”。在MOOC的在线评测系统中，这一步不加可能也能通过（因为评测函数只检查L3）；但一旦你把这套代码放到真实的工程项目中，让外部代码继续持有L1和L2的指针，不置空就会埋下极难排查的bug。

3.3 合并过程现场演示

光看代码还不够，我举个具体的例子，带着你走一遍合并流程。

假设L1存放的是 {1, 3, 5}，L2存放的是 {2, 4, 6}。

• 第一步：p1指向1，p2指向2。比较1和2，1更小，把节点1从L1摘下，接到L3尾部。此时L3 = {1}，p1后移指向3。
• 第二步：p1指向3，p2指向2。比较3和2，2更小，把节点2从L2摘下，接到L3尾部。此时L3 = {1, 2}，p2后移指向4。
• 第三步：p1指向3，p2指向4。3更小，L3 = {1, 2, 3}，p1后移指向5。
• 第四步：p1指向5，p2指向4。4更小，L3 = {1, 2, 3, 4}，p2后移指向6。
• 第五步：p1指向5，p2指向6。5更小，L3 = {1, 2, 3, 4, 5}，p1后移，此时p1为NULL。
• 第六步：循环结束，因为p1已经是NULL，走rear->next = p2分支，把剩余链表 {6} 整体接入。最终L3 = {1, 2, 3, 4, 5, 6}。

发现没有？整个过程中没有任何一个节点被新建或复制，所有操作都是“改指针”。这就是链表比数组优雅的地方：合并两个上万长度的有序链表，数组可能要开辟一块新的上万个元素的空间，而链表只需要额外开辟一个头节点的空间。

3.4 边界条件全覆盖验证

写链表题，最怕的就是边界条件处理得不完整。我整理了一份边界测试清单，你可以直接拿着这份清单去验证代码：

这份表格是我实际测试时用的完整清单。很多人可能觉得测一两个正常情况就够了，但真正的bug往往隐藏在“L1为空”、“所有值相等”这种看起来不起眼的场景里。你可以在自己的机器上把这些用例全部跑一遍，确保输出完全符合预期。

完整的测试main函数我放在下面，可以直接编译运行：

int main() { List L1 = (List)malloc(sizeof(LNode)); List L2 = (List)malloc(sizeof(LNode)); if (L1 == NULL || L2 == NULL) { printf("内存分配失败\n"); return 1; } L1->next = NULL; L2->next = NULL; int a[] = {1, 3, 5}; int b[] = {2, 4, 6}; CreateList(L1, a, 3); CreateList(L2, b, 3); printf("L1: "); PrintList(L1); printf("L2: "); PrintList(L2); List L3 = Merge(L1, L2); printf("L3: "); PrintList(L3); // 释放内存 free(L1); free(L2); free(L3); return 0; }

这里我特意在main里面检查了malloc的返回值。在校OJ上可能不检查也能过，但在真实项目中内存分配失败是可能发生的，如果不去检查就直接用空指针，程序会直接段错误。

4. 实际操作中最容易踩的四个坑

4.1 指针丢失，节点找不回来

链表操作最大的噩梦就是指针丢失。什么意思呢？假如你在合并过程中直接写：

rear->next = p1; p1 = p1->next; rear = rear->next;

看起来好像没问题，但如果你把顺序写反，比如先p1 = p1->next再rear->next = p1，那p1原来的节点就断了，后面的代码拿到的完全是错误的数据。类似的，如果你忘了rear = rear->next，那么下一次接入新节点时就会覆盖上一次接入的节点，导致结果链表永远只有两个节点。

防坑心得：你在写链表操作时，脑中一定要有一张“当前有几个指针指向这个节点”的计数表。任何节点在被free或改变指向之前，必须先确保还有另一个指针能到达它。或者说：先牵线，再断线。

4.2 空指针解引用

第二种高频bug是空指针解引用。比如在PrintList中，如果你直接写while (p->next != NULL)而不是while (p != NULL)，那么当链表只有一个节点时，打印完这个节点后p会变成NULL，下一次循环条件访问p->next就会崩溃。

在合并函数里也是一样。while (p1 != NULL && p2 != NULL)这个条件中，&&是短路运算符：一旦p1为NULL，后面的p2 != NULL就不会被求值。写这个条件时千万不能把顺序调成while (p1->next != NULL && p2->next != NULL)，否则当其中一条链表只有一个节点时进入循环，操作完最后一个节点后再判断条件就会访问NULL->next，直接段错误。

4.3 死循环：链表中形成环

还有一种隐蔽的bug就是形成环。比如你在把剩余链表拼接到结果链表尾部时，如果rear没有指向最后一个节点，而是指向了倒数第二个节点，然后你再执行rear->next = p1，结果就会把p1这条链表接在了一个中间位置，导致结果链表里出现环。这种bug非常难查，因为程序不会立刻崩溃，而是在你遍历链表时无限循环。

我有一个排错技巧：在打印链表时，可以加一个“保险丝”，打印一定数量的节点后就强制停止。比如:

int count = 0; while (p != NULL && count < 100) { printf("%d ", p->data); p = p->next; count++; }

这样即使链表中存在环，程序也不会卡死，你能从中看到打印内容是否异常，快速定位问题。但这个只是调试手段，定位之后一定要把问题根源修好，不能靠“打印100个就停”来掩盖环的存在。

4.4 内存泄漏：只malloc不free

链表题很少有内存泄漏的困扰，但这道题有个特殊之处：合并函数中为L3 malloc了一个头节点。如果在后续逻辑中你提前return了，或者在某些分支中没有释放L1、L2的头节点，就会造成内存泄漏。

虽然在校OJ上，程序结束后操作系统会回收所有内存，内存泄漏不影响判题结果，但一旦你离开OJ，进入企业级开发环境，内存泄漏就是大问题。服务跑一天两天看不出来，跑一个月就会把内存吃光。

我的习惯是：在main函数的末尾统一释放所有动态分配的内存，同时用Valgrind或AddressSanitizer检查是否有泄漏报告。这是检验指针功力的硬指标。

4.5 常见问题速查表

为了方便你快速排查，我把上面提到的坑整理成一张速查表：

5. 从考试到面试：这个题还能怎么变

5.1 面试高频变形：合并K个有序链表

当你能把两个有序链表的合并写得很熟练之后，下一个自然而然的问题就是：如果给你K个有序链表，怎么把它们全部合并成一个有序链表？

常见的解法有三种：

• 逐一合并法：先合并第一个和第二个，再把结果和第三个合并，依次类推。时间复杂是O(K² * n)。
• 两两合并法：先把第1个和第2个合并，第3个和第4个合并……得到K/2个链表，再重复，直到只剩一个。时间复杂度是O(K * logK * n)。
• 优先队列法（堆）：把每个链表的当前头节点放入最小堆，每次弹出最小的节点，然后把它的next节点进堆。时间复杂度同样是O(K * logK * n)，但实现更直观。

这道题的进阶版在面试中非常常见，比如LeetCode的23题。如果你能把基础版本讲清楚，面试官接下来很可能就会让你写K路归并。建议你学完本文的基础版本后，自己动手写一遍优先队列法。

5.2 递归实现：另一种思考方式

除了上面的迭代写法，这道题也能用递归来写。递归的核心想法是：合并两个链表的问题，可以转化为“取出较小节点，并将其next指向剩余链表的合并结果”。

List MergeRecursive(List L1, List L2) { // 递归终止条件：任一链表为空，直接返回另一条链表 if (L1 == NULL) return L2; if (L2 == NULL) return L1; if (L1->data <= L2->data) { L1->next = MergeRecursive(L1->next, L2); return L1; } else { L2->next = MergeRecursive(L1, L2->next); return L2; } }

注意这个递归版本假设传入的是不带头节点的链表。递归写法的优点是代码极短、逻辑清晰，缺点是当链表很长时可能造成递归栈溢出，而且在面试中，递归返回值容易被忽略。我的建议是：两种写法都要会，写题时用迭代更稳，面试聊思路时可以提一句“这个问题也可以用递归实现”，展示你的思维广度。

5.3 基础变体：逆序合并和去重合并

再延伸一下，如果题目改成“合并后要求降序排列”，你有一个非常漂亮的解法：依然用升序合并的代码得到L3，然后对L3做一次链表反转。反转链表本身又是一个经典题，你等于一道题练了两个考点。

如果题目要求“合并后去除重复元素”，那你只需要在合并过程中多加一个判断：如果即将接入的节点值与结果链表尾节点的值相等，就跳过（或者释放掉）这个节点。这个变体在实际处理有序数据时非常有用，比如日志合并时要去掉重复时间戳。

这些变形提醒我们：不要死记代码，要理解每一行代码背后的原因。一旦你理解了这个合并函数的每个分支为什么存在，那么不管题目怎么变，你都能应对。

6. 写在最后的一些经验

这道题我前前后后写了很多遍，从最开始照着答案抄都抄不对，到后来闭着眼睛能把边界条件列清楚，中间经历了大量的调试。回头来看，有几点心得非常想分享给你。

第一，链表题一定要动手画图。我见过太多学生盯着代码看半小时也找不到bug，但把节点和指针画在纸上，三秒钟就发现哪里断了。不要嫌麻烦，很多复杂链表题，画图是最快的解题手段。

第二，调试时善用打印。在合并循环里临时加上printf("p1=%d p2=%d\n", p1->data, p2->data);，你就能清晰看到每一步的走向。确定逻辑正确后，再把这些调试代码删掉。

第三，不要跳过边界条件测试。哪怕你觉得自己写得天衣无缝，也要把所有边界用例跑一遍。好多人觉得“空链表还不简单”，结果恰恰是在空链表上翻车的。按我上面的测试清单逐个验证，花不了五分钟，却能帮你省下大量排错时间。

这个题目虽然基础，但它真的是链表操作的分水岭。写好了，你就有能力去挑战更复杂的链表算法；写不好，后面反转链表、环检测、相交链表都会磕磕绊绊。希望这篇内容能帮你把这关顺利闯过去。