尧图网页设计 
我第一次学数据结构时被数组的“连续存储”绕进去了明明数组已经能存数据、能按下标访问为什么还要搞一个结构体套结构体的单向链表后来真正在C语言里手写了链表才明白数组的“连续”既是优势也是枷锁。这篇内容就来聊聊单向链表的上半部分从结点结构、建表、遍历到查找和销毁把最简单也最容易踩坑的细节讲透。不管你是正在复习数据结构期末、准备考研408还是刚开始学一门语言的底层容器这篇都适合先收藏再对照代码敲一遍。1. 为什么学链表前必须先搞懂结点和指针——从数组的局限说起1.1 数组的“连续”是优点也是枷锁数组在内存里是一块连续空间元素按下标依次排开。访问第i个元素时编译器只需要用“基地址 i * 元素大小”就能算出来时间复杂度是O(1)这是数组最大的优点。但同样因为连续数组的插入和删除操作非常痛苦想让一个元素插到数组中间意味着它后面的所有元素都得整体后移。我在自己写的学生管理系统里试过频繁插入删除时光看数据搬移的代码就头皮发麻。数组扩容更麻烦扩容一次基本等于重新申请内存再拷贝整个数组这个开销在数据量大了以后极其吓人。链表就是冲着这两个痛点来的它不要求元素在物理内存上连续每个结点存放数据之外再额外记录下一个结点的地址。这样插入和删除只需要改指针不需要搬动任何元素。代价是按下标直接访问的能力没了要找第k个结点必须从头指针出发顺着指针一个个走时间复杂度退化到O(n)。所以数据结构的核心取舍就一句话你想把代价花在“访问”上还是花在“增删”上。1.2 链表的“物理离散逻辑连续”单向链表里的每个结点通常包含两部分数据域和指针域。数据域存你自己要保存的数据指针域存的是“下一个结点在哪里”。一连串结点通过这个next指针串起来就形成了逻辑上的线性表。刚接触链表的人最容易出现的一个误区是以为“逻辑连续”等于“物理连续”。实际上链表结点可能分配在内存的各个角落一个结点的地址可能是0x7f...下一个结点可能完全不在相邻地址。这种“离散存储指针串联”的模式才是链表区别于数组的本质。我用一个生活化的类比说明数组像一列硬座车厢座位编号固定你只能按编号坐想加一个人必须让一排人挪位置链表像一摞写着地址的纸条每张纸条上写着自己的内容还写着下一张纸条放在哪儿你只要顺着地址找就能把所有纸条按顺序看完中间想插入一张新纸条只需要改一下前后两张的地址。1.3 从“内存块思维”切换到“结点指针思维”很多教材上来就给你一个链表的结构体定义然后就讲插入删除初学者往往看懂了代码却不知道为什么要这么写。关键障碍在于思维方式没切换过来。数组思维是“内存块”我把一整块空间视作一个大容器数据是容器里的格子。链表思维是“结点指针”每个数据单元是独立的数据之间的“连接关系”本身就是数据的一部分。在单向链表里next指针就是串联起所有结点的“胶水”。你写链表代码时脑子里不应该是一幅完整的内存地图而应该是一串动态的、不断变化的结点关系图。这个思维转变非常重要因为后面所有的链表操作本质上都是在处理“谁指向谁”的问题。头插法改变的是头指针和原首结点之间的指向关系删除结点改变的是前驱结点next指针的目标地址。你把这个逻辑想通了链表题基本就通了一半。2. 单向链表的核心结构结点并非“数据地址”那么简单2.1 C语言里的标准结点定义我用的C语言版本是国内教材最常见的写法#include stdio.h #include stdlib.h typedef int ElemType; // 数据域类型便于日后扩展 typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域指向下一个结点 } LNode, *LinkList;这里有个新手必问的问题为什么next的类型是struct LNode *而不是LNode *因为在这个结构体内部还处于定义过程中编译器还不知道LNode这个typedef别名已经生效所以只能写完整的struct LNode *。这种“自己指向自己”的结构在数据结构里叫自引用结构是构成各种链式结构的基础。我把数据域类型定义成ElemType而不是直接用int也是给自己留退路。今天用int测试明天想存学生信息、字符串只需要把ElemType改成对应的结构体类型链表逻辑完全不动。这种封装习惯在实际项目中太重要了。2.2 头指针和头结点一字之差天壤之别这是链表里最经典的混淆点。我一直建议初学者先刻两条定义在脑子里头指针是指向链表中第一个结点的指针它本身只是一个指针变量用来定位链表的起点。头结点是额外增加的一个“哨兵”结点它位于第一个实际数据结点之前data域通常不存数据next指向真正的首结点。为什么很多教材都在链表头部加一个头结点主要为了方便统一操作。如果没有头结点在第一个位置插入结点或者删除第一个结点时必须修改头指针的值有了头结点以后头指针永远指向固定存在的头结点插入和删除的逻辑就不需要单独判断“是不是第一个结点”代码能少写很多if。我用一个表格对比一下带不带头结点的区别操作场景无头结点带头结点空链表表示头指针为NULL头指针指向一个next为NULL的结点首结点插入必须特殊处理更新头指针和普通位置插入逻辑一致删除首结点必须特殊处理更新头指针和普通位置删除逻辑一致遍历判断条件从头指针开始循环从头结点next开始循环我在实战里通常选择带头结点的链表除非题目明确要求不带头结点。考研题里两种都可能出现所以两个版本你都得会写但理解上先以带头结点为主写起来没那么容易出错。2.3 为什么创建链表要用二级指针这也是一个高频迷惑点。如果你写了一个函数想在函数内部通过头插法创建链表并修改外部头指针那就必须传入头指针的地址也就是二级指针LinkList *L。比如void CreateListHead(LinkList *L, int n) { *L (LinkList)malloc(sizeof(LNode)); (*L)-next NULL; // ... 插入结点 }为什么不能直接传LinkList L因为C语言函数的传参是值传递你传进去的L是外部头指针的一个拷贝。在这个拷贝身上赋值函数结束之后外部头指针还是原来的值。经典的错误写法是void WrongInit(LinkList L) { L (LinkList)malloc(sizeof(LNode)); L-next NULL; }然后调用时LinkList L; WrongInit(L);最后L不是NULL就是野指针。除非你让函数返回新的头指针用L CreateListHead();这种方式否则就必须用二级指针。很多同学在链表操作上头疼根源就在这个“指针传值”的细节上。3. 手写一个最小可用的单向链表头插法和尾插法的取舍3.1 先写一个创建头结点的函数无论头插还是尾插第一步都是先申请头结点让头指针有地方可指LinkList InitList() { LinkList L (LinkList)malloc(sizeof(LNode)); if (L NULL) { return NULL; } L-next NULL; return L; }很多人懒得判断malloc返回值直接往下写这在小练习里通常没问题但一旦内存耗尽返回NULL代码就会直接操作空指针崩溃。判断返回值这个习惯从今天开始养成后面学树、图都会受益。3.2 头插法代码简单但结果顺序是反的头插法的核心逻辑新结点每次都插在头结点的后面成为新的首结点。void ListHeadInsert(LinkList L, ElemType x) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data x; s-next L-next; // 新结点先连上原来的首结点 L-next s; // 头结点再指向新结点 }这段代码虽然短但两行赋值顺序不能反过来。如果先写L-next s;原链表在后面的结点就丢失了因为s-next还指向NULL。每次插入新的都会放到最前面所以头插法建表得到的链表顺序和你输入数据的顺序正好相反。一个典型的应用场景就是构建“倒序”链表。比如我要实现一个栈式后进先出的效果头插法非常顺手。头插法还因为插入位置固定时间复杂度是O(1)不用担心遍历链表找尾部。缺点是当你希望链表保持输入顺序时必须最后再反转一次得不偿失。3.3 尾插法保留输入顺序但需要一个尾指针如果希望建表后链表的顺序和输入顺序一致那就用尾插法void ListTailInsert(LinkList L, ElemType x) { LNode *tail L; while (tail-next ! NULL) { tail tail-next; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data x; s-next NULL; tail-next s; }这个版本每次都要从头遍历到尾部建表的时间复杂度是O(n²)数据量大时明显变慢。更常见的优化是维护一个尾指针在创建过程中始终指向最后一个结点void ListTailInsertFast(LinkList L, ElemType x, LNode **tail) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data x; s-next NULL; (*tail)-next s; (*tail) s; }这个函数同样需要二级指针来更新外部尾指针。我实际写项目时更愿意定义一个“链表结构体”里面同时保存头指针和尾指针typedef struct { LNode *head; LNode *tail; } LinkedList;这样头插、尾插都不需要二级指针代码可读性高很多只是考研408的代码题通常还是用传统的LinkList表示法所以课内功课还是得适应老写法。3.4 两种建表方式的实验对比我自己用一组数字1 2 3 4 5分别做头插和尾插打印结果头插法最终链表5 4 3 2 1尾插法最终链表1 2 3 4 5所以做题时题目要求输出顺序和输入顺序一致时优先想尾插题目要求实现“逆序”、栈式存储时优先想头插。这两招在后续“链表的反转”问题里也会结合使用先记住它们的特点后面才能活学活用。4. 遍历链表时的三个隐性坑空指针、死循环、长度不一致4.1 遍历终止条件到底应该写在哪遍历单向链表的标准姿势是void PrintList(LinkList L) { LNode *p L-next; // 跳过带头结点 while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }这个p p-next必须放在循环体内而且和输出数据的顺序不能乱。最常见的错误是写成while (p ! NULL) { p p-next; printf(%d , p-data); }这样在循环最后一步p已经变成NULL再打印p-data就访问了空指针。我在调试链表代码时见到最多的段错误就是这种“先移动后使用”造成的。还有一种写法是while (p-next ! NULL) { ... }这样遍历时会丢掉最后一个结点。为什么因为p指向倒数第二个结点时p-next ! NULL成立进入循环打印处理完倒数第二个结点后p移到最后一个结点此时p-next NULL循环条件失败最后一个结点的数据根本没打印。这种“差一个结点”的错误很难一眼看出来尤其链表很长时。4.2 求链表长度时容易出现的偏一错误求长度最容易出错的是循环条件的初值。推荐写法int Length(LinkList L) { int count 0; LNode *p L-next; while (p ! NULL) { count; p p-next; } return count; }这个思路是对每个访问到的结点计数。p指向第一个数据结点时count从0开始访问一个就加一走到NULL时刚好数完全部结点。记住一个口诀“循环条件看p操作动机看人类逻辑”然后写完后用一个空链表和一个单结点链表分别测一下边界基本不会错。另一个常见错误是带头结点时把链表长度数成结点总数把头结点也算进去了。头结点的data不存数据逻辑上它不是线性表的一部分所以长度统计必须从L-next开始。我之前见过一个同学写了半天题最后才发现自己的每个链表长度都比预期多1就是栽在头结点上。4.3 遍历时不要动头指针本身有些同学为了少定义一个变量直接用L L-next来遍历导致函数结束后头指针丢了。比如void ErrPrint(LinkList L) { L L-next; while (L ! NULL) { printf(%d , L-data); L L-next; } }如果调用者后面还要用这个链表做插入、删除、销毁头指针已经跑到最后一个结点甚至NULL整条链就“找不回来”了。正确做法是永远用一个临时变量p去遍历让头指针L始终指向链表头部。这个习惯不仅为了正确性更是为了可维护性——你不想在排查问题时还得猜头指针跑哪儿去了。4.4 空链表的遍历也一样要跑通写遍历函数时先测试空链表。带头结点的空链表是L-next NULL遍历结果应该是什么都不打印正常退出。很多初学者拿非空链表测试通过就以为代码没问题结果空表直接崩。检查遍历、长度、查找这类函数时我都会列三个测试用例空表、单结点表、多结点表。三个都过了基本可以放心提交。5. 查找第K个结点和按值查找边界条件才是真正的考点5.1 按位置查找的循环次数推导链表没有随机访问能力要找第i个结点必须从头开始走。假设带头结点第一个数据结点的位置是1那么LNode *GetElemByIndex(LinkList L, int i) { if (i 0) return NULL; LNode *p L; int j 0; // 当前p指向的是第j个结点 while (p ! NULL j i) { p p-next; j; } if (p NULL || j i) // 实际上不会ji但防御式编程没坏处 return NULL; return p; }这里我把p初始化为L而不是L-next是为了统一处理“第0个结点就是头结点”的情况方便某些需要返回头结点的场景。当i1时循环走一次p移动到第一个数据结点j变成1返回正确。当i大于链表长度时p会走成NULL返回NULL。这个函数的关键在于链表的查找边界不是“写完看一遍就知道对不对”的必须用边界值去推。我总会自己推一遍空链表时p初始为头结点j0i1p-next是NULL循环结束返回NULL正确。这种推演在考试和面试时都很好用比背诵代码结果可靠得多。5.2 按值查找的返回设计按值查找是另一种高频操作LNode *LocateElem(LinkList L, ElemType e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; // 找到返回结点指针找不到返回NULL }很多初学者会困惑为什么返回的是结点指针而不是下标因为链表中“位置”不是物理上的索引指针本身就是最自然的定位方式。拿到结点指针后你可以直接读取数据、修改数据、也可以和前后结点配合做插入删除。如果题目要求返回序号第几个那还要再维护一个计数器。需要注意的是如果要查找的是结构体类型p-data ! e这种写法就失效了因为C语言结构体不能直接做不等于比较。实战中我会改成编写一个compare回调函数或者只针对基本类型用这种写法。考研题里很少会考结构体按值查找的完整代码但你在项目里用链表存结构体时一定会遇到。5.3 时间复杂度为什么链表的查找O(n)不是坏设计有同学觉得链表查找最坏情况O(n)是不是比数组差其实这个“差”是和你选择的抽象模型绑定的。如果你经常需要按下标找第k个元素就不应该选链表应该用数组或跳表。链表的核心优势在增删查找只是为增删服务的辅助手段。很多算法题看似在考“查找第k个”实际是考你能否在链式结构中利用双指针、快慢指针等方式优化遍历。基础和延伸是一体的。5.4 一次延伸思考倒数第K个结点为什么能优化上篇先不谈详细代码但这个思路值得提前种下。如果链表只知道头指针要找倒数第k个结点最笨的方法就是先遍历一遍求长n再从头走n-k1步。这种方法时间复杂度O(n)空间O(1)没问题。但如果链表太长只能遍历一次呢快慢指针就可以做到快指针先走k步然后快慢指针同步走快指针到NULL时慢指针正好指向倒数第k个结点。这不算“算法复杂度上更优”而是工程上“单遍扫描”的场景优化。等我们讲“单链表下”时我会把它和反转、合并、判断环一起展开这里你先有个印象链表的很多技巧都是围绕“怎么用有限个指针绕开随机访问缺失”来做文章的。6. 链表的销毁与内存管理不会释放结点的代码都是半成品6.1 销毁链表的完整流程先保存后释放很多初学者学链表时花大量时间写插入删除却忽略销毁。实际上在C语言里内存泄漏是真实bug尤其链结点数量动态增长时。销毁链表的标准做法void DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *tmp p-next; // 先保存下一个结点地址 free(p); // 再释放当前结点 p tmp; } }这里的关键就是“先保存再释放”。有些新手会写成while (p ! NULL) { free(p); p p-next; // 错误p已经被free了p-next是野指针访问 }free之后再去访问p-next是未定义行为轻则拿到脏数据重则直接崩溃。我自己就因为这个错误排查过一整晚最后用Valgrind才发现是free后继续用野指针。6.2 释放后头指针置空销毁链表后最好把外部链表的头指针手动置为NULL。因为free只释放了堆内存头指针L仍然存着那个已经失效的地址这种指针叫“悬挂指针”。如果后续代码不小心又用它操作链表会造成double free或者访问已释放内存的错误。所以在调用销毁函数后习惯性写一句L NULL;如果写一个清理函数包装这个操作那就要用到二级指针或者在主调函数里自行置空。我的个人习惯是凡是涉及“修改头指针”的操作要么函数返回新的头指针要么明确要求调用者之后自己LNULL。两种都行但必须约定清楚不能混着来。6.3 如何用工具确认内存没问题如果你们学校实验环境是Linux强烈推荐用valgrind检查内存泄漏。写完链表程序后编译运行gcc -g -o list_demo list_demo.c valgrind --leak-checkfull ./list_demo如果输出里有definitely lost或still reachable说明有结点忘记释放。运行结果里出现Invalid read/write则说明可能操作了野指针。这个工具对排查free后继续访问、越界访问等问题特别有效。我认识的同学里很多链表实验得分不高不是逻辑错而是内存检查不过关。这些工程细节面试官非常看重早点学会受益很大。6.4 为什么我觉得“上篇”必须止步于此单向链表最基本的操作包含建表、遍历、查找、销毁这些都属于“在没有改变链表结构的前提下理解链接关系”的范畴。到了插入和删除、反转、合并、判环、快慢指针这些应用题才是真正考验逻辑编排能力的地方。把基础结构和边界条件练扎实再进入下篇你才不会在插入删除时被指针指来指去绕晕。我一直觉得学链表不能只看思路一定要亲手把所有函数写一遍、跑一遍、破坏一遍。我写这篇文章时又把每个函数都放进本地环境里编译运行了一遍包括空链表、单结点、长链表、重复值这些边界确认没有偷懒省略。你也别光收藏看完代码就打开IDE敲一版折腾出几个段错误再修正那种记忆比背十遍教材都牢。单向链表上的内容就到这结点结构、头插尾插、遍历求长、按位置按值查找、链表销毁每一步我都把最容易出错的地方点出来了。下次我们继续聊真正的重头戏——单向链表的插入与删除、原地反转、有序合并以及快慢指针的那些经典用法。到时候你会发现今天打下的“边界条件”基本功会帮你在下篇少踩一半的坑。 单向链表核心操作详解：从结点结构到遍历销毁
我第一次学数据结构时被数组的“连续存储”绕进去了明明数组已经能存数据、能按下标访问为什么还要搞一个结构体套结构体的单向链表后来真正在C语言里手写了链表才明白数组的“连续”既是优势也是枷锁。这篇内容就来聊聊单向链表的上半部分从结点结构、建表、遍历到查找和销毁把最简单也最容易踩坑的细节讲透。不管你是正在复习数据结构期末、准备考研408还是刚开始学一门语言的底层容器这篇都适合先收藏再对照代码敲一遍。1. 为什么学链表前必须先搞懂结点和指针——从数组的局限说起1.1 数组的“连续”是优点也是枷锁数组在内存里是一块连续空间元素按下标依次排开。访问第i个元素时编译器只需要用“基地址 i * 元素大小”就能算出来时间复杂度是O(1)这是数组最大的优点。但同样因为连续数组的插入和删除操作非常痛苦想让一个元素插到数组中间意味着它后面的所有元素都得整体后移。我在自己写的学生管理系统里试过频繁插入删除时光看数据搬移的代码就头皮发麻。数组扩容更麻烦扩容一次基本等于重新申请内存再拷贝整个数组这个开销在数据量大了以后极其吓人。链表就是冲着这两个痛点来的它不要求元素在物理内存上连续每个结点存放数据之外再额外记录下一个结点的地址。这样插入和删除只需要改指针不需要搬动任何元素。代价是按下标直接访问的能力没了要找第k个结点必须从头指针出发顺着指针一个个走时间复杂度退化到O(n)。所以数据结构的核心取舍就一句话你想把代价花在“访问”上还是花在“增删”上。1.2 链表的“物理离散逻辑连续”单向链表里的每个结点通常包含两部分数据域和指针域。数据域存你自己要保存的数据指针域存的是“下一个结点在哪里”。一连串结点通过这个next指针串起来就形成了逻辑上的线性表。刚接触链表的人最容易出现的一个误区是以为“逻辑连续”等于“物理连续”。实际上链表结点可能分配在内存的各个角落一个结点的地址可能是0x7f...下一个结点可能完全不在相邻地址。这种“离散存储指针串联”的模式才是链表区别于数组的本质。我用一个生活化的类比说明数组像一列硬座车厢座位编号固定你只能按编号坐想加一个人必须让一排人挪位置链表像一摞写着地址的纸条每张纸条上写着自己的内容还写着下一张纸条放在哪儿你只要顺着地址找就能把所有纸条按顺序看完中间想插入一张新纸条只需要改一下前后两张的地址。1.3 从“内存块思维”切换到“结点指针思维”很多教材上来就给你一个链表的结构体定义然后就讲插入删除初学者往往看懂了代码却不知道为什么要这么写。关键障碍在于思维方式没切换过来。数组思维是“内存块”我把一整块空间视作一个大容器数据是容器里的格子。链表思维是“结点指针”每个数据单元是独立的数据之间的“连接关系”本身就是数据的一部分。在单向链表里next指针就是串联起所有结点的“胶水”。你写链表代码时脑子里不应该是一幅完整的内存地图而应该是一串动态的、不断变化的结点关系图。这个思维转变非常重要因为后面所有的链表操作本质上都是在处理“谁指向谁”的问题。头插法改变的是头指针和原首结点之间的指向关系删除结点改变的是前驱结点next指针的目标地址。你把这个逻辑想通了链表题基本就通了一半。2. 单向链表的核心结构结点并非“数据地址”那么简单2.1 C语言里的标准结点定义我用的C语言版本是国内教材最常见的写法#include stdio.h #include stdlib.h typedef int ElemType; // 数据域类型便于日后扩展 typedef struct LNode { ElemType data; // 数据域 struct LNode *next; // 指针域指向下一个结点 } LNode, *LinkList;这里有个新手必问的问题为什么next的类型是struct LNode *而不是LNode *因为在这个结构体内部还处于定义过程中编译器还不知道LNode这个typedef别名已经生效所以只能写完整的struct LNode *。这种“自己指向自己”的结构在数据结构里叫自引用结构是构成各种链式结构的基础。我把数据域类型定义成ElemType而不是直接用int也是给自己留退路。今天用int测试明天想存学生信息、字符串只需要把ElemType改成对应的结构体类型链表逻辑完全不动。这种封装习惯在实际项目中太重要了。2.2 头指针和头结点一字之差天壤之别这是链表里最经典的混淆点。我一直建议初学者先刻两条定义在脑子里头指针是指向链表中第一个结点的指针它本身只是一个指针变量用来定位链表的起点。头结点是额外增加的一个“哨兵”结点它位于第一个实际数据结点之前data域通常不存数据next指向真正的首结点。为什么很多教材都在链表头部加一个头结点主要为了方便统一操作。如果没有头结点在第一个位置插入结点或者删除第一个结点时必须修改头指针的值有了头结点以后头指针永远指向固定存在的头结点插入和删除的逻辑就不需要单独判断“是不是第一个结点”代码能少写很多if。我用一个表格对比一下带不带头结点的区别操作场景无头结点带头结点空链表表示头指针为NULL头指针指向一个next为NULL的结点首结点插入必须特殊处理更新头指针和普通位置插入逻辑一致删除首结点必须特殊处理更新头指针和普通位置删除逻辑一致遍历判断条件从头指针开始循环从头结点next开始循环我在实战里通常选择带头结点的链表除非题目明确要求不带头结点。考研题里两种都可能出现所以两个版本你都得会写但理解上先以带头结点为主写起来没那么容易出错。2.3 为什么创建链表要用二级指针这也是一个高频迷惑点。如果你写了一个函数想在函数内部通过头插法创建链表并修改外部头指针那就必须传入头指针的地址也就是二级指针LinkList *L。比如void CreateListHead(LinkList *L, int n) { *L (LinkList)malloc(sizeof(LNode)); (*L)-next NULL; // ... 插入结点 }为什么不能直接传LinkList L因为C语言函数的传参是值传递你传进去的L是外部头指针的一个拷贝。在这个拷贝身上赋值函数结束之后外部头指针还是原来的值。经典的错误写法是void WrongInit(LinkList L) { L (LinkList)malloc(sizeof(LNode)); L-next NULL; }然后调用时LinkList L; WrongInit(L);最后L不是NULL就是野指针。除非你让函数返回新的头指针用L CreateListHead();这种方式否则就必须用二级指针。很多同学在链表操作上头疼根源就在这个“指针传值”的细节上。3. 手写一个最小可用的单向链表头插法和尾插法的取舍3.1 先写一个创建头结点的函数无论头插还是尾插第一步都是先申请头结点让头指针有地方可指LinkList InitList() { LinkList L (LinkList)malloc(sizeof(LNode)); if (L NULL) { return NULL; } L-next NULL; return L; }很多人懒得判断malloc返回值直接往下写这在小练习里通常没问题但一旦内存耗尽返回NULL代码就会直接操作空指针崩溃。判断返回值这个习惯从今天开始养成后面学树、图都会受益。3.2 头插法代码简单但结果顺序是反的头插法的核心逻辑新结点每次都插在头结点的后面成为新的首结点。void ListHeadInsert(LinkList L, ElemType x) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data x; s-next L-next; // 新结点先连上原来的首结点 L-next s; // 头结点再指向新结点 }这段代码虽然短但两行赋值顺序不能反过来。如果先写L-next s;原链表在后面的结点就丢失了因为s-next还指向NULL。每次插入新的都会放到最前面所以头插法建表得到的链表顺序和你输入数据的顺序正好相反。一个典型的应用场景就是构建“倒序”链表。比如我要实现一个栈式后进先出的效果头插法非常顺手。头插法还因为插入位置固定时间复杂度是O(1)不用担心遍历链表找尾部。缺点是当你希望链表保持输入顺序时必须最后再反转一次得不偿失。3.3 尾插法保留输入顺序但需要一个尾指针如果希望建表后链表的顺序和输入顺序一致那就用尾插法void ListTailInsert(LinkList L, ElemType x) { LNode *tail L; while (tail-next ! NULL) { tail tail-next; } LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data x; s-next NULL; tail-next s; }这个版本每次都要从头遍历到尾部建表的时间复杂度是O(n²)数据量大时明显变慢。更常见的优化是维护一个尾指针在创建过程中始终指向最后一个结点void ListTailInsertFast(LinkList L, ElemType x, LNode **tail) { LNode *s (LNode *)malloc(sizeof(LNode)); if (s NULL) return; s-data x; s-next NULL; (*tail)-next s; (*tail) s; }这个函数同样需要二级指针来更新外部尾指针。我实际写项目时更愿意定义一个“链表结构体”里面同时保存头指针和尾指针typedef struct { LNode *head; LNode *tail; } LinkedList;这样头插、尾插都不需要二级指针代码可读性高很多只是考研408的代码题通常还是用传统的LinkList表示法所以课内功课还是得适应老写法。3.4 两种建表方式的实验对比我自己用一组数字1 2 3 4 5分别做头插和尾插打印结果头插法最终链表5 4 3 2 1尾插法最终链表1 2 3 4 5所以做题时题目要求输出顺序和输入顺序一致时优先想尾插题目要求实现“逆序”、栈式存储时优先想头插。这两招在后续“链表的反转”问题里也会结合使用先记住它们的特点后面才能活学活用。4. 遍历链表时的三个隐性坑空指针、死循环、长度不一致4.1 遍历终止条件到底应该写在哪遍历单向链表的标准姿势是void PrintList(LinkList L) { LNode *p L-next; // 跳过带头结点 while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }这个p p-next必须放在循环体内而且和输出数据的顺序不能乱。最常见的错误是写成while (p ! NULL) { p p-next; printf(%d , p-data); }这样在循环最后一步p已经变成NULL再打印p-data就访问了空指针。我在调试链表代码时见到最多的段错误就是这种“先移动后使用”造成的。还有一种写法是while (p-next ! NULL) { ... }这样遍历时会丢掉最后一个结点。为什么因为p指向倒数第二个结点时p-next ! NULL成立进入循环打印处理完倒数第二个结点后p移到最后一个结点此时p-next NULL循环条件失败最后一个结点的数据根本没打印。这种“差一个结点”的错误很难一眼看出来尤其链表很长时。4.2 求链表长度时容易出现的偏一错误求长度最容易出错的是循环条件的初值。推荐写法int Length(LinkList L) { int count 0; LNode *p L-next; while (p ! NULL) { count; p p-next; } return count; }这个思路是对每个访问到的结点计数。p指向第一个数据结点时count从0开始访问一个就加一走到NULL时刚好数完全部结点。记住一个口诀“循环条件看p操作动机看人类逻辑”然后写完后用一个空链表和一个单结点链表分别测一下边界基本不会错。另一个常见错误是带头结点时把链表长度数成结点总数把头结点也算进去了。头结点的data不存数据逻辑上它不是线性表的一部分所以长度统计必须从L-next开始。我之前见过一个同学写了半天题最后才发现自己的每个链表长度都比预期多1就是栽在头结点上。4.3 遍历时不要动头指针本身有些同学为了少定义一个变量直接用L L-next来遍历导致函数结束后头指针丢了。比如void ErrPrint(LinkList L) { L L-next; while (L ! NULL) { printf(%d , L-data); L L-next; } }如果调用者后面还要用这个链表做插入、删除、销毁头指针已经跑到最后一个结点甚至NULL整条链就“找不回来”了。正确做法是永远用一个临时变量p去遍历让头指针L始终指向链表头部。这个习惯不仅为了正确性更是为了可维护性——你不想在排查问题时还得猜头指针跑哪儿去了。4.4 空链表的遍历也一样要跑通写遍历函数时先测试空链表。带头结点的空链表是L-next NULL遍历结果应该是什么都不打印正常退出。很多初学者拿非空链表测试通过就以为代码没问题结果空表直接崩。检查遍历、长度、查找这类函数时我都会列三个测试用例空表、单结点表、多结点表。三个都过了基本可以放心提交。5. 查找第K个结点和按值查找边界条件才是真正的考点5.1 按位置查找的循环次数推导链表没有随机访问能力要找第i个结点必须从头开始走。假设带头结点第一个数据结点的位置是1那么LNode *GetElemByIndex(LinkList L, int i) { if (i 0) return NULL; LNode *p L; int j 0; // 当前p指向的是第j个结点 while (p ! NULL j i) { p p-next; j; } if (p NULL || j i) // 实际上不会ji但防御式编程没坏处 return NULL; return p; }这里我把p初始化为L而不是L-next是为了统一处理“第0个结点就是头结点”的情况方便某些需要返回头结点的场景。当i1时循环走一次p移动到第一个数据结点j变成1返回正确。当i大于链表长度时p会走成NULL返回NULL。这个函数的关键在于链表的查找边界不是“写完看一遍就知道对不对”的必须用边界值去推。我总会自己推一遍空链表时p初始为头结点j0i1p-next是NULL循环结束返回NULL正确。这种推演在考试和面试时都很好用比背诵代码结果可靠得多。5.2 按值查找的返回设计按值查找是另一种高频操作LNode *LocateElem(LinkList L, ElemType e) { LNode *p L-next; while (p ! NULL p-data ! e) { p p-next; } return p; // 找到返回结点指针找不到返回NULL }很多初学者会困惑为什么返回的是结点指针而不是下标因为链表中“位置”不是物理上的索引指针本身就是最自然的定位方式。拿到结点指针后你可以直接读取数据、修改数据、也可以和前后结点配合做插入删除。如果题目要求返回序号第几个那还要再维护一个计数器。需要注意的是如果要查找的是结构体类型p-data ! e这种写法就失效了因为C语言结构体不能直接做不等于比较。实战中我会改成编写一个compare回调函数或者只针对基本类型用这种写法。考研题里很少会考结构体按值查找的完整代码但你在项目里用链表存结构体时一定会遇到。5.3 时间复杂度为什么链表的查找O(n)不是坏设计有同学觉得链表查找最坏情况O(n)是不是比数组差其实这个“差”是和你选择的抽象模型绑定的。如果你经常需要按下标找第k个元素就不应该选链表应该用数组或跳表。链表的核心优势在增删查找只是为增删服务的辅助手段。很多算法题看似在考“查找第k个”实际是考你能否在链式结构中利用双指针、快慢指针等方式优化遍历。基础和延伸是一体的。5.4 一次延伸思考倒数第K个结点为什么能优化上篇先不谈详细代码但这个思路值得提前种下。如果链表只知道头指针要找倒数第k个结点最笨的方法就是先遍历一遍求长n再从头走n-k1步。这种方法时间复杂度O(n)空间O(1)没问题。但如果链表太长只能遍历一次呢快慢指针就可以做到快指针先走k步然后快慢指针同步走快指针到NULL时慢指针正好指向倒数第k个结点。这不算“算法复杂度上更优”而是工程上“单遍扫描”的场景优化。等我们讲“单链表下”时我会把它和反转、合并、判断环一起展开这里你先有个印象链表的很多技巧都是围绕“怎么用有限个指针绕开随机访问缺失”来做文章的。6. 链表的销毁与内存管理不会释放结点的代码都是半成品6.1 销毁链表的完整流程先保存后释放很多初学者学链表时花大量时间写插入删除却忽略销毁。实际上在C语言里内存泄漏是真实bug尤其链结点数量动态增长时。销毁链表的标准做法void DestroyList(LinkList L) { LNode *p L; while (p ! NULL) { LNode *tmp p-next; // 先保存下一个结点地址 free(p); // 再释放当前结点 p tmp; } }这里的关键就是“先保存再释放”。有些新手会写成while (p ! NULL) { free(p); p p-next; // 错误p已经被free了p-next是野指针访问 }free之后再去访问p-next是未定义行为轻则拿到脏数据重则直接崩溃。我自己就因为这个错误排查过一整晚最后用Valgrind才发现是free后继续用野指针。6.2 释放后头指针置空销毁链表后最好把外部链表的头指针手动置为NULL。因为free只释放了堆内存头指针L仍然存着那个已经失效的地址这种指针叫“悬挂指针”。如果后续代码不小心又用它操作链表会造成double free或者访问已释放内存的错误。所以在调用销毁函数后习惯性写一句L NULL;如果写一个清理函数包装这个操作那就要用到二级指针或者在主调函数里自行置空。我的个人习惯是凡是涉及“修改头指针”的操作要么函数返回新的头指针要么明确要求调用者之后自己LNULL。两种都行但必须约定清楚不能混着来。6.3 如何用工具确认内存没问题如果你们学校实验环境是Linux强烈推荐用valgrind检查内存泄漏。写完链表程序后编译运行gcc -g -o list_demo list_demo.c valgrind --leak-checkfull ./list_demo如果输出里有definitely lost或still reachable说明有结点忘记释放。运行结果里出现Invalid read/write则说明可能操作了野指针。这个工具对排查free后继续访问、越界访问等问题特别有效。我认识的同学里很多链表实验得分不高不是逻辑错而是内存检查不过关。这些工程细节面试官非常看重早点学会受益很大。6.4 为什么我觉得“上篇”必须止步于此单向链表最基本的操作包含建表、遍历、查找、销毁这些都属于“在没有改变链表结构的前提下理解链接关系”的范畴。到了插入和删除、反转、合并、判环、快慢指针这些应用题才是真正考验逻辑编排能力的地方。把基础结构和边界条件练扎实再进入下篇你才不会在插入删除时被指针指来指去绕晕。我一直觉得学链表不能只看思路一定要亲手把所有函数写一遍、跑一遍、破坏一遍。我写这篇文章时又把每个函数都放进本地环境里编译运行了一遍包括空链表、单结点、长链表、重复值这些边界确认没有偷懒省略。你也别光收藏看完代码就打开IDE敲一版折腾出几个段错误再修正那种记忆比背十遍教材都牢。单向链表上的内容就到这结点结构、头插尾插、遍历求长、按位置按值查找、链表销毁每一步我都把最容易出错的地方点出来了。下次我们继续聊真正的重头戏——单向链表的插入与删除、原地反转、有序合并以及快慢指针的那些经典用法。到时候你会发现今天打下的“边界条件”基本功会帮你在下篇少踩一半的坑。