企业官网建设流程全解析

C语言里写单链表，最折磨人的往往不是语法，而是指针。一个节点结构体看十遍都能懂，一动手创建、插入、删除，就开始各种崩溃：要么段错误，要么链表打印到一半就不动了，要么明明插入了节点，遍历时却找不到。这些问题的根源，几乎都出在“指针的指向顺序”和“谁持有头指针”这两件事上。

我接触过不少刚开始学习单链表的同学，也帮人排查过不少链表代码。今天就把单链表相关的核心操作从头到尾拆开讲一遍，包括结构定义、建表、遍历、查找、插入、删除、反转和内存释放，每个操作都会讲清楚“为什么要这么写”，而不是只丢一段能跑的代码。看完之后，你自己动手写一个单链表应该会很顺，甚至能一眼看出别人的代码问题出在哪。

1. 为什么我劝你先画图，再写单链表代码

很多人写链表一上来就敲代码，结果每次都在同一个地方翻车。我的建议是：先在纸上画节点，用方框代表节点，用箭头代表 next 指针，把所有操作都“走”一遍，再回到代码里验证。C 语言链表里所有的修改，本质上都是“箭头”的重新指向，代码只是把这个过程翻译给编译器。

1.1 节点的结构定义，核心只有两个成员

单链表节点的定义一般长这样：

typedef struct Node { int data; struct Node *next; } Node;

这里的struct Node *next就是连接下一个节点的“箭头”。注意一个细节：结构体内部不能直接写成Node *next，因为在类型声明还没有结束的时候，Node这个别名还不存在。所以必须用完整的struct Node *next。这个细节平时不显眼，但初学者经常在这里卡住编译错误。

data是节点携带的数据，这里用的int，实际项目里可以换成任意类型：一个结构体、一个指针、一个字符串缓冲区，都可以。但节点本身的结构不会变：一个存储区，一个指向下一个节点的指针。

1.2 链表的“链表属性”由谁承载：头指针是入口

单链表里真正重要的不是节点，而是头指针。头指针是一个指向第一个节点的指针变量，它本身不是节点，只是记录“第一个节点在哪”。当链表为空时，头指针的值是NULL。

很多人会把“头指针”和“头节点”混在一起。头节点是一个不存有效数据的哨兵节点，用来简化操作；而头指针只是一个变量。我们这里讲的是最朴素的单链表：没有头节点，头指针直接指向第一个有效节点。这种写法最贴近教材，也最能暴露问题，因为头指针在插入和删除头部时经常需要修改，写数组习惯了的人特别容易忽略这一点。

一句话记住：头指针是链表的“身份证”。只要头指针丢了，整个链表就找不回来了。所以写任何链表操作前，先确认你手里的head是持久的、还是会被改掉的副本。

2. 建表操作的两种姿势：头插法与尾插法

创建链表有两种典型做法：头插法和尾插法。同样是插入节点，得到的结果顺序完全不同，背后的指针操作也有区别。

2.1 头插法：三行代码，但结果顺序是反的

头插法每次都把新节点插到链表最前面，代码很短：

Node *head = NULL; for (int i = 1; i <= 5; i++) { Node *p = (Node *)malloc(sizeof(Node)); p->data = i; p->next = head; head = p; }

核心逻辑就两句：p->next = head;然后head = p;。第一次插入，head是NULL，所以第一个节点的next是NULL。第二次插入，新节点的next指向原来的第一个节点，然后head重新指向新节点。这样一路插下来，链表的顺序和输入顺序是反的：如果你依次输入 1、2、3、4、5，最终遍历得到的是 5、4、3、2、1。

头插法最常犯的错是顺序写反：有人先写head = p;，再写p->next = head;。这时候问题就大了——head已经指向了p，再接p->next = head等于让p->next指向自己，链表直接变成环。画一下图就会发现，必须先让新节点接住原来的链表，再移动head。

2.2 尾插法：尾指针的维护是细节重点

尾插法会让链表顺序和输入顺序一致，这也是实际项目里更常见的行为。朴素写法是每次从头遍历到尾部再插入，但那样复杂度是 O(n²)。正确做法是用一个tail指针始终指向最后一个节点：

