1. 练习72到底在考什么从“存数据”到“串数据”先问个问题你在刷菜鸟教程C经典100例的时候是不是也在第72题卡过这道题的题目原文只有简简单单一句话“创建一个链表”但真正动手写的时候你才会发现它几乎是整套100例里第一个要把结构体、指针、动态内存分配、循环、函数返回值这些东西全部串起来的题目。前面71道题大多还是数值计算、数组操作、字符串处理你还能靠“数组下标”的思维混过去到了链表这里你被迫换一种思维方式数据不再连续放在一整块内存里而是靠指针一个一个“串”起来。这道题在经典的题目编排里是名副其实的分水岭。我刚学C语言的时候也正好卡在这一题上卡了挺长时间。当时我参考的代码能跑通但看不懂为什么那样写更不知道自己改一改会不会崩。后来我把这段代码拆开、画图、用调试器一步一步跟才发现链表表面上只是多了个next指针实际上背后牵扯到的内存模型、结构体定义、指针移动每一个都是独立的坎。所以这次我决定把练习72完整拆开讲一遍题目到底考什么、代码每一步为什么那样写、容易踩的坑有哪些以及做完之后应该怎么继续往下练。你如果正打算刷这道题或者刷到一半有点迷糊这篇文章可以帮你少走很多弯路。我建议先把代码扔一边跟着思路走一遍“为什么要这么写”再回来看代码很多地方会一下通透。1.1 题目很短但它是C语言基础的分水岭在经典100例的编排里练习72的位置很讲究。练习66到练习71分别练了三个数排序、数组元素交换、数组循环移动、约瑟夫环问题、字符串长度统计、大小写转换。这些题有个共同点它们操作的数据规模在写代码时就已经确定了。要对10个数排序就开一个int a[10]要统计字符就开一个足够大的char数组。这种思路本身没有问题但它的天花板很明显——数组的大小必须在编译前定死一旦运行起来发现数据不够用你没有任何办法现场“再多加几个格子”。链表解决的正是这个问题。它允许你在程序运行的过程中按需向系统申请内存来一个数据就申请一个节点不需要数据了就把节点释放掉。这种数据结构的核心不再只是“存储”而是“组织”——每个节点除了保存数据本身还必须保存下一个节点的位置。这就解释了为什么练习72要求“创建一个链表”而不是让你用数组模拟一个链表它要让你第一次真正接触动态数据结构。我建议你在刷这道题之前先把结构体基础补齐。至少要知道struct怎么定义、怎么用typedef取别名、怎么访问结构体成员同时要分清楚“结构体变量”和“结构体指针”的区别。如果这两块还不太熟不用急先回前面几道结构体题目练几下再来碰链表会顺手很多。链表正是结构体、指针、动态内存这几个C语言核心概念第一次组合起来的地方前面的基础没打牢后面会越学越痛苦。1.2 数组和链表两种完全不同的组织方式很多人第一次接触链表时最大的困惑是我明明有数组了为什么还需要链表这里可以用一个生活化的例子来理解。数组就像电影院的一排连座座位在买票时就已经定死了你想临时加一把椅子很困难因为这一排的位置是固定的。链表则像一群人在玩“每个人只告诉我下一个人的联系方式”的游戏第一个人只告诉你第二个人的联系方式第二个人只告诉你第三个的依此类推。你要找第100个人就得从第一个人开始一个一个问下去。但链表有一个天大的好处——你随时可以在队伍里加一个人只需要改一改前后两个人的联系方式就行。正因为这样数组和链表的适用场景完全不同。数组适合“数据规模已知、经常按下标访问”的场景链表适合“规模不确定、频繁插入删除数据”的场景。练习72做的只是第一步创建一个链表让你亲眼看到数据是怎么被动态串起来的。后面你再继续刷题就会发现插入、删除、反转、合并这些操作全都建立在这个基础之上。这个差异想明白之后你再看练习72关注点就不会只放在“怎么把代码跑通”而会去想“链表这个结构怎样设计才合理”。比如为什么要有头节点为什么要尾插新节点创建之后要不要初始化next这些问题才是这道题真正想让你琢磨的东西。我见过不少人一口气把100例往后刷到了第72题就照着答案敲一遍过了但问他“为什么要tail p”答不上来。那就等于白刷了后面遇到反转链表、合并链表照样两眼一抹黑。1.3 这道题真正要掌握的是五个知识点如果只把练习72当成一个“照着敲一遍就能过”的题目那就太可惜了。这道题其实由五个小的知识点组成缺一个都跑不起来。我列成一张表你可以逐项自查考点具体内容如果不会的后果结构体自引用struct成员指向自身类型必须是指针编译报错或无限递归定义动态内存分配用malloc申请节点内存用free释放段错误、内存泄漏指针操作通过p-next访问和修改下一个节点链表串不起来尾插法新节点总是接到链表末尾数据顺序错乱链表遍历从头节点开始通过next逐个访问打印不全或死循环你拿这张表对照一下自己通常会发现欠缺的地方就集中在某一个具体点上。有人是结构体定义一直报错有人是malloc返回值没强转导致编译警告还有人是在循环里把tail的更新写反了。这些坑我在后面都会展开讲。这张表里的每一项都弄明白练习72才算真正拿下而不是“代码能跑就行”。2. 动手前必须弄懂的三块基石结构体、内存、尾插2.1 自引用结构体为什么next必须是指针创建链表的第一个动作是定义“节点”这个结构体。在C语言里结构体成员可以是任意类型甚至可以是这个结构体自身的指针。代码很直白typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;这里有一个新手很容易踩的坑为什么成员不能写成struct LNode next而必须是struct LNode *next原因很简单。如果成员是结构体变量那这个结构体内部又包含一个完整的一模一样的结构体那个结构体里又包含下一个无穷无尽编译器根本没法计算这个结构体到底占多少字节。而指针就不同了指针在64位系统上固定占8个字节编译器知道它的大小可以正常完成定义。所以“自引用”在这个场景下必须是“指向自己的指针”而不是“一个自己”。还有一个细节值得留意在结构体内部next成员必须写成struct LNode *next而不是直接写LNode *next。因为typedef出来的别名LNode要等结构体定义结束之后才生效你在结构体内部用LNode *next编译器还没见过LNode这个名字就会报“unknown type name”的错误。当然你也可以用另一种写法先typedef声明再定义结构体typedef struct LNode LNode; struct LNode { int data; LNode *next; };这样写也能让LNode在结构体内部可见但在初学阶段我建议你直接用第一种写法就好最不容易绕晕。在实际使用中我更喜欢直接用LNode *而不是LinkList来声明变量。因为LinkList看起来像是“链表类型”但实质上它只是个指针容易让人误以为它是一个结构体变量。LNode *则能明确告诉你“这是一个指向节点结构体的指针”。两种写法都能编译通过关键是别在一个函数里一会儿LNode *一会儿LinkList把指针和结构体混为一谈。2.2 malloc申请节点内存free还回去创建链表节点的标准动作是LNode *p (LNode *)malloc(sizeof(LNode)); if (p NULL) { // 处理失败 }malloc是一个比较“底层”的接口它接收的参数是多少个字节返回的是一段连续可用内存的首地址。既然返回的是地址那它本质上就是一个指针。这里有两个经常出问题的地方要重点说。第一sizeof里到底写什么我们要申请的是一个节点的大小应该写sizeof(LNode)意思是“够放一个struct LNode的空间”而不是sizeof(LNode *)。后者是“一个指针变量占用的字节数”在64位系统上只有8个字节远不够装下data和next两个成员。写错了可能不会立刻崩溃但一旦访问p-next就会踩到别的内存头上属于最隐蔽的bug。第二malloc返回的void *需不需要强制转换。C语言里void *可以隐式转换成任意类型的指针所以LNode *p malloc(sizeof(LNode))也是合法的。但很多教程还是习惯写成(LNode *)malloc(...)好处有两个一是读者一眼能看出你打算把这块内存当什么类型用二是把代码放到C编译器里也能通过因为C不允许void *隐式转换。两种写法都行看你自己环境不过我会在代码里保留强转减少编译器的兼容问题。内存泄漏是另一个必须从一开始就养成习惯的问题。每次malloc申请的内存程序不会自动还回去必须你主动调用free。链表这种结构特别容易泄漏因为你在循环里申请了一堆节点如果只释放了头节点后面的节点就再也找不到了。一个比较稳妥的习惯是写创建函数之前先想好对应的销毁函数怎么写。不要等到程序跑完发现内存占用越来越高才回头找哪里漏了。如果条件允许可以安装Valgrind一类的内存检测工具专门检查“分配了多少内存、释放了多少内存”。运行一次它就会告诉你哪一行malloc的内存没有free。现在很多在线编译网站也有类似的内存检测功能练题的时候顺手加一道检查能帮你省很多排查功夫。2.3 头节点和尾插法两个容易被忽略的设计决定设计单链表时第一个问题是到底要不要“头节点”。所谓头节点就是一个额外的、不保存实际数据的节点但它永远站在链表的最前面。我给出的参考实现带了头节点原因是它能省掉大量边界处理。举个例子。假如要在链表头部插入一个新节点不带头节点时新节点就变成了新的头这会导致函数外面的头指针变量需要更新。而如果函数通过传值方式接收头指针它就永远改不了函数外面那个指针——这就是为什么有时候需要传二级指针LNode **。带头节点就没有这个烦恼新节点永远插在head的后面头节点本身的位置不变函数外面的head指针也不用改。对于刚学链表的同学来说这个设计能让你少想很多“头指针变了怎么办”的问题。第二个问题是怎么把新节点接到链表末尾。尾插法的核心是三句话p-next NULL; tail-next p; tail p;第一句保证新节点是一个干净的“尾节点”第二句把它挂到当前链表最后一个节点的后面第三句非常重要把tail指针指向这个新节点让它成为新的最后一个节点。如果漏掉第三句下一次循环时新节点又会挂到原来那个“旧尾巴”的后面结果是旧尾巴的next被覆盖链表中间直接断掉。很多新手输出链表时发现只显示一个节点大多数就是这个原因。我用一句话总结这三个变量的分工head是锚点永远站在最前面不动tail是队尾指针记录最后一个节点在哪p是每一次新来的节点带着数据准备入队。每次循环做的事情就是“让新节点入队然后更新队尾指针”。你把这个口诀记在脑子里后面再写链表插入、删除思路都会清晰很多。3. 完整代码实现与逐段解读3.1 一个可运行的基础版本含防错和释放为了让你直接对照实践我提供一个完整版本。它基于菜鸟教程C经典100例中练习72的原始思路在参考代码的基础上做了三处补充一是malloc之后判断返回值二是中途分配失败时把前面已分配的节点全部释放再返回三是增加了一个销毁链表的函数避免程序退出时内存泄漏。你把它保存成list.c直接编译就能运行。#include stdio.h #include stdlib.h typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList; // 创建链表返回带头节点的链表头指针失败返回NULL LinkList CreateList(int n) { LNode *head, *tail, *p; int i; head (LNode *)malloc(sizeof(LNode)); if (head NULL) { printf(头节点分配失败\n); return NULL; } head-next NULL; tail head; for (i 1; i n; i) { p (LNode *)malloc(sizeof(LNode)); if (p NULL) { LNode *cur head; LNode *nxt; printf(第%d个节点分配失败\n, i); while (cur ! NULL) { nxt cur-next; free(cur); cur nxt; } return NULL; } printf(请输入第%d个元素的值: , i); scanf(%d, p-data); p-next NULL; tail-next p; tail p; } return head; } // 遍历链表并打印 void PrintList(LinkList head) { LNode *p; if (head NULL) { return; } p head-next; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 销毁链表释放所有节点 void DestroyList(LinkList head) { LNode *p head; LNode *q; while (p ! NULL) { q p-next; free(p); p q; } } int main() { int n; LinkList head NULL; printf(请输入链表节点个数: ); scanf(%d, n); head CreateList(n); if (head NULL) { printf(链表创建失败\n); return 1; } printf(刚建立的链表为: ); PrintList(head); DestroyList(head); head NULL; return 0; }这段代码可能比你之前看到的参考版本长一点但多出来的部分都不是多余的。判空是为了不让程序在内存不足时直接段错误销毁函数是保证程序退出前把堆内存还回去。等你把链表操作练熟了这两个函数会变成你写所有链表程序的基础很多链表相关的OJ题也需要你自己写释放逻辑提前养成习惯不吃亏。3.2 创建链表时指针是这样一步步移动的光看懂代码还不够强烈建议你在纸上把指针的指向画一遍。下面以输入n3依次输入10、20、30为例画出每一步的关键状态。初始化时head申请出来head-next NULLtail head。此时链表结构是headdata未初始化next指向NULLtail和head指向同一个地方。这里head的data值没有被初始化但你不会去读它因为遍历链表时总是从head-next开始所以没有问题。第一次循环p保存新节点的地址。新节点的data10nextNULL。执行tail-next p后head-next指向了这个新节点。再执行tail ptail从head移到了这个新节点。此时链表head - 节点10 - NULLtail指向节点10。第二次循环再创建一个新节点data20。tail目前指向节点10所以tail-next p这一步是把节点10的next从NULL改成指向节点20。tail p后tail指向节点20。链表变成head - 节点10 - 节点20 - NULL。第三次循环同理最后链表是head - 节点10 - 节点20 - 节点30 - NULL。你会发现一个规律tail始终指向“当前最后一个节点”新节点总是接在tail后面然后tail更新为新节点。这个过程和排队很像新来的人永远站在队伍末尾队尾标志跟着最后一个人走。只要记住“tail是队尾指针”这个循环就不会写错。打印函数PrintList相对简单。它先取head-next跳过头节点然后用while循环顺着next指针一路走边走边打印data直到p变成NULL。注意循环条件是p ! NULL如果写成p-next ! NULL最后一个节点就漏掉了。这里用while而不是do-while也很讲究链表长度事先未知而且完全可能是空链表所以要先判断“当前有没有节点”而不是“先做一次再说”。你要是用do-while遇到空链表时就会访问空指针这就是为什么遍历链表几乎都用while。3.3 编译运行与输入输出实测如果你用的是Linux或macOS在终端里编译运行非常直接。把代码保存成list.c然后执行gcc list.c -o list ./list程序会先让你输入节点个数比如输入3回车然后依次让你输入第1个元素的值、第2个元素的值、第3个元素的值。全部输入完屏幕上会打印出“刚建立的链表为: 10 20 30”这样的结果。如果你的机器上没有gcc先用包管理器把编译器装上或者直接用VS Code加C/C插件也一样能编译。如果你用Windows下的Dev-C或者Visual Studio操作更简单新建一个C源文件把代码粘贴进去点“编译运行”按钮就行。这里提醒一句scanf输入数据时数字之间用空格或者回车隔开都可以因为%d格式会自动跳过空白字符但如果你输入了字母scanf会返回0而不是读取成功后续的循环就可能不断提示你输入。这时候按下CtrlC重新运行别跟它较劲。还有一个小经验代码里的printf提示语尽量写得明确一点比如“请输入第3个元素的值:”而不是笼统的“请输入:”。链表创建过程中节点一多提示不清非常容易输错序号。调试程序时printf就是你的眼睛这点细节能帮你省不少时间。现在很多同学习惯用在线编译器刷题我建议你至少在这道题上回到本地环境跑一次因为后面你要用调试器在线网页很难做到单步观察内存。4. 常见错误与调试三板斧4.1 五个高频错误症状和修复对照表我帮不少学弟学妹改过这道题的代码总结下来新手翻车大多集中在下面几种情况你对着检查症状原因修复办法编译报错unknown type name LNodetypedef还没生效前结构体内部用了别名LNode结构体内部的next成员写成struct LNode *next运行崩溃提示段错误malloc返回NULL后没有判断或head为NULL就访问head-nextmalloc后判空对函数返回值统一判空只打印出第一个元素循环里漏写了tail p新节点没接到队尾补上tail p并检查更新位置打印时死循环遍历时p没有往前走while(p ! NULL)内写p p-nextfree时报错或程序挂掉sizeof写成了sizeof(LNode *)或者free了栈变量sizeof写节点类型只free malloc出来的地址场景一和场景二在初学链表时几乎每个人都会遇到。场景三则是逻辑错属于最典型的“代码不报错但结果错”调试起来反而比编译报错更花时间。我自己的习惯是一旦发现结果不对先打印tail指针看看它到底指向哪里再决定从哪一步开始查。如果tail始终不变一定有个地方忘了更新如果tail指向了某个奇怪的地址那可能是malloc越界或者节点没初始化。场景五要特别提醒地址对齐和强制转换有时候也会产生free失败的诡异情况但大多数时候就是“释放了不该释放的东西”。比如你把free(p)写在了p p-next之后那释放的就是下一个节点而不是当前节点链表顺序直接乱套。释放节点一定要先保存next再free当前指针。这个顺序问题毁掉过很多人一下午的时间。4.2 用GDB看着链表长出来如果你以前没接触过GDB这道题值得你开一次头。GDB可以让你在程序运行到一半时停下来一屏一屏地看内存和指针比靠printf猜靠谱太多。步骤很简单编译时加上调试信息再启动GDBgcc -g -o list list.c gdb ./list进入GDB后先给CreateList函数下个断点(gdb) b CreateList (gdb) r程序会在进入CreateList时停下来。接着用n单步执行执行几行后用p命令查看指针内容(gdb) p head $1 (LNode *) 0x1a26010 (gdb) p *head $2 {data 0, next 0x0}p *head会把这个节点内部两个成员的值都打印出来data目前是未初始化的随机值next是NULL。当你执行完tail-next p、tail p之后再用p tail-next、p *tail就能看到next指针指向了新节点data也变成了你输入的数字。这样一步一步看下来链表是怎么“长”出来的会比任何文字解释都直观。一个实用的小技巧是用display命令让GDB每次停下时自动打印tail指向的内容(gdb) display *tail这样你每次n单步执行后GDB都会自动刷新tail的值。你很快就会发现tail从head逐渐移到节点10、节点20上整个过程一目了然。需要注意当程序执行到scanf那一行时GDB会在当前终端等待你输入节点数据你正常敲数字回车就行不用管调试器是不是在“运行”状态。我当年第一次用GDB调链表看到head、tail、p三个指针的地址在各个循环里依次变化时才真正理解了“指针变量也是变量只是它的值是地址”这句话。如果你从来没在调试器里看过链表强烈建议试试这个习惯能让你以后在数据结构上少走太多弯路。4.3 不用GDB时手绘和printf也能定位如果暂时还不想学GDB也有两个土办法简单直接。第一个是手绘找一个本子把每个变量名都当成一个小盒子每执行一步就更新盒子里的内容。比如head盒子里存一个内存地址旁边画一个箭头指向它指向的节点节点上再标上data和next的内容。画图慢是慢一点但图文一对比漏掉哪位数的毛病马上暴露。第二个是打印法。在关键位置插入临时printf例如循环内部加入printf(i%d, p%p, tail%p, tail-next%p\n, i, (void *)p, (void *)tail, (void *)(tail-next));注意printf里的%p要求参数是void *所以前面需要加(void *)强转。跑一遍你会看到每次循环tail-next都从NULL被改成了p然后tail也跟着移到p上面。如果发现某一次循环里tail-next没有变化说明tail没有正确更新当场就能定位。打印法虽然笨但在没有图形界面、没有集成调试器的时候它就是最可靠的定位手段。有一点要提醒打印法定位完问题之后记得把那些临时的printf注释掉或删掉不要让它们留在最终代码里。不是说不能留而是输出一多会干扰你观察真正重要的信息。我自己的习惯是调试代码用统一的调试宏或者加上XXX_DEBUG之类的标记最后全文搜索一下全部删掉。5. 做完这道题之后怎么进阶5.1 三个变形练习建议全部写一遍练习72完成之后证明你基本理解了“节点-指针-遍历”这条链路。但我还是要说这道题只是链表的“第一课”。真正要会用建议在它的基础上至少做三个变形。第一个变形把尾插法改成头插法。逻辑很简单新节点不再接到tail后面而是总是插在head的后面p-next head-next; head-next p;。你会发现一个有趣的现象输入顺序和输出顺序是反的。为什么反因为后输入的数据总是排在前面。这个小修改能帮你理解头节点到底起了什么作用也会让你体会到同样的代码结构只要调整一行连接顺序行为就完全不一样。第二个变形去掉头节点改成“空链表用NULL表示”。这时CreateList的返回值就不再是固定的头节点地址而是第一个数据节点的地址所以每次插入都可能要修改函数外面的头指针。你需要学会用LNode **参数或者直接返回新的头节点。这个变形是在为后续的删除、插入操作打基础因为很多操作都需要考虑“头指针可能变化”这件事。我记得自己当年第一次不用头节点写链表各种段错误频出直接加深了对传值和传地址的理解。第三个变形创建一个“按从小到大排序”的有序链表。每来一个新节点先从头节点的next开始遍历找到第一个节点a满足“a的data小于新节点data且a的下一个节点data大于等于新节点data”就把新节点插到a后面。这道题把“创建”和“插入”结合起来了难度比练习72高一个台阶。如果觉得难可以先从“删除指定值的节点”这种简单操作练起再回来做有序插入。5.2 两道经典的单链表题等你把上面的变形都写完就可以去接触真正经典的单链表算法题了。我个人推荐两道一道简单一道中等。第一道是反转链表。核心思路是准备三个指针prev、cur、next从头开始把每个节点的next反过来指向前一个节点。这道题会让你重新思考“next指针只是保存位置”的含义也会让你更熟悉指针移动的顺序。注意别把next指向的地址搞丢否则剩下的链表就找不回来了。很多人在反转链表时卡住就是因为没有提前保存下一个节点的地址结果原链表断成两截。第二道是合并两个有序链表。给你两个已经排好序的链表要你合并成一个仍然有序的链表。这道题通常用两个指针分别指向两个链表头部谁小谁就接进结果链表然后对应指针后移一位。写的时候要注意处理“其中一个链表提前走完”的边界情况。它很考验你对链尾和NULL的判断也能让你感受到“哨兵节点”在链表操作中的价值。这两道题在LeetCode上分别是206和21很多面试也都会直接考。做完之后你对单链表的理解基本就过关了。如果还有余力可以看看“链表是否有环”“环的入口在哪”这一组问题它会用到快慢指针又是另一种思维训练。刷这些题时你可以回头想想练习72里那张链表是怎么建立的你会发现所有链表题的本质无非就是“改next指向”和“注意别丢节点”。5.3 给新手的几点学习建议第一别背代码背节奏。我发现很多同学刷题的方式是看一遍答案然后默写默写十遍过两天照样忘。正确的节奏是看懂思路合上答案自己在纸上画链表图然后一步步写出代码卡住了再看答案找到卡住的那一步搞清楚为什么再继续。全程不要开复制粘贴让手写出那种“指针到底怎么指”的感觉。第二把内存图和指针图当成命根子。链表里所有的bug都可以在那个“盒子与箭头”图里找出来。宁可花半小时画图也不要花十分钟瞎猜。遇到段错误先画一下哪一步访问了空指针遇到死循环先画一下哪个节点永远走不到。很多同学总觉得画图麻烦其实它是最省时间的排错方式。我在带人学链表时会强制要求先画图再写代码坚持下来的人普遍学得比埋头苦干的快。第三务必学会一个调试工具。GDB、VS的调试器、CLion的调试都行。会设断点、会看变量、会单步执行这三板斧就够用很久。链表题是练习调试的最佳材料因为它的状态藏在看不见的堆内存里只有调试器能让你“看见”它。你如果只会printf也能调但效率低不少尤其是节点多起来之后屏幕刷得飞快根本看不清楚。最后再分享一个我自己的感受。当年我做完练习72觉得链表不过如此结果后面刷反转链表时又卡了两小时原因就是纸上画图时漏了保存next。后来我把这道题重新用三种方法写了一遍——尾插、头插、不带头节点——每种都故意写错一次再调试才真正把指针在内存里移动的感觉建立起来。所以我不太提倡顺着100例一路往后赶遇到链表这种关键节点宁可慢一点。你如果能像我一样把第72题在纸上、在调试器里反复折腾三五遍后面再遇到复杂的链表题都会稳很多。这是我个人练下来最值的一题也建议你认真对待它。