企业官网建设流程全解析

我第一次写链表的头插法，是在一个不太顺利的上机晚上。当时对着严蔚敏那本经典的C语言版教材看了半天，觉得“这有什么难的，无非是改两个指针”，结果一编译就翻车：不是段错误，就是打印出来整条链全是最后一个节点的值。后来才明白，头插法虽然核心代码只有三行，但每一步都在和指针较劲，一个顺序写反，链就断了。

这篇文章就是冲着“把头插法彻底吃透”来的。我会从“头插法到底在做什么”讲起，拆解每一行代码为什么这么写，再给出带不带头结点两种写法的完整C语言实现，最后把我这些年遇到、也帮别人排查过的几个经典坑全部列出来。无论你是正在学数据结构的学生，还是准备考研408、正在刷链表题的考生，都能照着一步步复现出正确结果，并且明白背后的原理。

1. 头插法到底是什么：一个“抢第一名”的插入操作

1.1 名字里的“头”才是关键

链表是一串节点组成的结构，每个节点分成两半：一半是数据域，存放真正的值；另一半是指针域，存放下一个节点的地址。整条链表只有一个对外入口，一般叫头指针 head。你要访问任何一个节点，都只能从 head 出发，沿着 next 指针一个一个往后走，谁都不能跳着访问。这就是“链”的含义。

头插法里的“头”，指的就是链表的第一个位置。头插法做的事情很简单：每次来一个新节点，直接把它塞到最前面，让新节点成为链表的第一个节点。原来的第一个节点自动退位成第二个，原来的第二个退位成第三个，后面的依次顺延。

打个比方，这就跟食堂打饭排队一样。别人按顺序依次排在队尾是正常操作，头插法就是总有新人直接站到打饭窗口前，插到队首。你按 10、20、30、40、50 的顺序，让这五个数字依次插队五次，最后队伍从前到后就是 50、40、30、20、10。先来的反而排到了最后，这一条性质，就是头插法最大的特征：建成的链表顺序和输入顺序完全相反。

1.2 头插法与尾插法、指定位置插入的横向对比

清楚了基本动作之后，把链表里常见的三种插入放一起对比，会更有感觉。

尾插法如果想做到 O(1)，必须在建表时额外维护一个尾指针 tail，每次都让 tail 指向最后，否则每插一次都要从头走到尾，n 次插入就是 O(n²)，非常浪费。指定位置插入就更不用说了，不管插在第几个位置，都得先遍历查找，遍历本身就是链表的“固定成本”。

头插法特殊在它根本不需要定位。第一个位置在哪里，head 已经告诉你了，所以它天然是 O(1)。这同时带来一个副产品：你不需要知道链表当前有多少个节点，插入过程完全不受链表长度影响。对于“只要建表、不要求顺序”的场景，头插法是所有插入方式里成本最低的一种。而且它和尾插法的结果正好相反——如果想用头插法得到正序链表，答案是不行，除非结束后再做一次整体逆置。

1.3 为什么教材和实验课都先讲头插法

很多学生不理解，为什么教材不先讲看起来更“正常”的尾插法，而偏偏让头插法打头阵。我个人的体会是：头插法是所有链表插入操作里代码量最短、指针操作最经典的样板。

它的核心就三步：申请新节点、让新节点指向原来的头、让头指向新节点。这三步涵盖了单链表操作一半以上的要点——malloc 动态申请内存、指针域修改、头指针更新。理解头插法的“先接后断”之后，删除节点、链表逆置、有序插入这些操作都可以顺着同一套思路推出来。

更现实的原因是：头插法的“逆序”特性是考试常客。408 和各类数据结构的卷子里，“用头插法建立链表后，输出顺序是什么”这类题能变着花样考一万年。很多同学代码会写，但到了这种概念题上反而丢分，不是不懂指针，而是没把这个性质刻在脑子里。先学头插法，其实是在用最小的代码量同时掌握操作能力和性质理解。

