★ FEATURED ARTICLE 链表拼接.c这个文件名在很多人电脑里都出现过。它可能来自大学机房的实验课来自某次面试前的临时练习甚至来自一个写了一半就丢在角落的工程目录。名字起得随意但打开文件之后代码往往没那么随便——这通常是第一次认真和指针较劲的地方。链表拼接听着简单就是把两个链表接在一起可真动手写的时候断链、野指针、死循环一个接一个冒出来。这篇文章就从这个朴素的文件名出发把链表拼接的三种典型需求、背后的指针操作原理、完整实现代码、边界条件排查以及工程化习惯一次讲透。适合刚开始学数据结构的读者也适合已经写了几个月C语言但总在指针上翻车的开发者。1. 拼接这个词背后的三种不同需求不要在拼接到底指什么这件事情上含糊。你翻开任何一本数据结构教材里面讲的链表合并和链表拼接并不是一回事。我见过很多同学在作业里把有序合并写成简单的尾接结果测试一跑就出错。其实需求不同代码结构完全不同先看清楚要拼什么再动手。1.1 尾接把一整条链挂到另一条链的末尾这是字面意思上的拼接链表A的尾节点指向链表B的头节点。这种操作常用于多个缓冲区、多段数据的串联比如把三个链表分别存着不同时段的日志最后一次性拼起来遍历。尾接的典型特征是B内部不需要任何改动A的尾节点从NULL变成B的头节点地址。难点只有一个找到A的尾节点。找尾节点必须从头开始遍历时间复杂度O(n)。如果频繁做尾接操作一般会额外维护一个tail指针直接把复杂度降到O(1)。这个优化思路很常见但很多人写尾接函数时都会忽略。1.2 有序合并两个有序链表按大小穿插成一条新的有序链这种操作在归并排序里用得最普遍。链表的归并排序需要一个merge函数把两个已经有序的子链表合并成一个有序链表。它和尾接最大的区别是要逐个比较节点的大小决定下一个节点取A的当前节点还是B的当前节点。很多初学者把有序合并和尾接混在一起以为先排序再接上就完事了。如果两个链表本身已经有序逐个穿插合并是O(mn)的线性时间但你先把它们尾接在一起再整体排序最差就是O((mn)log(mn))成本完全不一样——如果链表很长这个差别会很明显。搞清楚自己到底要哪种操作能省下大量无谓的排序。1.3 局部拼接把一段链表插入到指定节点之后尾接和有序合并之外还有一类场景在主链表的某个位置插入一段子链。比如一个文本编辑器的撤销链表要把一段新操作拼接在当前位置之后一个进程调度队列要把一批新任务插在某个优先级节点之后。局部拼接的难点在于两个边界插入位置为NULL说明要拼到末尾插入段为空则什么都不做。而永远是稳定的操作顺序先把子链的尾链到后段再把前段链到子链的头——这个顺序如果反过来子链会被自己吃掉产生环形引用这是局部拼接最常见的坑。下面这张表总结了三种需求的差异方便对照需求类型数据前提操作核心时间复杂度尾接无要求找A尾节点指向B头节点O(n)有序合并A、B各自有序逐节点比较大小穿插连接O(mn)局部拼接给出插入位置先链后段再接前段O(len(seg))2. 指针操作的本质拼接是在接线不是在复制理解了需求之后接下来必须搞清楚C语言链表拼接的底层原理。很多人代码写不对是因为脑子里想的是把节点搬过去但C语言链表拼接根本不搬运任何东西它只把指针的指向关系重新接一遍。形象点说链表是一串用线拴着的气球拼接做的事情是把线头解开、重新绑上气球本身没有动过。2.1 节点结构里到底存了什么先看最基础的结构定义typedef struct Node { int data; struct Node* next; } Node;每个节点由两部分组成数据域data和指针域next。next存的是下一个节点的内存地址注意是地址不是节点本身。所以当你写tail-next head_b;的时候实际发生的事情只有一件把tail节点的next字段的值改成head_b的地址。head_b指向的那个节点的内存位置不会移动节点里的data也不会变化。这个只改指针、不改数据的特性决定了链表拼接的一个巨大优点拼接操作不涉及数据拷贝。假如data是一个几百字节的结构体用数组做插入需要把后面所有元素整体后移而链表只需要改两次指针。这也是拼接类操作在工程里被大量采用的底层原因。2.2 四步接线法每一次拼接都逃不过的骨架以尾接A和B为例。假设A链有3个节点B链有2个节点要把B接在A后面。完整的指针操作可以拆成四步找到A的尾节点tail特征是tail-next NULL验证tail不为NULL否则说明A为空链把tail-next赋值为head_b的地址如果有需要把head_b置为NULL避免两个链表共享同一份头指针核心代码三行就够Node* tail head_a; while (tail-next ! NULL) { tail tail-next; } tail-next head_b;但实际工程里远没有这么简单。你要考虑head_a本身就是NULL怎么办head_b是NULL怎么办两个链表拼完之后原来的head_b变量是否还要继续使用。这些边界条件如果预先不处理指针就会在你不注意的地方悄悄越界。2.3 NULL是边界也是保护C语言里的NULL是最容易被忽视的防线。一个链表走到头靠的是检查p-next ! NULL一个函数的合法性判断靠的也是入参不为NULL。拼接操作里95%的崩溃都和NULL有关对NULL指针做while (tail-next)直接段错误返回的链表头是NULL调用方没有检查就继续遍历崩溃两个链表拼好了但忘了把旧头置NULL析构时二次释放崩溃所以我有一个习惯所有链表操作函数的第一步永远是防御检查。虽然看起来啰嗦但在联调阶段能救你很多次。尤其是那种五个条件组合出32种输入情况的工具函数防御检查写的越全后面调试越省心。3. 三份可以直接运行的实现代码讲了一堆原理现在上实际代码。我写了一个完整的演示文件包含三种拼接方式的实现、辅助打印函数和测试主函数。需要在本地复现的话直接保存成文件编译运行即可——文件名建议用英文避免某些工具链在处理中文文件名时出现意外问题。3.1 基础结构与辅助函数#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node* next; } Node; Node* create_node(int value) { Node* p (Node*)malloc(sizeof(Node)); if (p NULL) { fprintf(stderr, memory alloc failed\n); exit(1); } p-data value; p-next NULL; return p; } Node* create_list(int arr[], int n) { if (n 0) return NULL; Node* head create_node(arr[0]); Node* tail head; for (int i 1; i n; i) { tail-next create_node(arr[i]); tail tail-next; } return head; } void print_list(Node* head) { Node* p head; while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); } void free_list(Node* head) { Node* p; while (head ! NULL) { p head; head head-next; free(p); } }create_node里做了malloc失败检查打印到stderr之后直接exit。这种处理在正式工程里略显粗暴在单文件练习项目里反而是最直观的——失败就应该立刻暴露不要拖着NULL指针往下传。3.2 尾接版本appendNode* list_append(Node* head_a, Node* head_b) { if (head_a NULL) return head_b; if (head_b NULL) return head_a; Node* tail head_a; while (tail-next ! NULL) { tail tail-next; } tail-next head_b; return head_a; }注意这里返回值的处理如果A是空链直接返回B的头这样调用方不需要在函数外再写一次空链判断。我见过一些写法是不管A是否为空都往里走最后一个循环下来tail是NULL再执行tail-next直接崩溃。先把两个空链情况挡在前面代码看起来多两行但安全性完全不一样。调用方式int a[] {1, 3, 5}; int b[] {2, 4, 6}; Node* list_a create_list(a, 3); Node* list_b create_list(b, 3); Node* merged list_append(list_a, list_b); print_list(merged); // 1 - 3 - 5 - 2 - 4 - 6 - NULL free_list(merged);3.3 有序合并版本merge_sortedNode* list_merge_sorted(Node* head_a, Node* head_b) { if (head_a NULL) return head_b; if (head_b NULL) return head_a; Node dummy; dummy.next NULL; Node* tail dummy; while (head_a ! NULL head_b ! NULL) { if (head_a-data head_b-data) { tail-next head_a; head_a head_a-next; } else { tail-next head_b; head_b head_b-next; } tail tail-next; } if (head_a ! NULL) tail-next head_a; if (head_b ! NULL) tail-next head_b; return dummy.next; }这段代码最容易引起疑问的地方是dummy节点——它分配在栈上不是堆上始终留在函数栈帧内。为什么不能直接用一个Node*指针然后不断改tail tail-next因为合并的第一轮你还没确定返回的头应该是A还是B直接用空指针做起点没法连接第一个节点。dummy的作用就是充当一个不参与数据的哨兵头让每一轮比较都有统一的tail-next ...写法。等循环结束dummy.next就是真正的链表头。栈上创建的dummy在函数返回时自动销毁不需要free。有人担心返回的链表节点里会不会包含栈上的dummy地址——不会因为dummy.next指向的始终是堆上的某个原链表节点最后一次循环结束后也没有任何节点指向dummy本身。这个哨兵技巧在链表的很多操作删除、反转、合并里都能用建议务必要掌握。测试主函数int a[] {1, 3, 5}; int b[] {2, 3, 4}; Node* list_a create_list(a, 3); Node* list_b create_list(b, 3); Node* merged list_merge_sorted(list_a, list_b); print_list(merged); // 1 - 2 - 3 - 3 - 4 - 5 - NULL free_list(merged);3.4 局部拼接版本insert_segmentNode* list_insert_segment(Node* head, Node* pos, Node* seg) { if (seg NULL) return head; if (head NULL) return seg; if (pos NULL) { return list_append(head, seg); } Node* seg_tail seg; while (seg_tail-next ! NULL) { seg_tail seg_tail-next; } seg_tail-next pos-next; pos-next seg; return head; }关键在最后两行。seg_tail-next pos-next先把子链的尾接到主链插入点后面的部分pos-next seg再把pos的next指向子链头。这个顺序不能反如果先写pos-next seg那么pos后面的整段主链就脱离了接着再去遍历seg_tail你会一直遍历到原来主链的末尾seg_tail最终指向的不是子链的尾而是整个主链的尾这时候再把seg_tail-next pos-next子链段会变成环。我用一个具体例子说明A链是 10-20-30-40pos指向20seg是 21-22。正确操作后结果是 10-20-21-22-30-40。如果两步反了第一步把20-next指向21之后seg_tail会一路找到40然后把40-next指向此时已经变成21的20-next于是40后面接上了21但21已经在20后面了链中出现环遍历会死循环。这个bug在初学时非常隐蔽因为打印链表时会看到一长串重复的循环直到程序崩溃或者超时。所以局部拼接的接线顺序我建议用笔在纸上画两遍再写代码。4. 边界条件、内存归属和调试踩坑代码能跑通不等于程序是安全的。链表拼接里最折磨人的问题往往发生在看起来没啥问题的输入上。这个部分讲几个典型边界和一个完整的排查链路。4.1 空链表、自拼接和极端长度的处理空链表不是小事。函数入参中有任意一个为NULL处理方式应该是明确返回另一个链表而不是直接进入遍历逻辑。上面三份代码都做了这一层处理。自拼接则需要格外小心如果调用list_append(head, head)会发生什么A和B其实是同一条链你会先从头找到尾然后让尾-next指向头构成一个环。这不是你想要的而且这个环一旦形成几乎无法通过遍历来终止——除非建立一个访问过的标记。因此在实际工程里对链表拼接函数增加断言两个链表不是同一条链但可能有共同尾节点非常困难更务实的做法是在设计层面保证不传入同一个头指针或者在文档里明确标注这个函数不支持自拼接。还有一类边界是长链拼接。比如一个100万节点的链表做尾接从head开始逐节点找尾要遍历100万次。虽然尾接本身是O(n)但如果程序里频繁做这种操作性能瓶颈会很明显。这种情况下通常增加一个结构体链表描述符把head和tail都存进去尾接直接操作tail指针O(1)完成。这是链表工程化的一个常见改进方向。4.2 内存归属拼完之后谁负责释放链表拼接后两个链表的内存合并成一个整体。于是有问题free_list应该只释放一次还是分别释放两次答案是只释放一次。因为拼接后的链表是一条完整的链从头遍历到尾就能覆盖所有节点如果调用方再单独free掉原来的head_b就是二次释放直接崩溃。我在实际调试中遇到过一个很典型的现象程序在拼接后主流程释放了一次链表然后在某个日志清理函数里又好心释放了一次原链表B的头结果malloc报错。排查了半天才意识到B的头地址现在也是合并后大链的中间节点地址早就被释放过了。解决办法就是规定拼接函数返回后调用方的两个输入头指针都不再单独管理统一以返回值为准。如果实在需要保留原头指针的语义就在拼接前把B的所有节点复制一份深拷贝——但那是另一套方案的取舍了。4.3 一个完整的排查链路打印卡住到底是谁在作怪我遇到过的最常见的三个症状分别是程序段错误、打印内容跳节点、打印内容无限循环。这里以一个无限循环为例还原完整的排查过程。现象调用list_insert_segment之后print_list迟迟不结束终端疯狂输出一串重复的数字直到按CtrlC。第一步先确认是CPU忙转真死循环还是输出太多慢但会结束。用调试器中断进程查看调用栈发现停在print_list的printf(%d - , p-data);这一行而p指向的地址一直在重复出现。这就确认了链表有环。第二步找出环在哪里。方法是一边沿next走一边把沿途地址打印出来观察第一次出现重复地址的位置void debug_print_addresses(Node* head, int limit) { Node* p head; for (int i 0; i limit p ! NULL; i) { printf(node %d at %p, next - %p\n, i, (void*)p, (void*)p-next); p p-next; } }第三步对照插入操作的手工推导发现我犯的正是上面说的顺序错误——先改pos-next再找seg_tail导致环的产生。修复后再跑debug_print_addresses发现地址序列不再重复。这个排查过程看起来简单真正的经验在于不要一上来就怀疑调试器有问题或者机器不够快链表问题靠画图打印地址基本都能定位盲目加断点反而浪费时间。4.4 输入输出习惯对调试的影响还有一个细节很多人的链表测试数据是手动在main里逐个create_node构建的写起来特别长还容易写错。我强烈建议写一个create_list(int arr[], int n)辅助函数像上面代码那样用数组初始化链表。这样测试用例可以写得很紧凑int test1[] {1, 2, 3, 4}; int test2[] {};每次改动测试数据只需要改数组内容不需要改create_node的调用序列。这个习惯在刷题和面试准备阶段能节省大量时间。5. 测试用例设计与性能观察代码写完只是开始怎么证明它在各种输入下都没问题才是真正考验人的地方。链表拼接的测试不需要复杂的测试框架但输入组合必须覆盖全。5.1 覆盖六类典型输入我把链表拼接的核心测试组合整理成一张表照着这组用例跑一遍基本可以覆盖大部分现实的边界情况用例编号A链表B链表预期输出验证重点T11-2-3(空)1-2-3空链BT2(空)4-54-5空链AT31-231-2-3单节点链T412-31-2-3单节点AT51-23-4-51-2-3-4-5不等长T6(空)(空)(空)双空链如果是有序合并还要额外加一组乱序但各自有序的输入比如1-5-9和2-3-7确认输出严格非递减。我在测试merge_sorted时发现一个容易忽略的小问题若两个链表都含有相同数值比如1-3-5和1-3-5合并结果应该是1-1-3-3-5-5并且整个过程不产生额外的临时节点。用而不是做判断才能保证结果稳定、不丢数据。5.2 打印与释放验证每次拼接操作之后打印链表是一部分释放链表是否正常也应该纳入验证。因为程序退出前不释放链表内存泄漏在跑一次的小程序里根本看不出来但放到长时间运行的服务里就会逐渐吃满内存。最简单的方法是在free_list里加一行统计int free_list_count(Node* head) { int count 0; Node* p; while (head ! NULL) { p head; head head-next; free(p); count; } return count; }如果一个测试里create_list创建了5个节点调用free_list_count最终也返回5说明没有遗漏也没有二次释放。在正式工程里这不算追踪手段但在练习阶段能帮你逐步建立谁创建谁释放的意识。5.3 时间复杂度的实测感受尾接一个n节点和m节点的链表遍历A找尾是O(n)B不必遍历。合并且两个链表都有序耗时大约正比于mn如果先拼接再排序整体排序的耗时在数据量增大时增长得更快。我在本机测试过一组实验数据分别对1000、1万、10万个节点做尾接和有序合并尾接需要遍历A的全部节点有序合并需要同时推进两个链表两者都基本呈线性增长但有序合并常数更大因为每个节点都要比较大小。这种复杂度观察的意义不在于精确到微秒而在于建立数据结构操作成本的直觉。接下来面试里面试官问合并两个链表的时间复杂度时你能直接给出O(mn)并解释为什么不能更快——因为每个节点至少要访问一次才能确定它在结果链中的位置。6. 从链表拼接.c到工程级代码的习惯进阶一个命名为链表拼接.c的单文件本质上是练习代码。但练习代码写得好不好会直接影响你在真实项目里写链表代码的水平。这个章节谈谈从临时文件走向工程代码的几个升级方向。6.1 接口设计返回头指针还是返回描述符基础版的拼接函数直接返回链表头节点指针简单直观。到了工程里链表往往带长度字段、尾指针字段甚至带一个互斥锁。这时候函数签名会变成List* list_append(List* dst, List* src);返回List而不再是Node。好处是拼接后可以同步更新len字段坏处是接口变重所有调用点都得改成描述符操作。我见过一个中型项目里两种风格来回切换导致同一个链表的某些接口传Node*、某些接口传List*非常混乱。所以选择哪一种风格不重要重要的是在项目内部保持一致。从链表拼接.c这种单文件开始我的建议是把Node操作和List操作分层。底层提供操作Node的裸函数append、insert、merge上层提供带语义校验的List封装。这样练习代码的天花板和控制力都被保留工程可用性也兼顾了。6.2 防御式编程入参校验不只是加个if入参校验不是每个函数开头堆三个if就完事。关键是校验的粒度和提示信息要有意义。例如if (head NULL) { fprintf(stderr, append: head_a is NULL, return head_b\n); return head_b; }有日志的输出和默默退出是两种调试体验。尤其是线上程序冷冰冰的段错误远不如一条带函数名的stderr提示信息有用。但注意日志别打得太啰嗦——正常路径不需要日志只在异常分支打才不会污染输出。另一个防御习惯是使用const。像print_list的入参明明不修改链表就应该写成void print_list(const Node* head);这样任何误操作在编译阶段就会被拦下来比运行期段错误早得多。修改指针指向的节点内容时编译器也会给出明确警告这是C语言里最容易被忽视的内置防护。我在review自己早期的代码时经常发现const标注不完善的地方往往是bug最多的地方。6.3 扩展方向双向链表拼接、循环链表拼接、深拷贝单向链表的拼接讲完后有两个扩展方向值得尝试。第一个是双向链表拼接。注意点比单向多一个除了修改next还要同步修改prev。尾接两个双向链表时A尾的next指向B头B头的prev指向A尾插入中间段时前后四个方向的指针都要正确连接。一个常见的错误是修改了next之后忘了更新prev导致反向遍历时跳到错误的节点。第二个是循环链表的拼接。循环链表没有NULL节点找尾节点不能再用while (p-next ! NULL)而是判断p-next head。拼接时还要额外处理头尾相接边界比普通链表多一层复杂度。如果对链表的理解还不够扎实建议先用画图方式走通再动代码。第三个是深拷贝版本。有时候不能把B链直接接到A上因为B还要独立使用或者两侧的生命周期不同步。这时候要做的是遍历B在堆上重建一整条与B等值的链再接过去。实现代码并不复杂但最容易错的是深拷贝时把新节点的next误点返回原节点的next新旧链交错在一起释放时炸得一片狼藉。我自己的经验是深拷贝完毕后及时free原链的临时头指针并且对原链和新链分别做一次释放测试能更快发现这类交错。6.4 写在代码注释里的经验最后分享一个小的注释习惯。我一般在链表拼接这类稍复杂的函数顶部写一段注释说明三个问题这个函数做什么、参数分别是什么语义、调用方负责什么。例如/* * list_append: 将 head_b 指向的链表整体接到 head_a 的末尾。 * 返回值为拼接后的链表头。 * 注意拼接后 head_b 的内存归属由新链表统一管理 * 调用方不得再单独释放 head_b。 */这段注释不算长但能在两周后再次翻看代码时节省大量时间。有经验的程序员看一个函数的第一件事不是读实现是读注释里关于内存归属和边界条件的说明。如果每个函数都有这类注释即使项目文件仍然叫链表拼接.c它的水平也已经不是练习代码而是可以给别人复用的工具模块了。链表拼接这个主题往深了说可以延伸出链表翻转、环检测、跳表等一堆话题但万变不离其宗指针操作的本质是明确所有节点之间的指向关系并保证变更过程中的每个中间状态都可解释、可跟踪。写完这一整个文件之后我自己最大的体会是头铁的遍历远不如一张画清楚的节点关系图更可靠。特别是遇到局部插入这种接线顺序问题先在纸上画出四个节点在两轮赋值之后的指向情况再写代码几乎不可能再写出环形链。希望你调试链表拼接时也试试这种先画图再写代码的方式它会让你少走很多弯路。
阅读完成 · 觉得有帮助？
