有序链表合并详解：C语言双指针原地归并实现

两副有序的扑克牌合在一起还要保持有序你会怎么做大多数人会从两叠牌的最上面各取一张比对小的拿下来放新牌堆。这道链表的合并习题本质上就是把这个动作翻译成指针操作。很多数据结构教材会把两个有序链表序列的合并放在线性表章节的习题里看起来平平无奇但它几乎涵盖了单链表操作的所以基本功指针移动、边界判断、头结点处理、空间复用。不管你是期末备考、考研刷题还是想补一补基本功这篇文章都适合你。我会用 C 语言给出完整可运行的解法拆解每一步为什么这么做然后把我自己踩过的坑和调试方法一并分享出来。1. 先看清题目到底要你做什么1.1 题目考的是归并而不是排序先明确习题2.5这类题目的经典表述有两个按值非递减排列的有序单链表La和Lb要求将它们合并成一个新的有序单链表LcLc仍然按值非递减排列。关键约束是——要求利用原表的结点空间不另设新的结点。换句话说你不能 new 出一堆新节点把数据搬过去而是在原有的节点之间改改指针把两条链串成一条有序的链。你可能会想把两条链的数据放进数组排序一遍再建一条新链不也挺简单能跑但这不是题目想考察的。数据结构习题的意图从来不是用任何方法解决问题而是用最贴合这个结构的办法解决问题。如果借助数组时间复杂度是 O((mn)log(mn))空间复杂度 O(mn)完全没有体现链表的优势。这题真正想让你掌握的是归并思想——两个已经有序的序列怎样用 O(mn) 时间合并成有序序列。归并排序之所以叫归并核心合并步骤用的正是这个思路。要注意非递减这个词。很多教材写的是非递减而不是递增意味着允许相等元素连续出现。这个细节会影响你合并时相等元素的处理方式也涉及稳定性问题后面代码部分我会细说。1.2 为什么一定用链表而不是数组数组也能实现归并那教材为什么非要用链表因为链表有数组不具备的两个特性一是插入不需要移动元素二是不需要预先知道总长度。对于合并这个问题数组版的归并你通常得开一块临时空间最后再把结果拷回去而链表版的合并只需要改一连串next指针不需要额外的存储空间这是一种物理意义上的原地合并。另一个隐藏考点是头结点。链表分带头结点和不带头结点两种很多初学的人在这上面翻车。带头结点的链表有一个哑结点dummy node作为哨兵好处是无论是插入第一个元素还是删除第一个元素操作逻辑都不用单独写特殊情况而不带头结点的链表头指针本身就是一个真实的存储数据的节点一旦这个节点被移走你要记得更新头指针。本题目如果你用带头结点的写法代码会简洁很多。这也是我推荐的写法。2. 核心算法思路与为什么这样做2.1 双指针遍历从两副有序的牌说起想象你手上有两堆已经按从小到大排好的牌每堆的最上面是最小的牌。你想得到一叠从小到大的牌做法就是每次只看两堆最上面的那张牌取较小的一张放到新牌堆的底部然后继续。这个每次只看两堆最上面的操作翻译到链表里就是两个指针分别指向两条链表的当前节点。一开始pa指向La的第一个有效节点pb指向Lb的第一个有效节点。每次比较pa-data和pb-data谁小就把谁接到结果链表的尾部然后让对应的指针向后移一步。一轮循环下来当一个指针变成NULL说明这条链表已经遍历完了另一条链表剩下的节点直接接到结果后面即可。这就是双指针法也叫二路归并的合并阶段。它之所以高效是因为每次比较只需要 O(1) 时间而且每个节点最多被移动一次。2.2 为什么可以原地合并不需要新建节点如果说双指针是主心骨那么复用节点就是这题最优雅的地方。因为两个链表原本就是有序的我们做的只是把节点从两条链上解下来重新串起来。每个节点的next指针可以被覆盖节点本身还在所以不需要 malloc 任何新空间。举个例子La {1, 3, 5}Lb {2, 4, 6}。合并开始pa指向1所在的节点pb指向2所在的节点。因为1 2我们让结果链表的尾部直接指向1这个节点然后pa指向3。下一次比较3和22更小就把2节点接过来pb指向4。整个过程没有任何节点被复制或新建只是指针在不断重连。这样做的好处不只是省内存。面试里如果你写的解法是新建了 mn 个节点面试官往往会追问一句能不能不建新节点这题就是要训练你用指针操作去缝合两条链的能力。我个人觉得这种在原有的基础上重排关系的思路比单纯地造新数据要难得多但也值钱得多。3. 完整代码实现与逐段讲解3.1 结构体定义与基础工具函数先定义单链表的节点结构这是整个实验的基础。这里采用最常见的定义方式#include stdio.h #include stdlib.h typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;LinkList本质上是LNode *但用这个别名能明确表达它是一条链表的头指针这层语义。为了测试我们通常还需要一个创建带头结点链表并插入数据的函数。下面我提供一个简单的尾插法把数组中的元素逐一追加到链表尾部void CreateList(LinkList L, int arr[], int n) { L (LinkList)malloc(sizeof(LNode)); // 创建头结点 L-next NULL; LNode *tail L; for (int i 0; i n; i) { LNode *s (LNode *)malloc(sizeof(LNode)); s-data arr[i]; s-next NULL; tail-next s; tail s; } }这里的C风格引用写法LinkList L是为了让函数内部修改头指针能传回外层。如果你在纯 C 环境下编译需要改成二级指针LinkList *L后面我会提到这点的注意事项。还需要一个打印函数方便我们调试时随时查看链表内容void PrintList(LinkList L) { LNode *p L-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }3.2 合并函数详解带头结点版本下面进入核心部分。我直接给出合并函数然后逐行拆解为什么这么写void MergeList(LinkList La, LinkList Lb, LinkList Lc) { LNode *pa La-next; // 指向 La 的第一个有效节点 LNode *pb Lb-next; // 指向 Lb 的第一个有效节点 Lc La; // 复用 La 的头结点作为 Lc 的头结点 LNode *pc Lc; // pc 始终指向结果链表的当前尾部 while (pa ! NULL pb ! NULL) { if (pa-data pb-data) { pc-next pa; // 把 pa 指向的节点接到结果链尾部 pc pa; // 更新尾部指针为 pa 所在的节点 pa pa-next; // pa 向后移动继续比较 } else { pc-next pb; pc pb; pb pb-next; } } // 循环结束后最多只剩一条链表还有剩余节点 pc-next (pa ! NULL) ? pa : pb; free(Lb); // 释放 Lb 的头结点 }这段代码最核心的地方在于Lc La这一步。因为题目允许复用原节点我们直接把La的头结点征用为结果链表的头结点这样就不用再为了头结点单独 malloc 一块内存。很多初学者会另写Lc (LinkList)malloc(sizeof(LNode))那也可以但就多了一次分配和一次释放没必要。pc Lc以后pc始终指向当前结果链表的最后一个节点。为什么pa和pb的一大段比较逻辑里每一步都是先接节点、再更新尾部、再后移指针因为顺序不能乱。如果你先把pa pa-next那你就丢失了当前节点没法把它接到结果链表上了。如果你先把pc pa再把pa pa-next也能工作但要注意pc-next还没设置就移动了pc之后反而容易漏接。我建议初学者统一按接、移、走三步走第一步让前一个尾部节点指向当前节点第二步让pc跳到当前节点第三步让原链指针往后走。循环结束以后为什么一句话就能接完剩余部分因为pc-next pa ? pa : pb。如果pa不是NULL说明pb已经走完La剩下的所有节点都已经按序连好了直接整串接过去即可反之则接pb。这一步同时处理了三类情况pa为空、pb为空、两者都为空此时pc-next NULL正好。最后别忘了free(Lb)Lb的头结点已经没有任何用处了不释放会造成内存泄漏。3.3 边界条件与特殊情况处理边界条件往往是代码写对的关键。我整理了这题最常见的四种边界情形以及代码里是怎么自动兜住的第一种两条链表都为空。此时pa和pb都是NULL循环不会执行pc-next (pa ! NULL) ? pa : pb得到NULL。合并结果就是一个空链表正确。第二种一条链表为空另一条非空。比如La为空Lb {2, 5}。pa NULL循环不进入直接pc-next pb结果就是{2, 5}。这正好是合并的最简形态。第三种两条链表等长且所有元素交替更小。比如{1, 3, 5}和{2, 4, 6}。while 循环会完整走完最后pa和pb同时变为NULLpc-next接到空指针。正确。第四种一条链表很短另一条很长。比如{1}和{2, 3, 4}。循环第一次比较后pa变成NULL循环退出直接接上pb所在的整条链。正确。我刚才代码里用的是pa-data pb-data也就是相等时把pa的节点先接进来。这样写的好处是保持了稳定性原来在La中先出现的元素合并后依然在Lb的同值元素前面。如果题目没有明确要求稳定性也能跑但面试时能说出相等时优先取第一个链表的节点可以维持稳定性会是不错的加分项。4. 复杂度分析与测试用例验证4.1 时间与空间复杂度推导先说时间复杂度。设La有 m 个节点Lb有 n 个节点。while 循环的每一轮都会让pa或pb其中一个向后移动一步把它们想象成两条队伍每轮消耗一个节点。最坏情况下要一直比到两条链都走完才结束循环执行 m n 轮。循环结束后剩余节点的连接操作是 O(1) 的。所以总时间复杂度是 O(m n)。这其实是最好的结果了。因为要合并两个有序序列至少得把两个序列都看一遍才能确定全局顺序不可能低于 O(m n)。如果你看到有人声称 O(1) 时间合并完那一定是在玩文字游戏要么他已经提前知道了两个序列的某些特殊关系要么他把合并和连接混为一谈。再说空间复杂度。因为我们没有新建任何节点只是复用了La和Lb的节点额外只用了几个指针变量所以额外空间是 O(1)。如果你自己新建一条结果链那空间复杂度就是 O(m n)。4.2 构造测试数据验证空说无凭我准备了三组测试数据读者可以自己复制代码跑一遍看看。第一组是最常规的情况La {1, 2, 4}Lb {1, 3, 4}。输出应当是1 1 2 3 4 4。注意两个链表里都有1和4这能验证相等节点是否都保留下来。第二组验证一条链更长La {1, 3}Lb {2, 4, 5, 6, 7}。输出应当是1 2 3 4 5 6 7。这个用例主要检查循环结束后剩余节点是否正确整串接入。第三组验证边界La {}Lb {0}。输出应当是0。这个用例专门验证空链表的情形。测试代码大概是这样的int main() { LinkList A, B, C; int a[] {1, 2, 4}; int b[] {1, 3, 4}; CreateList(A, a, 3); CreateList(B, b, 3); printf(La: ); PrintList(A); printf(Lb: ); PrintList(B); MergeList(A, B, C); printf(Lc: ); PrintList(C); return 0; }我实际跑过很多次这段代码输出是稳定的。要注意的是A和B在调用MergeList之后就不能再单独访问了因为它们的节点已经混入C的链表结构中。这不是 bug正式这种指针转移才实现了原地合并。5. 实操中常见的坑与排查技巧5.1 空指针访问与断链问题我见过太多人在这道题的代码上栽跟头总结下来高频问题就三类。第一类是空指针访问。比如你在循环里写pc-next pa-next然后pa pa-next最后发现输出不全。原因通常是你本意是让结果链接上pa当前节点结果你把pa-next接过去了跳过了pa本身后续指针错位还可能把NULL解引用。第二类是断链。什么叫断链就是你用pc接上了pa随后pa后移但之前pa-next指向的那个节点没有任何指针指向它了。在一般的比较逻辑里这不会出问题因为比较的双方总有一方还在被另一个指针pa或pb持有。真正容易断链的时候是循环结束后的pc-next赋值有人会写if (pa) pc-next pa; if (pb) pc-next pb;这其实也行但注意这是两个独立的 if如果前面已经接上了pa后面if (pb)又覆盖了pc-next就会把刚接上的pa后半段丢掉。所以要么用if ... else if要么直接像我那样用三元表达式。第三类是不带头结点引发的头指针更新问题。如果你把两条不带头结点的链表拿来合并就必须在每次移动最小节点后判断是否第一个节点如果是则要更新Lc头指针。这个逻辑很容易漏。解决的简单办法是先在函数内部定义一个新的头结点指针head让它始终指向已经接好的最后一个节点最后用Lc head-next返回。这本质上是给自己造了一个临时哑结点。5.2 用打印链表调试法快速定位遇到输出不对很多人的第一反应是盯着代码瞪眼。我推荐的做法是在每个循环关键位置加上打印语句用最笨但最有效的方式看指针到底走到哪了。比如你可以在循环开头加上一句printf(pa%d pb%d\n, pa ? pa-data : -1, pb ? pb-data : -1);再在循环结束后打印整个结果链。这样你能非常直观地看到两个指针是怎么交替消费节点的一旦某一步接错了输出的数字顺序会立刻暴露问题。我自己调试时还会做一个短小用例策略不要用十个节点的数据去测用三四个节点的最小用例。比如{1, 3}和{2, 4}一共四个节点手动模拟一遍指针的变化再对照代码的执行过程很快就能定位到是哪一步的逻辑和预期不一致。5.3 几个必须想清楚的问题除了代码本身还有几个概念问题建议自己口头回答一遍能讲清楚才算真的掌握了。第一个问题合并后原来La和Lb的头结点去哪了答案是其中一个头结点被复用为Lc的头结点另一个被free释放。如果你理解成合并完三条链表都存在只是内容重合了那说明你对指针指向共享内存的理解还不到位。第二个问题Lc和La是什么关系在我们的代码里Lc初始等于La也就是说Lc和La在合并开始时指向同一个头结点。合并完成后原来的La这种说法已经不再成立了因为它的节点已经被重新组织La这个指针在语义上已经被吸收进了Lc。第三个问题如果把papb时改为优先取pb的节点结果还正确吗正确但稳定性变化了。如果题目没有专门要求通常两种写法都算对如果面试官问了相等时你会选哪个你应当能说出稳定性差异。6. 衍生问题与进阶思考6.1 如果不带头结点代码差在哪里我上面给的版本建立在带头结点的基础上。如果题目或者团队已有的链表实现是不带头结点的你需要重写几处关键逻辑。第一种思路是临时头结点法。函数内部 malloc 一个假的头结点让合并逻辑和带头结点版本保持一致最后把真正的头结点地址返回释放假头结点。这算是最省事的改动而且是很多标准库实现的做法。第二种思路是直接处理头指针。先比较La和Lb的第一个节点谁小谁是新的头然后继继续双指针比较。这里最大的坑是一旦你把第一个节点从原链上移走原链的头指针就要更新否则你后续对原链的遍历会重复碰到已经转移走的旧头节点。如果是 C 语言必须用LinkList *二级指针来改传入的头指针变量否则外层感知不到变化。不带头结点的版本代码量会明显增加而且容易出现头指针指向了错误节点这种隐蔽 bug。所以我现在写链表工具类代码时都默认带头结点哪怕题目要用不带头结点的链表我也会先在心里构建一个虚拟头结点来辅助思考。6.2 递归写法很短但不要在生产中用有人喜欢展示递归解法我也写出来供读者参考LinkList MergeRec(LinkList pa, LinkList pb) { if (pa NULL) return pb; if (pb NULL) return pa; if (pa-data pb-data) { pa-next MergeRec(pa-next, pb); return pa; } else { pb-next MergeRec(pa, pb-next); return pb; } }这个写法的优点是逻辑极简和数学归纳法如出一辙先考虑两个基本情况某条链为空就返回另一条然后递归地将较小节点的next指向剩余两条链合并的结果。缺点也明显递归调用栈的深度和链表长度成正比。如果链表有十万个节点递归深度十万层可能会导致栈溢出。而且每次递归都有函数调用的开销。实际项目里几乎不用这种写法但在面试里写出来能展示你对递归的理解前提是你把栈溢出的风险也主动说出来。6.3 从两个链表扩展到 K 个链表两个有序链表合并是基础力扣上有一道经典题叫合并 K 个升序链表。如果直接思路是两两合并先合并第 1、2 条再合并结果和第 3 条总的复杂度是 O(KN)其中 N 是总节点数。更优的做法是使用优先队列把 K 条链表的当前最小节点放进一个最小堆每次取出堆顶接到结果链然后让该节点的下一个节点入堆这样总复杂度是 O(N log K)。理解了本节的双链表合并之后再去看 K 路归并你会发现核心还是那双指针的思路只不过选最小的动作从比较两个值变成了堆的堆顶操作。这就是能力的迁移。数据结构刷题不能只背题解要看到不同题目之间的骨架其实是同一副。最后再说点题外话。这几年我帮人改代码发现很多入门者不是不会写算法而是被编译环境折磨得够呛。比如在 C 语言中传引用是 C 的语法如果你用gcc而不是g编译会直接报错。这时候你有两个选择要么把文件后缀改成.cpp用g编译要么把所有LinkList 改成二级指针。我给初学者的建议是先在一套环境里跑通不要频繁切换等理解了指针本身再去考虑不同写法之间的等价性。等这个合并函数你能闭着眼写出来再试着把free(Lb)去掉看看用valgrind或者 ASAN 工具能报出什么内存错误这比单纯刷题更能锻炼动手能力。