2. 三行核心代码逐句拆解：指针顺序为什么不能乱

2.1 节点的基本形态：数据域加指针域

要写头插法，先得有节点。C 语言里定义一个单链表节点，最标准的方式是下面这样：

struct Node { int data; // 数据域：存放节点的值 struct Node *next; // 指针域：存下一个节点的地址 };

int写在最前面，是因为这里拿整数做演示。实际工程里可以把 int 换成任意数据类型，甚至是一个复杂结构体，链表节点的组织方式不变。重点是struct Node *next这一行，它是“自引用”——结构体里面有一个指向自己这个类型的指针。

有些新手会对这个写法困惑：结构体还没定义完，怎么就在自己里面声明自己了？这里的关键是：next存的是地址，指针的大小在给定的平台上总是固定的（一般是 8 字节），编译器不需要知道 Node 的完整布局就能算出指针域需要多少空间。所以这种自引用是合法且常用的。注意 C 语言里写类型名必须带struct前缀，除非一开始用typedef起别名，很多教材喜欢用typedef简化，我这里保持struct Node的写法，是为了让每一步都看得见、摸得着。

2.2 malloc 申请内存与新节点的三行操作

有了类型定义，头插法的核心函数就可以写了。这里用二级指针的版本，通过参数直接修改外部 head，这也是最不容易出错的写法：

void insertAtHead(struct Node **head, int value) { // 第 1 步：申请一个新节点 struct Node *newNode = (struct Node*)malloc(sizeof(struct Node)); if (newNode == NULL) { printf("内存分配失败\n"); exit(1); } // 第 2 步：给数据域赋值 newNode->data = value; // 第 3 步：新节点指向原来的第一个节点 newNode->next = *head; // 第 4 步：让头指针指向新节点 *head = newNode; }

这几行要逐句理解，不能背过就完。

第一步的malloc是在堆上申请一块能装下一个 Node 结构体的空间，返回这块空间的首地址。这里有两个新手容易忽略的点。第一，malloc完全有可能失败，失败时返回 NULL，如果不检查就用，后面解引用 NULL 指针会直接段错误。第二，malloc不会清理内存，申请出来的空间里是残留的垃圾数据。也就是说，你无法假设newNode->next现在是什么值。所以后面必须明确给它赋值，这也是很多 bug 的根源——以为 new 出来的对象是干净的，其实完全不是。C++ 里new也一样，next也得手动初始化。

第二步给数据域赋值，这个好理解。第三步newNode->next = *head，是让新节点接管原来的第一个节点。此时*head还保存着旧链表第一个节点的地址，赋值之后，新节点的 next 就指向了它，相当于把整条旧链“挂在”新节点后面。注意，这时候 head 还没有变，旧链表依然能通过原头指针访问到。

第四步*head = newNode，把入口指针更新成新节点。这一步一执行，新节点正式成为链表的第一个节点。从外部看，整个链表比原来长了一个节点，数据多了 value，而头指针 head 指向的位置变了。

把三行操作浓缩一下，整个过程就一句话：先让新节点接管旧链，再让 head 指向新节点。顺序不能反。

还有一个很多人会问的问题：为什么这里用二级指针，不用返回值行不行？当然行，返回值版本也就是把“更新 head”这件事挪到函数外：

struct Node* insertAtHead(struct Node *head, int value) { // 前面的 malloc 和数据赋值都一样 newNode->next = head; head = newNode; return head; }

函数里改的参数只是形参，函数一结束就失效，所以必须把新头 return 出去，外部靠head = insertAtHead(head, value)接收。二级指针版本的区别是直接改传进来的地址所指向的变量，这跟“通过快递单号直接改收货地址”是一个道理，更符合“插入本身是一个就地操作”的直觉。两个版本代码里都经常出现，建议都写一遍，能区分它们，说明你已经理解了 C 语言的值传递。

2.3 为什么“先接后断”的顺序不能换

现在把顺序反过来，写一段错误代码感受一下后果：

void wrongInsert(struct Node **head, int value) { struct Node *newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = value; *head = newNode; // 错误：先把 head 改了 newNode->next = *head; // 错误：*head 已经是 newNode 自己 }

仔细看这两行。第一行把*head改成 newNode 之后，旧链表第一个节点的地址被彻底覆盖了，外部已经没有任何变量能访问到旧链表，旧链等于直接“蒸发”。第二行执行newNode->next = *head时，*head的值是 newNode 自己的地址，于是新节点的 next 指向自己，形成自环。

这种环非常隐蔽。你遍历链表时会发现，第一个节点打印完之后又打印它自己，然后一直打印同一个值，程序陷入死循环，或者缓冲区打印满了，最终以段错误收场。当然也有一种可能：如果你运气“好”，旧链表的第一个节点地址被某些地方还保存着，但这种情况只是把崩溃延后了，该错的还是错。

正确的记忆口诀很简单：先接后断。新节点先把旧链的第一个节点“接住”，然后才允许 head 换人。这个过程和我们换手机号是一样的：先把通讯录备份到新手机，再注销旧号码。如果反过来，先注销旧号再备份，联系人全没了。在代码层面，“备份”就发生在newNode->next = *head这一句，旧链的首地址被安全地存到了新节点里；之后*head = newNode怎么改都不怕，因为旧链已经挂在新节点后面了。

3. 带不带头结点，两套写法的选择逻辑

3.1 哨兵节点到底解决了什么问题

说完了核心原理，接下来是很多教材会把新手绕晕的一个点：链表到底要不要带头结点？这里的“头结点”指的是哨兵节点（dummy node），它是链表中一个特殊的、不存业务数据的节点，永远站在链表最前面，头指针 head 永远指向它，真正的数据节点从head->next才开始。还有一种链表不带头结点，第一个节点就直接存数据，head 直接指向第一个元素。

两种画法都叫链表，差别全在“第一个位置”怎么处理。

不带头结点时，插入第一个位置意味着要修改 head 本身，所以头插函数必须写成二级指针或者用返回值，否则外部 head 不会变。带头结点时，插入第一个位置变成了“在哨兵节点之后插入”，head 始终指向哨兵，永远不需要动 head 这个变量，一级指针直接改head->next就够了。

哨兵节点的意义，就是让空表和非空表的操作逻辑完全统一。空表时没有数据节点，但哨兵还在，head->next == NULL表示空表；插入时，空表和非空表执行的代码一模一样，不用额外写 if 判断。这个“少一个特殊分支”的优势，在插入、删除都要做的时候特别明显，代码能明显写得干净。

3.2 两种头插实现对比

先看不带头结点的版本。空链表时 head 是 NULL，往空链插入第一个节点，newNode->next = *head等于newNode->next = NULL，正好让新节点成为既是第一个也是最后一个节点，逻辑上没有任何特殊情况：

void insertAtHead(struct Node **head, int value) { struct Node *newNode = createNode(value); newNode->next = *head; *head = newNode; }

再看带头结点的版本。head 初始指向哨兵节点，哨兵的 data 可以随便放个值，比如 -1，真正有意义的数据从哨兵后面开始：

void insertWithDummy(struct Node *head, int value) { struct Node *newNode = createNode(value); newNode->next = head->next; head->next = newNode; }

对比一下细节，我干脆列个表格：

从表里能看出来，带头结点最大的好处是消除了“第一个位置”的特殊性。代价是多占用一个节点的内存，以及多一个哨兵节点需要维护。但这点内存几乎可以忽略，换来的是代码逻辑的大幅简化，所以工程里非常爱用。

3.3 考研和项目里分别怎么选

这个话题经常有学生纠结，我直接给结论：两种都要会，但要知道它们分别在什么场合出现。

课程刚入门或者写实验报告，不带头结点更直观，因为你能直接看到一个空链表就是 NULL，插入过程也没有“哨兵”这个额外概念。但你必须强迫自己接受一个现实：不带头结点的链表，凡是可能修改头指针的地方，都要用二级指针或者返回值来同步。这也是很多实验报告里同学漏掉return head然后整个链表“丢失”的真正原因。

备战考研和刷 408 题的时候，建议熟悉带头结点写法。严蔚敏教材里大量算法都建立在带头结点模型上，很多选择题和大题也会默认链表带头结点。做链表类算法题时，即便题目没给哨兵，也经常会人为造一个 fake head，目的就是消除头节点的边界判断，降低出错概率。工程代码里，凡是频繁在头部插入删除的结构，比如邻接表、缓存淘汰链表、栈的链式实现，用哨兵节点都能省掉大量边界逻辑，维护性也更好。

把两种写法花十分钟互相改一遍，如果都能跑通，链表基础基本就扎实了。

4. 完整实战：用头插法建表，结果为什么是倒序的

4.1 main 函数完整代码与运行结果

原理说了这么多，直接看一个能编译、能运行的完整程序。下面的代码会依次向链表头插入 10、20、30、40、50，每次插入后立刻打印整条链表：

#include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; struct Node* createNode(int value) { struct Node *p = (struct Node*)malloc(sizeof(struct Node)); if (p == NULL) { printf("内存分配失败\n"); exit(1); } p->data = value; p->next = NULL; return p; } void insertAtHead(struct Node **head, int value) { struct Node *newNode = createNode(value); newNode->next = *head; *head = newNode; } void printList(struct Node *head) { struct Node *p = head; while (p != NULL) { printf("%d -> ", p->data); p = p->next; } printf("NULL\n"); } void freeList(struct Node *head) { while (head != NULL) { struct Node *tmp = head->next; free(head); head = tmp; } } int main() { struct Node *head = NULL; int values[] = {10, 20, 30, 40, 50}; for (int i = 0; i < 5; i++) { insertAtHead(&head, values[i]); printList(head); } printf("最终链表："); printList(head); freeList(head); return 0; }

运行结果是：

10 -> NULL 20 -> 10 -> NULL 30 -> 20 -> 10 -> NULL 40 -> 30 -> 20 -> 10 -> NULL 50 -> 40 -> 30 -> 20 -> 10 -> NULL 最终链表：50 -> 40 -> 30 -> 20 -> 10 -> NULL

注意我特意在createNode里把p->next = NULL写上了。有些同学觉得在头插法里 next 反正马上会被赋值，初始化为 NULL 多此一举。这个习惯非常不好。malloc出来的内存不会自动清零，万一某次插入逻辑没有覆盖 next，垃圾地址就会顺着链表跑，到时候查 bug 查到你怀疑人生。创建一个节点就初始化好所有字段，是链表代码最基础的自保手段。

4.2 从寄存运行结果里看到的“逆序”性质

逐行看 main 的运行过程，逆序就变得非常直观。

第一次插入 10，此时 head 还是 NULL，newNode->next = *head让 10 的 next 指向 NULL，所以链表是10 -> NULL。

第二次插入 20，20 的 next 指向当时的 head，也就是 10。链表变成20 -> 10 -> NULL。新节点 20 稳稳地站在最前面，10 被挤到第二位。

第三次插入 30，同理，30 抢到最前面，20 和 10 往后挪，链表变成30 -> 20 -> 10 -> NULL。

最终，插入顺序 10、20、30、40、50，链表的实际顺序变成了 50、40、30、20、10。每一轮新插入的节点都像“插队”的人，排到第一位的同时，把前面所有人往队伍后面压。先来的 10 到最后反而成了队尾。

这个性质是头插法的宿命，不是 bug。如果你需要的是一个和输入顺序一致的链表，就别用头插法建表，老老实实用尾插法，或者建完表后再做一次逆置。反过来，如果你就是想倒着建表，“用头插法输入一串数据，然后从头遍历输出”就是一种最简单的思路，很多“从尾到头打印链表”的题目都能用它秒解。

4.3 一个容易被课设和 oj 误判的经典行为

头插法的逆序特性经常害人“被挂”。我帮人调试过不少课程设计代码，好多次都是学生用头插法建表，结果打印出来的数据和输入顺序相反。老师一看就说程序错了，学生也是一脸委屈——明明代码逻辑没问题。

这个事说到底是一个语义问题，不是技术问题。在课设题目里，如果要求“创建一个单链表并输出”，如果题面没有明确建表方式，默认应该保持输入顺序，那就得用尾插法；如果题目明确说“用头插法”，那么输出倒序是预期结果，不算错。放进 OJ 或力扣题里，题目描述通常会写明“给定一个链表”或者“请你按顺序创建一个链表”，这时你拿头插法去建，顺序铁定反，判题必然 WA。

我给个实用的判断标准：你创建链表时是不是需要“把用户输入顺序保留下来”？需要，就用尾插法；不需要，或者题目明确要求逆序、要求从头部快速插入，那就放心用头插法。代码本身没有对错，用错场景才是问题。

5. 最容易踩的四个雷：从段错误到死循环的完整排查

5.1 雷区一：忘记初始化头指针

不带头结点的链表，头指针必须初始化为 NULL。这行代码看起来不起眼，漏掉的人非常多：

struct Node *head; // 错误！没有初始化为 NULL insertAtHead(&head, 10);

局部变量不初始化，里面是个随机值，可能是 0，也可能是内存里任意一个地址。第一次头插时，newNode->next = *head会把 head 里的垃圾值复制给新节点，链表的第一条指针就指向了一个不可控的位置。最后遍历时，程序顺着一个野地址往下跳，大概率直接段错误。

排查这个雷很简单：在 main 开头写struct Node *head = NULL;。如果是带头结点的链表，则要写struct Node *head = createNode(-1);，让 head 明确指向哨兵。任何“先声明、后使用”的指针，都要在一开始就给它一个确定的身份。空指针在链表里不是“没有”，而是“链表的终点”，它非常有用。

5.2 雷区二：用局部变量代替 malloc

还有一个初学者特别容易踩的坑，就是用栈上的局部变量当节点。错误代码大概长这样：

void badInsert(struct Node **head, int value) { struct Node node; // 局部变量，生命周期只在函数内 node.data = value; node.next = *head; *head = &node; // 把局部变量地址给了外部 }

这段代码看起来甚至“更简单”，不用 malloc 也不用释放。但问题是，node是函数里的局部变量，存储在栈上。函数执行完返回时，栈空间被回收，*head保存的是一个已经失效的地址，这就是悬空指针。之后任何访问head->data的操作都是未定义行为。运气好打印出奇怪的值，运气不好整个程序崩掉。

为什么必须用 malloc？因为只有 malloc 出来的对象在堆上，生命周期不受函数返回影响，它可以“活”到你手动free的那一天。链表的节点必须保证在函数外部依然有效，所以从这一点来说，所有节点都必须来自动态分配。写链表代码之前，先把“栈上变量不能用”这个观念立起来，能避免一大半内存相关的崩溃。释放也是一样的道理，free之后那个节点就没了，千万别再通过保留的旧地址去访问。

5.3 雷区三：两步操作顺序写反，链表直接断掉

前面第 2.3 节已经推演过顺序写反的后果，这里从调试角度再说一遍现象。

顺序写反最常见的现象有两种。第一种，链表打印出来只有最后一个节点，再往下访问就崩溃。原因是原来的 head 被覆盖，旧链丢失，新节点成了“孤儿”。第二种，打印同一个值无限循环，屏幕疯狂刷同一个数字。原因是 newNode->next 指向了自己，形成自环，遍历永远走不到 NULL。

遇到这两种现象，第一反应就应该是检查头插的核心三行代码。正确的形态永远是：

newNode->next = *head; // 先把旧链的头部地址保存到新节点 *head = newNode; // 再更新头指针

只要看到*head = newNode写在newNode->next = *head前面，不管当时觉得多顺，直接改过来。这个原则不光适用于头插，也适用于任何需要“在某个位置之前插入节点”的操作：先在 next 链上做“搭桥”，然后再修改前驱或头指针，顺序永远不能颠倒。

5.4 雷区四：释放链表时顺序错误，二次 free 或断链

链表用完之后要释放内存，这一步在实验报告里经常被忽视，但只要写了，就有不少人写错：

// 错误写法 void badFreeList(struct Node *head) { while (head != NULL) { free(head); head = head->next; // 错：head 已经被 free 掉了 } }

free(head)执行之后，head 指向的那块内存已经归还给系统，再去访问head->next就是访问已释放的内存，完全不可控。更严重的情况是，如果编译器或系统在那块内存上做了回收，你读到的 next 可能是垃圾值，遍历会跑到未知地带，最后在 free 时二次释放，程序直接崩溃。

正确的顺序是：先用临时变量保存 next，再释放当前节点，最后移动 head：

void freeList(struct Node *head) { while (head != NULL) { struct Node *tmp = head->next; // 先保存下一个节点 free(head); // 再释放当前节点 head = tmp; // 最后更新 head } }

释放的顺序和访问的顺序正好相反，这就像拆一个书架，你要先搬走最上面那层的东西，才敢把架子往后撤，不然整个架子都会塌下来。任何“边遍历边删除”的操作，都得先留好退路。

5.5 一次真实段错误的排查链路

上面几个雷是单独出现的，但真实世界里它们经常一起发作，现象也只有一句“segment fault”。我拿一个实际案例讲讲排查链路，这个过程比答案本身更有价值。

有个同学说他的链表程序一运行就报段错误，代码贴出来一看，核心逻辑就是头插，但死活跑不对。我让他按下面顺序查。

第一步，定位崩溃发生在哪一段。最简单粗暴的办法是在 insertAtHead 函数末尾和 printList 的开头分别加一行printf("到这里了吗\n")。运行后发现，insert 执行完、printList 打印出第一个节点之后程序才崩。这基本可以判断，节点本身建好了，但第一个节点的 next 指向了非法地址。

第二步，打印关键变量的地址。在 insertAtHead 里加上printf("newNode = %p, oldHead = %p\n", newNode, *head);，再用 gdb 跑一次：

gdb ./a.out run backtrace

gdb 的backtrace立刻指出了崩溃点在 printList 的 while 循环里，并且p的值是一个很怪异的地址。再把 main 里 head 的初始值打出来，发现是一个随机的大数，而不是 0。问题瞬间定位清楚：main 里忘写struct Node *head = NULL;了。

第三步，把初始化补上，重跑，程序正常。整个排查过程其实不到五分钟，核心思路是“先定位崩溃位置，再判断是哪个指针出了问题，最后追溯来源”。链表问题九成以上都是指针指向了错误的地方，不要盯着屏幕空想，用 printf 或者 gdb 把每一步的指针地址打出来，问题会自己现形。

6. 复杂度与应用场景：学了头插法接下来能干什么

6.1 时间与空间复杂度：O(1) 带来的优势

单次头插的时间复杂度是 O(1)，原因很简单：它不需要遍历，不管链表里有一百个节点还是一百万个节点，插入过程都只改两个指针。相比尾插法在不维护尾指针时需要 O(n) 的时间遍历到尾部，头插在“只建表不看顺序”的场景下优势非常明显。

用头插法建立含 n 个节点的链表，总时间就是 n 次 O(1)，合计 O(n)。如果改用不维护尾指针的尾插法，每次都要从头走到底，总时间是 O(n²)，数据量一大差距就出来了。空间方面，每个节点需要常数级别的额外空间，n 个节点就是 O(n)。这一点平凡，但值得说清楚：链表不是省空间的结构，它牺牲指针空间换取操作的灵活性，头插法是这种灵活性的极致体现。

6.2 邻接表建图为什么偏爱头插

学完链表头插法，你会在图论里再次遇到它，这就是邻接表。

图的邻接表存储，每个顶点都挂一条链表，链表里存的是它能直接到达的邻居。向一个顶点添加新邻居时，最直接的做法就是往这条链表的头部插。原因和前面反复强调的完全一致：插入 O(1)，不需要遍历到链表尾部，也不需要为每个顶点额外维护一个尾指针。

一个典型的有向图加边操作长这样：

void addEdge(struct Node **adj, int u, int v) { struct Node *newNode = createNode(v); newNode->next = adj[u]; adj[u] = newNode; }

你会发现，这跟头插法的结构几乎一模一样，只是 head 从“一个链表的头”变成了“顶点 u 对应链表的头”。BFS、DFS 遍历图的时候，通常不关心一个顶点的邻接顺序，所以头插法产生的“反向邻接顺序”在绝大多数场景下都无伤大雅，换来的是建图的高效。数据结构课程里图和链表就这么自然地串起来了。

6.3 链表逆置的秒解方案：本质还是头插

头插法最漂亮的延伸应用，是链表逆置。你可能在各种题解里见过“三指针反转链表”，看代码晕晕乎乎，其实它的本质就是一趟头插法。

思路是这样：准备一个新的空链表，然后遍历原链表，每遇到一个节点，就把它整个“拆”下来，头插进新链表。由于头插的逆序特性，新链表正好是原链表反过来：

struct Node* reverseList(struct Node *head) { struct Node *newHead = NULL; while (head != NULL) { struct Node *next = head->next; // 先保存原链的下一个节点 head->next = newHead; // 把当前节点头插进新链 newHead = head; // 新链的头更新 head = next; // 继续处理原链的下一个 } return newHead; }

把目光聚焦到循环里的两行head->next = newHead; newHead = head;，这不就是newNode->next = *head; *head = newNode;吗？连头插法那个“先接后断”的顺序都没变。所以 408 卷子里线性表大题考的“链表逆置”，如果你能一眼看到头插法的影子，写起来会顺手很多，心里也更有底。

6.4 栈、任务队列和更多“只关心头部”的场景

头插法最对口的场景，永远是那些只关心头部增删的数据结构。最典型的是栈：栈的链表实现，入栈就是头插，出栈就是删除第一个节点。链表实现的栈天然不需要哨兵节点，也天然没有满栈的概念，只要内存够就可以一直压栈。

很多“最近访问”类型的缓存结构，也会用类似思路维护一个热度链表：新的访问记录放在最前面，最久没用的记录被挤到尾部，淘汰时直接删尾巴。虽然真正落地的 LRU 一般用双向链表方便移动节点，但“新数据往头部塞”这个思想，源头就是头插法。

学完头插法，你不只是学会了一种插入方式，更是掌握了一个重要的思维模式：在不需要保序的场景里，与其花时间去定位尾部插入，不如用 O(1) 的成本直接插到头部，把顺序问题交给后续处理或干脆忽略。这个判断能力，比记住三行代码本身更值钱。

最后说句实在话。头插法不是看会的，是敲会的。如果你现在正对着教材发呆，不如直接把第 4 章的代码敲进编译器，把输出结果跟文中的运行结果对一下；再把*head = newNode和newNode->next = *head两句换一下顺序，亲眼看一次断链和死循环是什么效果。我在带学生做课程设计时，常让他们顺手把带头结点和不带头结点两种写法都试一遍，对比空表插入时哪段代码更省心。这种对比不花多少时间，但对理解“头指针是什么、哨兵节点是什么”特别有帮助。这两步做完，头插法就算真正长在你脑子里了。