在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(nm)其中n和m分别是两条链表的长度因为每个节点最多被访问一次。提示很多初学者会犯的一个错误是在合并过程中申请了新节点去存放数据然后再把新节点接到结果链表中。这样做虽然也能得到正确结果但空间复杂度会变成O(nm)背离了题目考察“原地操作”的本意在面试中会被扣分。我还想特别强调一点“比较后摘节点”和“把一个链表整个插入另一个链表”是有本质区别的。前者是按大小逐节点归并后者更像是两个链表“粘连”。这道题要求的是前者所以你必须逐节点比较不能偷懒。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指向1p2指向2。比较1和21更小把节点1从L1摘下接到L3尾部。此时L3 {1}p1后移指向3。第二步p1指向3p2指向2。比较3和22更小把节点2从L2摘下接到L3尾部。此时L3 {1, 2}p2后移指向4。第三步p1指向3p2指向4。3更小L3 {1, 2, 3}p1后移指向5。第四步p1指向5p2指向4。4更小L3 {1, 2, 3, 4}p2后移指向6。第五步p1指向5p2指向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 边界条件全覆盖验证写链表题最怕的就是边界条件处理得不完整。我整理了一份边界测试清单你可以直接拿着这份清单去验证代码测试场景输入L1输入L2期望输出两条链表都为空空空空L1为空空{1, 2}{1, 2}L2为空{3, 4}空{3, 4}L1全部小于L2{1, 2}{3, 4}{1, 2, 3, 4}L1全部大于L2{5, 6}{1, 2}{1, 2, 5, 6}两链等长且值交错{1, 3, 5}{2, 4, 6}{1, 2, 3, 4, 5, 6}两链长度不同{1, 5}{2, 3, 4, 6}{1, 2, 3, 4, 5, 6}所有值相等{2, 2}{2, 2}{2, 2, 2, 2}只有一个节点{1}{2}{1, 2}包含负数和0{-3, 0, 2}{-1, 1}{-3, -1, 0, 1, 2}这份表格是我实际测试时用的完整清单。很多人可能觉得测一两个正常情况就够了但真正的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 常见问题速查表为了方便你快速排查我把上面提到的坑整理成一张速查表症状可能原因排查方法段错误(Segmentation Fault)空指针解引用p-next被错误修改检查while循环条件打印关键指针的值结果链表缺少部分节点忘记更新rear指针指针移动顺序错误确认rear每接入一个节点后都后移程序卡死/无限循环链表成环打印前100个节点检查剩余链表拼接位置合并后L1或L2无法正常遍历未将L1-next和L2-next置空在Merge函数末尾重新赋值为NULL输出结果顺序错误比较条件写反了用了而不是在if-else中打印当前被选中的data值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);你就能清晰看到每一步的走向。确定逻辑正确后再把这些调试代码删掉。第三不要跳过边界条件测试。哪怕你觉得自己写得天衣无缝也要把所有边界用例跑一遍。好多人觉得“空链表还不简单”结果恰恰是在空链表上翻车的。按我上面的测试清单逐个验证花不了五分钟却能帮你省下大量排错时间。这个题目虽然基础但它真的是链表操作的分水岭。写好了你就有能力去挑战更复杂的链表算法写不好后面反转链表、环检测、相交链表都会磕磕绊绊。希望这篇内容能帮你把这关顺利闯过去。