Node *head = NULL; Node *tail = NULL; for (int i = 1; i <= 5; i++) { Node *p = (Node *)malloc(sizeof(Node)); p->data = i; p->next = NULL; if (tail == NULL) { head = p; tail = p; } else { tail->next = p; tail = p; } }

第一个节点插入时，head和tail都要指向它，因为此时链表里只有一个节点，它既是头也是尾。之后每插入一个节点，先把新节点挂到tail->next上，再更新tail。

这里有个常见错误：只写了tail->next = p;，忘了tail = p;。结果第二次插入时，新节点总是挂在第二个节点后面，链表变成一条“挂歪”的结构，遍历时会发现后面的节点全丢了。画图的时候，每次插入后都要重新问自己：现在这个链表的最后一个节点到底是谁？tail是否指向它？

2.3 为什么建表函数必须返回 Node *

看到这里，有同学会想：“我写个函数void createList(Node *head)，在函数里给 head 分配节点不就行了？”听起来合理，实际上不行。C 函数的参数是值传递，head是实参的一份拷贝，你在函数里修改head，外部原来的变量没有任何变化。典型的错误代码长这样：

void createList(Node *head) { head = (Node *)malloc(sizeof(Node)); head->data = 1; head->next = NULL; } int main() { Node *head = NULL; createList(head); // head 仍然等于 NULL }

调用结束后，外部head还是NULL，因为函数里修改的是形参head。解决办法有两个：一是让函数返回新的头指针，外部接收返回值；二是传入头指针的地址，也就是Node **head，在函数里通过*head修改外部变量。我建议做练习时两个都写一遍，能加深对指针传递的理解。

Node *createListByReturn(int arr[], int n) { Node *head = NULL, *tail = NULL; for (int i = 0; i < n; i++) { Node *p = (Node *)malloc(sizeof(Node)); p->data = arr[i]; p->next = NULL; if (tail == NULL) { head = tail = p; } else { tail->next = p; tail = p; } } return head; }

2.4 堆内存和栈内存：你的临时节点为什么活不过函数

创建节点必须用malloc，这是新手最容易偷懒的地方。有人图省事，在函数里定义一个局部变量Node tmp; tmp.data = 1; tmp.next = NULL;，然后返回&tmp。这是悬空指针的经典来源：局部变量在函数返回后就被回收了，外面的代码虽然还握着这个地址，但里面的数据随时会被其他调用覆盖。

malloc申请的内存来自堆，函数结束后不会自动消失，需要手动free释放。这就是链表代码里“每个 malloc 都要有对应的 free”这条铁律的原因。练习时不妨在每次malloc后检查返回值是否为NULL，虽然平时不太会失败，但这是好习惯。

3. 遍历、查找与长度统计：把链表走一遍需要留神的三件事

链表不像数组，不能通过下标直接访问第 k 个元素。所有按位置或按值的操作，都得从head开始一个一个往下走。这个“走”的过程看似简单，但有三个细节很值得注意。

3.1 循环条件 while (cur != NULL) 和 while (cur->next != NULL) 的差别

遍历链表最常见的是这种写法：

void printList(Node *head) { Node *cur = head; while (cur != NULL) { printf("%d ", cur->data); cur = cur->next; } printf("\n"); }

条件cur != NULL意味着循环会走到最后一个节点之后才停，适合访问每个节点的数据。如果你需要“停在最后一个节点上”，比如想在尾部插入，那么条件应该换成cur->next != NULL：

Node *cur = head; if (cur == NULL) { // 空链表单独处理 } while (cur->next != NULL) { cur = cur->next; } // 现在 cur 是最后一个节点，cur->next == NULL

这两个条件的差别，说到底是“你想在哪种状态停下”。很多人把cur->next != NULL用在访问数据的遍历上，结果漏掉最后一个节点，因为最后一个节点的next是NULL，循环提前结束。这是非常隐蔽的错误。

3.2 按值查找返回什么最合理

按值查找的经典实现：

Node *findByValue(Node *head, int target) { Node *cur = head; while (cur != NULL) { if (cur->data == target) { return cur; } cur = cur->next; } return NULL; }

这里我建议返回Node *，而不是返回一个int下标。因为返回节点指针以后，你既能访问数据，也能直接对这个节点做修改，还能基于它继续做插入、删除操作。如果返回下标，单链表里想“根据下标找到节点”又得重新遍历一遍。实际工程里还有可能返回节点在链表中的“前驱节点”，这涉及到删除操作，下一部分会讲到。

这里注意一个语义：如果链表里有多个相同的值，findByValue返回第一个匹配项。需要找最后一个或者所有匹配项的话，遍历条件要做相应调整，或者用一个容器收集结果。

3.3 统计长度时的空链表特判

计算链表长度：

int listLength(Node *head) { int count = 0; Node *cur = head; while (cur != NULL) { count++; cur = cur->next; } return count; }

这个写法对空链表是安全的：head为NULL时循环一次也不执行，返回 0。我见过有人把条件写成while (cur->next != NULL)，然后空链表一进来就访问NULL->next，直接段错误。任何链表操作，第一步都要先问“我拿到的是不是 NULL”，这是保命习惯。

4. 插入和删除：改指针的顺序错一个，链表就断了

插入和删除是单链表操作的核心难点，也是最容易产生 bug 的地方。核心规律其实一句话：先把新节点和右边接上，再动左边的指针。这句话可以解决大部分插入问题。

4.1 头部插入/删除：头指针本身也是“节点指针”

头部插入我们已经在建表时看过了：

p->next = head; head = p;

头部删除更简单，但要小心一个“看起来没问题”的写法：

// 正确：先保存旧第一个节点，再移动 head，最后 free Node *old = head; head = head->next; free(old);

有人会写成free(head); head = head->next;，这实际上是先释放了当前头节点，然后又去读它的next字段，属于对已释放内存的访问，行为未定义。正确的顺序永远是：先通过局部变量把下一步要用的指针存下来，再执行释放或改写。头部操作之所以要单独讲，是因为它动的是head本身，而其他位置动的是某个节点的next字段。

4.2 中间插入：先让新节点的 next 就位，再动旧节点

假设现在有一个节点pos，要把新节点p插到pos后面：

p->next = pos->next; pos->next = p;

就这么两行，顺序不能反。如果你先写pos->next = p;，那你已经把pos后面的链表“丢”了，因为pos->next已经被覆盖成新节点，原来的后续节点没有任何指针能到达。接下来再写p->next = pos->next;，等于让p->next指向p自己，链表当场变成环。所以关键原则是先备份右边，再接上右边，最后更新左边的指针。

如果要在指定位置之前插入，那就得先找到目标位置的前驱节点。这正是“找前驱”的用武之地。从head出发，用prev和cur两个指针一前一后移动，当cur到达目标位置时，prev就是前驱。然后执行同样的两步：p->next = prev->next; prev->next = p;。

4.3 删除节点：让前驱绕过目标节点，并保存后驱

删除某个节点，本质上是让它的前驱越过它，直接指向它的后驱。如果已知前驱是prev，要删除prev->next，核心代码是：

Node *target = prev->next; prev->next = target->next; free(target);

但这里有个更隐蔽的坑：如果删的是头节点，prev根本不存在，你得单独处理：

void deleteHead(Node **ppHead) { if (*ppHead == NULL) return; Node *old = *ppHead; *ppHead = old->next; free(old); }

删除中间节点时，很多初学者会犯“先 free 再去改写指针”的错。比如free(target); prev->next = target->next;，这条语句在free(target)之后访问target->next，target 的内存已经归还给系统，里面的值随时可能被改写，结果不可预测。规范做法是先记录target->next，再free(target)。

还要注意一个问题：单链表没有前驱查询能力，所以删除“某个给定的指针节点”时，必须从头遍历找到它的前驱。这也是单链表比双链表麻烦的地方。如果你频繁需要“给定节点删除它”，双链表会舒服很多，后面会展开聊。

4.4 按值删除的常见路径：prev 指针的工作方式

按值删除的完整逻辑，一般写成这样：

void deleteByValue(Node **ppHead, int target) { Node *prev = NULL; Node *cur = *ppHead; while (cur != NULL && cur->data != target) { prev = cur; cur = cur->next; } if (cur == NULL) { return; // 没找到 } if (prev == NULL) { // 删除的是头节点 *ppHead = cur->next; } else { prev->next = cur->next; } free(cur); }

这里一定要用Node **ppHead，否则在删除头节点时无法更新外部传入的head。prev指针的用途就是记录“当前节点的前驱”，因为单链表只能往后走，不能回头看。遍历过程中prev始终比cur慢一步，当cur停下时，prev正好停在它前一个节点上。

需要注意，这个函数只删第一个匹配值。如果要删除所有匹配值，需要循环查找，每删除一个之后别急着返回，继续从当前位置向下扫描。练习时建议先实现“删一个”，再扩展成“删全部”，理解会更扎实。

5. 单链表反转：迭代画三个指针，递归理解函数栈

反转链表是单链表操作里很能考察“指针感”的题目。它并不修改数据，只是把每个节点的next方向调转。关键是过程中的指针保存：每当你改变一个节点的next，原来的下一个节点地址就丢了，必须提前存好。

5.1 迭代反转：三个指针如何初始化和移动

迭代法很好记：三个指针prev、cur、next。初始化prev = NULL，cur = head，然后在cur != NULL的循环里不断调整指向：

Node *reverseList(Node *head) { Node *prev = NULL; Node *cur = head; while (cur != NULL) { Node *next = cur->next; // 先保存后一个节点 cur->next = prev; // 把当前节点的箭头反向 prev = cur; // prev 前进一步 cur = next; // cur 前进一步 } return prev; // 原链表尾节点变成新链表头 }

很多人看不懂的是为什么要多一个next。原因是：cur->next = prev这行执行完之后，cur原来的后继就再也通过cur访问不到了，所以在改指向前必须用局部变量把next存起来。这个“先保存，再改写”的模式，和插入删除里的思路完全一致。

循环结束时，cur已经是NULL，prev指向原链表的最后一个节点。由于每个节点的箭头都被反转了，原来的尾节点现在就是新链表的头节点，所以返回prev。

5.2 递归反转：大部分人没绕明白的返回头

递归版本代码很短，但理解门槛更高：

Node *reverseRecursive(Node *p) { if (p == NULL || p->next == NULL) { return p; } Node *newHead = reverseRecursive(p->next); p->next->next = p; p->next = NULL; return newHead; }

很多人的困惑在最后一层：p是当前节点，p->next->next = p是什么意思？举个例子，链表A -> B -> C -> NULL。当函数处理到C时，C->next为NULL，直接返回C。回到B这一层时，p是B，p->next是C，p->next->next = p就是让C->next = B，于是方向变成C -> B。接着p->next = NULL，也就是让B->next断开。这时返回的newHead一直是最初的C，等递归一层层回到最外层时，新的头节点就是C，而A的next已经变成NULL。

递归反转可以理解成“先把后面的链表反向，再把当前节点挂到反转后链表的尾部”。它的缺点也很明显：链表很长时递归深度大，可能有爆栈风险。实际项目里我一般用迭代法，但递归能锻炼对“函数调用栈”的理解，作为一个思考题来做是值得的。

5.3 反转之后的头指针更新，以及内存图上发生了什么

不管用哪种反转，调用的地方都要注意重新接收返回值：

head = reverseList(head); head = reverseRecursive(head);

如果忘了用返回值更新head，你手里的头指针还是原链表的头，但原头节点现在已经变成了尾节点，它的next是NULL，一遍历就只输出一个节点。这提醒我们：链表操作里，任何可能改变头指针的函数，要么返回新头，要么用双重指针修改，二选一。

反转过程中不涉及节点的创建和销毁，所以不需要malloc和free。很多人误以为反转也要释放内存，千万不要，反转只是改指针方向。

6. 释放整表与常见崩溃排查

链表如果只 malloc 不 free，跑一次两次看不出问题，长时间运行就会内存泄漏。释放整表也有讲究，顺序错了照样出错。

6.1 freeList 的顺序为什么必须先存 next

void freeList(Node *head) { Node *cur = head; while (cur != NULL) { Node *next = cur->next; free(cur); cur = next; } }

关键就是那句Node *next = cur->next;必须先执行。free(cur)之后，cur指向的内存已经归还系统，虽然很多情况下地址里的值还在，但这是未定义行为，不应该依赖它。先保存next，再释放cur，再让cur走到next，全程不访问已释放内存。这个模式在删除单个节点时已经用过，释放整表只是把它循环化。

另外注意：freeList结束后，调用处最好把head设为NULL，否则你手里还有一个“悬空指针”，下次误用会崩得莫名其妙。有些人习惯写一个带双重指针的版本：

void freeListSafe(Node **ppHead) { freeList(*ppHead); *ppHead = NULL; }

这样调用之后，head自动变成NULL，很安全。我自己写练习代码时，经常会在free后把指针置空，虽然多写几行，但排查问题时省很多事。

6.2 三大崩溃来源：空指针、悬空指针、未初始化

我帮人排查链表代码，遇到的崩溃基本可以归成三类：

第一类：空指针访问。链表为空时还去访问head->data，或者在循环条件里用了cur->next != NULL，但cur本身就是NULL。解决办法是任何操作前先判断是否为空，循环条件写对。

第二类：悬空指针。访问已经free的内存，典型就是前面说的先释放再读next。这类 bug 很隐蔽，因为内存释放后不一定立刻被改写，可能跑好几次才出错。解决办法是养成“先存后 free”的习惯。

第三类：未初始化。malloc出来的节点，内存里的next是随机值，如果你不手动赋成NULL，遍历时可能顺着垃圾地址一路乱跑，最后段错误。所以创建节点后，一定要立刻初始化data和next。

这三种错误的共同特点是：代码本身可能能跑通一次，但换一个输入、换一个编译环境，问题就炸了。写链表代码时，建议把“每个指针字段都有确定值”当成强制约束。

6.3 一套适合练习的调试习惯：打印地址与最小用例

我在练习链表时非常依赖一个简单的调试函数：把每个节点的地址、数据和 next 指向的地址打出来。

void debugList(Node *head) { Node *cur = head; int idx = 0; while (cur != NULL) { printf("[%d] node=%p data=%d next=%p\n", idx++, (void *)cur, cur->data, (void *)cur->next); cur = cur->next; } }

打印地址的好处是，你能亲眼看到“这个节点的 next 到底指向谁”。如果发现某个节点的 next 指向自己，那你基本定位到了插入顺序写反的问题；如果 next 是垃圾地址，那就是未初始化。配合gdb或者直接printf，都能很快缩小范围。

另一个有效手段是“最小用例”。不要一上来就建一百个节点，先用三五个节点跑一个操作，人脑能跟上的规模才有调试价值。我用 3 个节点调试反转，在纸上把三个节点的 next 变化每一步都写出来，再对照debugList的输出，出错位置一目了然。

6.4 自然扩展：tail 指针、双链表、循环链表

单链表学完之后，有几个方向的扩展非常自然。

第一个方向是“如何让尾插法更快”。单纯从头遍历找尾节点是 O(n) 的，频繁尾插时整体效率不高，于是引出维护tail指针的思路，甚至可以用一个带head和tail的链表结构体来管理。

第二个方向是“如何快速找前驱”。单链表删除一个已知节点必须遍历找前驱，效率低，于是引出双向链表：每个节点多一个prev指针，删除操作从 O(n) 变成 O(1)。理解了单链表的箭头逻辑，双链表就是多维护一个反向箭头。

第三个方向是“如何让链表首尾相接”。循环链表把最后一个节点的next指向头节点，适合循环队列、约瑟夫环这类场景。单链表里如果你把tail->next = head，就得到最简单的循环链表。

这些扩展我都建议自己敲一遍。数据结构这东西，靠看是学不会的，第一次写出来有 bug 很正常，关键是能根据现象快速定位到是指针顺序问题、地址保存问题，还是初始化问题。等你把单链表这几个操作搞顺了，后面学双链表、树、图，都会感谢现在画的这几张图。