先说明看到“王道道道道”这几个字我就懂了你多半是在准备考研或者期末复习数据结构要么就是被某个视频里老师的口头禅洗脑了。单链表作为线性表里最基础也最阴间的部分头插法和尾插法属于那种“上课一听就会、一写代码就废”的知识点。这篇文章不玩虚的直接把这两种插入方式从原理到代码、从时间复杂度到应用场景全部拆干净看完你再去刷题会顺手很多。1. 先把单链表这层窗户纸捅破1.1 为什么需要链表这种结构数组用起来多爽按下标随机访问 O(1) 就完事这是它的优点。但是数组的痛点也很明显插入、删除数据需要大量搬移元素平均时间复杂度 O(n)而且数组的空间是连续分配的扩容要么一次性开大导致浪费要么频繁扩容导致性能不行。链表就是为了解决“频繁增删数据”这个场景而生的。链表的核心思路是“用空间换时间、用指针换自由”每个结点各自存储数据和一个指向下一个结点的指针逻辑上连成一条线。它不需要一整块连续的内存而是允许数据散落在内存各处。单链表则是链表家族里最朴素的一种每个结点只存一个 next 指针只能从前往后走。虽然功能上不如双向链表灵活但它在面试笔试里出现的频率最高因为实现简洁、坑也足够多特别适合考察基本功。1.2 结点的结构定义不管用 C 还是 C写单链表第一步都是定义结点结构。C 语言的写法如下typedef struct Node { int data; // 数据域这里以 int 为例 struct Node *next; // 指针域指向下一个结点 } Node;注意这里struct Node *next这个写法很多新手会漏掉struct关键字或者忘了在结尾加分号。你要是用 C 写结构体名本身就可以直接当类型名用不需要 typedef但 C 语言里必须这样写。指针域存放的是下一个结点的地址这就是“链”的本质。1.3 两个必备辅助功能初始化和遍历打印在正式讲插入之前先把两个后面要用到的辅助函数写出来。第一个是初始化一个空链表我用的是带头结点的写法Node* initList() { Node *head (Node*)malloc(sizeof(Node)); if (head NULL) { printf(内存分配失败\n); return NULL; } head-next NULL; // 头结点不存数据next 先置空 return head; }第二个是遍历打印。链表的遍历只能从头开始通过 next 指针一个一个跳void printList(Node *head) { Node *p head-next; // 跳过头结点从第一个有效结点开始 while (p ! NULL) { printf(%d - , p-data); p p-next; } printf(NULL\n); }为什么要设置“头结点”这里说一下我的理解带头结点的好处不仅仅是代码统一更重要的是头结点作为哨兵让“在第一个位置插入”和“在中间位置插入”的代码逻辑完全一致不需要单独判断“是不是插在开头”。这不只是为了写起来省事关键是能少写很多 if 分支也就少很多 bug 隐患。不带头结点的写法在很多教材里也出现但实际工程和个人练习我更推荐带头结点思路清晰不容易错。2. 头插法把新结点怼在最前面2.1 头插法的核心逻辑头插法的思路非常粗暴每次新创建一个结点都把它插到头结点后面、当前第一个有效结点的前面。也就是说新结点始终成为链表的第一个结点。这个方法有个天然的结果插入的顺序和最终的链表顺序是反的。你按 1、2、3 的顺序插入最后遍历输出是 3、2、1。这个特性不是 bug而是头插法的核心优势。先看核心流程新建结点 - 新结点 next 指向原来第一个结点 - 头结点 next 指向新结点。这里最关键的坑就在顺序上必须先让新结点的 next 指向原来的首元结点然后再更新头结点的 next。如果先改头结点的 next原来的链表就断掉了后面的结点全找不到了。为什么是这个顺序因为头结点的 next 是我们找到第一个结点的唯一入口。你把入口改了原来的第一个结点就变成一片“失联区域”内存还占着但你没法通过链表访问到它了。这就像你要在一串珍珠项链的头部加一颗珠子你得先让新珠子的孔套住原来第一颗珠子再把项链的头绳换到新珠子上。顺序反了整串就散了。2.2 头插法完整代码与逐行解读void insertAtHead(Node *head, int data) { // 1. 创建新结点 Node *newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); return; } newNode-data data; // 2. 新结点指向原首元结点 newNode-next head-next; // 3. 头结点指向新结点 head-next newNode; }逐行说几个关键点第 1 步malloc之后要判断返回值。内存分配失败不是闹着玩的嵌入式场景或者长时间运行的服务里频繁分配内存后没及时释放很可能分配失败程序直接崩溃。第 3 步这里先让newNode-next head-next在head-next还没被覆盖时完成指向这步是整段代码的灵魂。之后head-next newNode才把链表的入口切到新结点。第 4 步这里不需要特殊判断链表是否为空。如果链表是空的head-next本来就是 NULL新结点的 next 等于 NULL逻辑完全自洽。这也是带头结点设计的好处之一。为了更直观用一个简单的数据流向说明初始链表head - NULL插入 1 先建结点11-next head-next即 NULL然后head-next 结点1结果head - 1 - NULL再插入 2 建结点22-next head-next即结点1然后head-next 结点2结果head - 2 - 1 - NULL再插入 3 结果head - 3 - 2 - 1 - NULL可以看到输入顺序 1、2、3链表顺序 3、2、1。每次都插在头部所以最后插入的元素排最前。2.3 头插法的特点逆序与 O(1)头插法有两个显著特点需要记住。第一个特点是逆序。因为每次都插在最前面所以最终的链表顺序和插入顺序相反。这个特性平时看起来像缺点但在某些场景非常实用。比如后面第 6 节要讲的链表反转不用额外申请空间直接反复用头插法就能实现“原地反转”这就是典型的以毒攻毒。第二个特点是时间复杂度。头插法的时间复杂度是 O(1)不管链表有多长都只需要常数级别的指针修改操作就完成插入。对于需要频繁在头部插入数据的场景这是最快的方案。这里补充一个大家容易问的问题头插法和“在表头插入”是一回事吗严格来说在有头结点的链表结构中头插法都发生在头结点后面也就是说插入的位置永远是“第一个有效位置”。逻辑位置固定但物理上不需要遍历链表因此效率非常高。3. 尾插法老老实实排队3.1 尾插法的核心逻辑尾插法的作用很直观把新结点追加到链表末尾保持插入顺序和链表顺序一致。如果一个线性表的数据是按序读入的最后希望按同样的顺序输出尾插法就是最自然的方案。尾插法的流程比头插法多一个动作需要先找到当前的最后一个结点然后把新结点接上去。这听起来很简单但实现细节里藏着两个不同的版本我分别展开。第一个版本每次插入都从头遍历找尾巴。比如Node *p head; while (p-next ! NULL) { p p-next; } // 此时 p 是最后一个结点这个版本每次插入的时间复杂度是 O(n)因为每插入一个结点都要从头到尾走一遍。每次插入都重新遍历那建一个 n 个结点的链表总时间复杂度是 O(n²)数据量大了以后效率很差。第二个版本维护一个尾指针 tail始终指向最后一个结点。每插入一个新结点tail 就能直接定位时间复杂度 O(1)。核心就是时刻记着“尾巴在哪”。第二个版本是我自己更常用的写法尤其在批量建链表的场景下效率差距不是一点半点。3.2 尾插法完整代码与逐行解读// 带尾指针的尾插法 void insertAtTail(Node *head, Node **tail, int data) { Node *newNode (Node*)malloc(sizeof(Node)); if (newNode NULL) { printf(内存分配失败\n); return; } newNode-data data; newNode-next NULL; // 新结点的 next 一定置为 NULL (*tail)-next newNode; // 原来最后一个结点指向新结点 *tail newNode; // 更新尾指针 }这里有个细节Node **tail也就是尾指针的指针。因为在函数内部要修改 tail 本身的值让 tail 指向新的最后一个结点如果传的是Node *tail函数结束时修改不生效必须传地址才能让实参跟着变。这个知识点本身就是 C 语言里的常见考点值得记住。完整的建链过程是这样的Node *head initList(); Node *tail head; // 初始时头结点也是最后一个结点 insertAtTail(head, tail, 1); insertAtTail(head, tail, 2); insertAtTail(head, tail, 3); // 链表结果head - 1 - 2 - 3 - NULL如果不用尾指针那每次都要从 head 遍历到末尾写法如下Node *p head; while (p-next ! NULL) { p p-next; } p-next newNode;这个写法也能用但每次插入都是 O(n)。在数据量几千几万的时候体感不明显到了百万级别O(n²) 和 O(n) 的差别就是几分钟和毫秒级的差距。3.3 尾插法的特点正序与 O(1) 的关键尾插法保持输入顺序这个特性决定了它最常用来“从无到有”构建一个符合逻辑顺序的链表。比如读入一批学生成绩、一组坐标点希望链表顺序和源数据保持一致直接用尾插法。要真正做到 O(1) 插入关键在于尾指针 tail。如果不维护它每次插入都要从头遍历到尾时间复杂度直接退化。这一点无论是在考试写伪代码还是实际开发中都很重要。很多新手一开始写尾插法是 O(n²)后来加了 tail 指针就变成 O(n)整个建链过程效率翻天覆地。在考试或者面试中不要只写一个函数要把 tail 的变化过程也写清楚。很多判卷标准里尾指针更新是得分点漏了*tail newNode这行代码逻辑就崩了。4. 头插和尾插到底怎么选4.1 多维对比表用一张表把区别说清楚复习的时候直接看这张表就行。对比维度头插法尾插法插入位置头结点之后表首链表末尾是否需要遍历不需要O(1)有尾指针 O(1)无尾指针 O(n)结果顺序与插入顺序相反逆序与插入顺序一致正序代码复杂度简单只需改两个指针稍复杂需要维护尾巴或遍历典型应用链表反转、栈顶插入输入顺序敏感的建链、队列插入4.2 实际场景怎么选如果是构建一个全新的链表而且输入数据的先后顺序有业务含义比如时间序列、日志记录用尾插法。如果只要求快速插入、不关心顺序或者希望实现后进先出的效果用头插法。如果你要把一个既有链表反转头插法是天然的工具不用额外开辟空间。这里我补充一个自己的偏好凡是需要“批量建链”的地方我都优先尾插法并且配一个 tail 指针。原因很简单尾插法建出来的链表读起来符合直觉调试的时候顺着输出看一眼就知道哪里有问题。头插法虽然写起来更短但逆序的特性容易让后来维护代码的人包括三个月后的自己满脸问号代码的可读性也是一种成本。5. 新手最容易踩的坑含现场排查5.1 指针顺序反了链表断成两截这是头插法和尾插法里最经典的一个错误。以头插法为例如果代码写成这样head-next newNode; newNode-next head-next; // 此时 head-next 已经是 newNode 了那么newNode-next指向的是自己原来链表里的所有结点全部丢失。这种 bug 在代码里看是“逻辑错误”不报编译错运行也不崩但遍历的时候要么死循环如果打印输出的话会一直走要么只输出一个结点。排查方法插入后立刻调用遍历函数看输出结果是否和预期一致。如果链表节点数量突然从 n 变成 199% 是指针顺序写反了。记住铁律先把新结点的 next 改成旧值再改前驱的 next。5.2 malloc 后忘了判断返回值内存分配失败不是大概率事件但一旦发生程序通常会段错误。原因很简单返回 NULL 之后代码立刻访问newNode-data等于对空指针解引用直接崩溃。现代操作系统上内存分配失败概率低所以很多人养成不判断的习惯。但在嵌入式开发、内存受限的环境里或者测试覆盖率极高的工程项目里这种习惯会出事。拿我的经验来说写完链表增删函数先把 malloc 的判断补上这是基本的工程素养也能防止线上事故。5.3 尾插法忘记置空 next用尾插法时newNode-next NULL这一行容易被漏掉。malloc 出来的内存区域内容随机不是默认的 NULL如果不显式置空遍历的时候就会顺着一个野地址跑到未知区域轻则多输出一堆垃圾值重则直接崩溃。这是一个“看起来最不起眼但实际非常致命”的坑。我排查过不少学弟学妹的代码报错说“遍历输出停不下来”十有八九是尾插之后 next 没置空。5.4 混淆头结点和首元结点头结点是一个不存数据的结点它的作用是作为入口和哨兵首元结点是第一个真正存数据的结点。很多题目会把头结点和首元结点混着说导致代码里判断边界的时候出错。区分方法很简单头结点的 data 域不用next 指向首元结点遍历链表时要跳过头结点从 head-next 开始。如果初始化时把 head 的 data 也赋值了那后面的逻辑全是歪的。6. 拿两道经典题练手6.1 用头插法实现链表反转这是一道经典到不能再经典的题给定一个单链表把它反转。思路很简单新建一个带头结点的空链表然后遍历原链表每遇到一个结点就用头插法插到新链表里。因为头插法是逆序的所以遍历完原链表新链表的顺序就是原链表的逆序即反转完成。Node* reverseList(Node *head) { Node *newHead initList(); Node *p head-next; while (p ! NULL) { Node *temp p-next; // 先暂存下一个结点 p-next newHead-next; // 头插的两步 newHead-next p; p temp; // 继续处理原链表的下一个结点 } return newHead; }注意Node *temp p-next这一步不暂存的话p 的 next 被改掉之后原链表就断了后面的结点全找不回来。这个和头插法插入顺序是同一个道理都是“先保存再修改”。6.2 尾插法按顺序构建播放列表模拟一个场景你有一串歌曲名单要按照用户添加的顺序播放。用尾插法构建链表保持顺序每添加一首歌就追加到尾部。核心代码如下Node *head initList(); Node *tail head; // 假设 names 数组是歌曲名的字符串数组这里简化为 int 了 int songIds[] {101, 202, 303, 404}; for (int i 0; i 4; i) { insertAtTail(head, tail, songIds[i]); } printList(head);这个场景体现了尾插法不可替代的价值输入顺序就是展示顺序没有任何一次插入需要搬移数据。数据量很大时链表存取的优势会非常明显。6.3 从题里提炼出的通用套路我自己的感觉是链表相关的题不管怎么变核心就是四种操作插入、删除、遍历、反转。头插和尾插是插入的两种极端形态掌握了它们很多题的做法就是“套模板”。比如“从尾到头打印链表”可以用头插法重新建链再打印“合并两个有序链表”每次都选择较小的那个尾插到新链表“删除倒数第 k 个结点”用到快慢指针本质上也是遍历技巧的组合。所以我的建议是不要急着一道题刷十种解法先把单链表的基本结构、头插、尾插、删除、反转这五个操作写熟。写熟了以后遇到没见过的题至少能想到“哦这能用头插法特性做”“这能用尾插顺着走”思路自然就来了。最后再分享点个人想法。我刚开始学链表的时候觉得头插法很反直觉为什么还要专门学一个“逆序插入”的方法后来才发现这不只是应付考试的考点它是很多高级数据结构的底层零件。比如邻接表存图的时候头插法就是在 O(1) 时间内把边加到顶点下面的标准操作。每个新边都能最快到达这正是需要效率的场景。如果你正在准备考试或者面试把本文这份代码自己手敲一遍然后不看代码再写一遍直到形成肌肉记忆。链表这东西看十遍不如写一遍写一遍不如调试一遍。祝你一次就过。