企业官网建设流程全解析

直接说结论：链表这玩意儿，是C语言学习路上绕不过去的坎，也是区分“会写C语法”和“懂C语言数据结构”的一道分水岭。很多人学完指针、结构体、动态内存分配，觉得自己会了，一到写链表就卡壳。头插尾插搞反、遍历条件写错、free之后没置NULL、内存泄漏查半天……这些都是学链表时的经典名场面。这篇文章就用最简单的版本，把单向链表和单向循环链表从头到尾撸一遍，代码可以直接抄，每一步我都讲清楚为什么要这么写，以及你在自己练习时最容易踩哪些坑。适合刚学完指针和结构体、准备啃数据结构的C语言新手，也适合考试前想快速过一遍链表核心操作的兄弟。

1. 先想清楚：链表到底解决什么问题

1.1 从数组到链表的必然性

很多人第一门语言学的就是C，接触的第一个数据结构就是数组。数组用起来确实简单，int a[100]，一个循环就能遍历，下标访问还快。但数组的毛病也很明显：长度写死了，存满了就得换大数组，数据少了又浪费空间；往中间插入一个元素，后面的全得往后挪，删除也一样，成本很高。

链表就是冲着这两个痛点来的。它不要求元素在内存里连续存放，每个节点都是独立malloc出来的，用一个指针串起下一个节点。想插一个节点？改两条指针就行，不需要挪数据。想扩容？再malloc一个节点挂上就是。代价是没法按下标直接访问，想找第5个节点，得从头往后走5步。

这个“空间换时间、灵活换随机访问”的取舍，是整个数据结构的核心思想。

1.2 单向链表和单向循环链表的关系

单向链表是最基础的形态：每个节点只有一个next指针指向后继节点，最后一个节点的next指向NULL，表示“到头了”。

单向循环链表就是在此基础上做了一个小修改：让最后一个节点的next不再指向NULL，而是指回头节点。这样一来，整条链表形成一个环，从任意节点出发，都能走回自己。

很多初学者会觉得循环链表没什么用，其实你想想操作系统里的进程调度轮转、游戏里玩家轮流操作、数据缓冲区循环覆盖读写，这些都是环形结构的典型场景。C语言课程里最经典的练习题目——约瑟夫环问题，用的就是单向循环链表。

1.3 前置知识：指针、结构体、动态内存

写链表之前，有三个前置技能点必须过关：

• 结构体定义：用struct把“数据域 + 指针域”打包成一个节点类型。
• 指针操作：理解p->next到底取的是什么，以及二级指针什么时候用得上。
• malloc和free：节点是动态分配的，谁malloc的谁负责free，这个规矩从学链表第一天就要刻在脑子里。

如果你这三点还有点虚，建议先写几个小例子练练手，再回来看这篇文章。

2. 单向链表：从零开始写一个能跑的版本

2.1 结构体定义：节点长什么样

先定义一个节点结构体，为了简单起见，数据域放一个int：

typedef struct Node { int data; /* 数据域 */ struct Node *next; /* 指针域：指向下一个节点 */ } Node;

注意这里用的是struct Node *next，不是Node *next，因为typedef还没生效，结构体内部只能用自己的完整名字。这是个很容易被忽视的小细节，自己定义链表节点时经常会在这里报编译错误。

2.2 创建节点：malloc不是随便用的

任何链表操作的第一步都是创建节点。创建节点时最容易犯的错误就是忘了判断malloc的返回值。内存分配失败返回NULL，你不做检查直接使用，程序崩溃只是时间问题。

Node *createNode(int val) { Node *newNode = (Node *)malloc(sizeof(Node)); if (newNode == NULL) { printf("内存分配失败\n"); exit(1); } newNode->data = val; newNode->next = NULL; return newNode; }

2.3 头插法：代码最简洁的插入方式

头插法的核心思想：新节点插在链表头部，成为新的头节点。头插法代码非常短，但容易在指针顺序上犯迷糊。

Node *insertAtHead(Node *head, int val) { Node *newNode = createNode(val); newNode->next = head; /* 先让新节点指向原头节点 */ head = newNode; /* 再更新头指针 */ return head; }

关键点在于newNode->next = head这一步必须在head = newNode之前完成。如果你先让head等于newNode，头指针就指向新节点了，原来的链表就找不到了，这叫“断链”，是链表操作里最经典的事故现场。

2.4 尾插法：需要遍历找到最后一个节点

尾插法要在链表末尾追加节点，需要先走到最后一个节点。最后一个节点的特征是p->next == NULL。

Node *insertAtTail(Node *head, int val) { Node *newNode = createNode(val); if (head == NULL) { head = newNode; return head; } Node *p = head; while (p->next != NULL) { p = p->next; } p->next = newNode; return head; }

这里有个边界条件必须考虑：如果链表为空，头插和尾插都是直接让头指针指向新节点。很多初学者写尾插时不写head == NULL的判断，导致空链表直接段错误，这是第一个容易踩的坑。

2.5 遍历打印：迭代法就够用

遍历的思路很简单：从头开始，每访问一个节点打印数据，然后p移动到下一个节点，直到p为NULL。

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

2.6 删除节点：必须记住前驱节点

删除节点分三种情况：删除头节点、删除中间节点、删除末尾节点。核心思路是找到“待删除节点的前一个节点”，让前一个节点的next跳过待删除节点，直指后继节点，最后free掉待删除节点。

Node *deleteNode(Node *head, int target) { Node *p = head; Node *prev = NULL; /* 头节点就是目标 */ if (p != NULL && p->data == target) { head = p->next; free(p); return head; } /* 查找目标节点，同时记录前驱 */ while (p != NULL && p->data != target) { prev = p; p = p->next; } if (p == NULL) { printf("没找到目标节点\n"); return head; } prev->next = p->next; free(p); return head; }

说一句题外话：删除节点时，用prev记录前驱这个技巧，在双向链表、二叉树删除、LRU缓存等很多场景都会用到。它不是冷门技巧，而是链表算法的通用基本功，值得多写几遍形成肌肉记忆。

2.7 销毁链表：释放每个节点的内存

写链表时大家最容易忽略的操作就是销毁链表。程序结束前要把所有malloc出来的节点都free掉，否则就是内存泄漏。

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

这里有两点要注意：第一，free之前必须先把下一个节点的地址保存下来；第二，你如果把这个函数用在循环链表上，while (p != NULL)会死循环，因为循环链表里next永远不会为NULL——这一点等会儿讲到循环链表的时候再具体说。

2.8 一个完整的单向链表功能演示

把上面的函数拼在一起，写一个简单的菜单程序，方便你对照着编译测一下：

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int val) { Node *newNode = (Node *)malloc(sizeof(Node)); if (newNode == NULL) { printf("内存分配失败\n"); exit(1); } newNode->data = val; newNode->next = NULL; return newNode; } Node *insertAtHead(Node *head, int val) { Node *newNode = createNode(val); newNode->next = head; head = newNode; return head; } Node *insertAtTail(Node *head, int val) { Node *newNode = createNode(val); if (head == NULL) { head = newNode; return head; } Node *p = head; while (p->next != NULL) { p = p->next; } p->next = newNode; return head; } void printList(Node *head) { Node *p = head; while (p != NULL) { printf("%d -> ", p->data); p = p->next; } printf("NULL\n"); } Node *deleteNode(Node *head, int target) { Node *p = head; Node *prev = NULL; if (p != NULL && p->data == target) { head = p->next; free(p); return head; } while (p != NULL && p->data != target) { prev = p; p = p->next; } if (p == NULL) { printf("没找到目标节点\n"); return head; } prev->next = p->next; free(p); return head; } void freeList(Node *head) { Node *p = head; while (p != NULL) { Node *tmp = p; p = p->next; free(tmp); } } int main(void) { Node *head = NULL; head = insertAtTail(head, 10); head = insertAtTail(head, 20); head = insertAtTail(head, 30); head = insertAtHead(head, 5); printList(head); head = deleteNode(head, 20); printList(head); freeList(head); return 0; }

编译运行一下：

gcc -Wall -o demo demo.c ./demo

输出结果为：

5 -> 10 -> 20 -> 30 -> NULL 5 -> 10 -> 30 -> NULL

注意编译时别忘了加-Wall选项，让编译器把警告都打出来。写链表代码遇到编译警告一定要重视，很多警告背后就是野指针或类型不匹配的隐患。

3. 单向循环链表：只改一处next的指向

3.1 循环链表和单向链表的核心区别

单向循环链表和普通单向链表，结构体定义其实是一样的，就一个区别：普通单向链表最后一个节点的next指向NULL，循环链表的最后一个节点next指向头节点。

操作上的差异主要体现在两点：遍历的终止条件从p->next != NULL变成了p->next != head（或者用计数器控制循环次数）；删除、查找时对空链表和单节点链表的判断要更小心。

3.2 约瑟夫环：循环链表最经典的场景

约瑟夫环这个问题，我第一次在翁恺老师的C语言练习题里看到的时候就印象深刻。问题大意是：N个人围成一圈，从第1个人开始报数，报到M的人出列，然后从下一个人开始重新报数，如此循环，直到所有人出列，求最后剩下的那个人（或者输出完整的出列顺序）。

围成一圈、循环报数、淘汰出列——这不就是循环链表最自然的应用场景吗？每个人是链表里的一个节点，报数就是沿链表走下去，报到M就删除当前节点，然后继续。

3.3 约瑟夫环的C语言实现

下面这个实现，我尽量写得贴近真实项目习惯：创建一个规模为N的循环链表，模拟报数M出列的过程，打印出列顺序，最后打印幸存者。

#include <stdio.h> #include <stdlib.h> typedef struct Node { int data; struct Node *next; } Node; Node *createNode(int val) { Node *newNode = (Node *)malloc(sizeof(Node)); if (newNode == NULL) { printf("内存分配失败\n"); exit(1); } newNode->data = val; newNode->next = NULL; return newNode; } /* 创建包含n个节点的循环链表，数据为1到n */ Node *createCircularList(int n) { Node *head = NULL; Node *tail = NULL; for (int i = 1; i <= n; i++) { Node *newNode = createNode(i); if (head == NULL) { head = newNode; tail = newNode; } else { tail->next = newNode; tail = newNode; } } tail->next = head; /* 关键：让末尾节点指向头节点，形成环 */ return head; } void josephus(Node *head, int m) { Node *p = head; Node *prev = NULL; /* 先让prev指向p的前驱。 对循环链表来说，从头节点出发走一圈能回到头节点， 所以最自然的做法是：先让prev走到p的前一个节点。 */ prev = p; while (prev->next != p) { prev = prev->next; } printf("出列顺序："); while (p->next != p) { /* 只要环里还有多于1个节点 */ /* 报数1到m-1，走到要删除的节点 */ for (int i = 1; i < m; i++) { prev = p; p = p->next; } printf("%d ", p->data); /* 删除当前节点 */ prev->next = p->next; free(p); p = prev->next; /* 从被删节点的下一个节点继续报数 */ } printf("\n最后剩下：%d\n", p->data); free(p); } int main(void) { /* 例如：5个人，报到3出列 */ Node *head = createCircularList(5); josephus(head, 3); return 0; }

运行结果：

出列顺序：3 1 5 2 最后剩下：4

你可以自己拿纸笔画一画验证一下，看看这个结果对不对。这个模拟过程建议亲手走一遍，比看十遍代码都管用。

3.4 循环链表的遍历和销毁要注意什么

循环链表的遍历不能再用while (p != NULL)了，因为环里永远不会出现NULL。常见做法是：从头节点开始，用do-while先执行一次再判断是否回到头节点，或者遍历到p->next == head时停止。

销毁循环链表也要特别处理：先保存头节点，然后从头节点开始遍历，当p->next != head时不断free当前节点，循环结束再free头节点。如果你图省事用单向链表的销毁函数去处理循环链表，结果就是一个死循环，程序卡死，这也是很多初学者踩过的坑。

3.5 循环链表的一个实用改造：尾指针

刚才创建循环链表的时候，其实需要保留tail尾节点来快速接入新节点。稍微优化一下，可以不在链表里存储头指针，而是存储尾指针——也就是让tail->next指向head。

为什么要这么做？因为有了尾指针，在末尾插入一个节点就变成了O(1)操作，不用再从头遍历到末尾。而通过tail->next就能快速拿到头节点。这是循环链表在实际工程里非常常见的一个改造方向，面试时如果你能主动提到这一点，印象分会好很多。

4. 常见问题与排查技巧实录

4.1 野指针：free之后不置NULL的后果

我在带新人写代码时，见过太多类似的段错误。典型例子是删除节点时，delete函数里free(p)了，但main函数的某个指针还保存着被删节点的地址，继续用这个指针去访问数据，程序不出问题才怪。

我自己的习惯是：每次free一个指针之后，立刻把它置为NULL。虽然C语言里没有“强制必须置NULL”的规则，但不置NULL的话，这个指针就成了野指针。你留着它，以后可能引发“悬空指针”问题，排查起来非常痛苦。

4.2 断链：修改指针顺序的黄金法则

链表操作的一切错误，归结到最后都是“指针连错了”。有一个黄金法则可以少踩无数坑：先接新的，再拆旧的。

以头插法为例，先让新节点的next指向原来的头节点，再把head更新为新节点。如果你先改head，就相当于把原来的链表给丢了，后面的节点找不回来了——这就是“断链”。

凡是涉及插入、删除的操作，写代码前先在心里把指针的先后顺序过一遍，养成这个习惯之后，链表相关的bug至少能减少一半。

4.3 空链表与单节点：边界条件最容易漏

链表里最简单也最容易被忽略的两个边界情况就是空链表和只有一个节点的链表。

空链表做任何操作之前都要先判断head != NULL。很多初学者在写删除函数的时候，上来就判断head->data是否等于目标值，如果head是NULL，这一步直接段错误。

单节点链表在删除时也有坑。如果你删的是唯一的那个节点，删除之后head应该变成NULL，而不是继续指向那个已被free的内存。循环链表里单节点更是特殊——比如刚才约瑟夫环的while (p->next != p)循环，小于等于1个人时整个循环体根本不会进去，逻辑就要额外处理。

建议你在写完链表函数后，专门用“空链表、单节点链表、双节点链表”三组数据各测一遍，这三个边界能过，说明函数基本是稳的。

4.4 内存泄漏：用工具帮你查

C语言没有自动垃圾回收，全靠自觉。写链表程序，最直接的检查方式是valgrind：

valgrind --leak-check=full ./demo

如果输出中出现了“definitely lost”，说明你有malloc没有对应的free。这种问题堆得多了，程序长期跑下来内存会有明显增长，这在嵌入式环境下是非常致命的。

如果没有条件用valgrind，也可以自己在程序里加统计信息：比如每次createNode时全局计数+1，每次free时全局计数-1，最后打印计数是否为0。这种“土办法”在面试现场反而是加分项，能体现出你对内存管理的理解。

4.5 调试笨办法：画图比加日志快

看指针代码，很多人第一反应是加printf输出日志。我的经验是，链表这种几步一个指针变更的逻辑，打印一屏日志远不如拿张纸画个链表图来得快。

把每个节点的data、next箭头都画下来，然后一步步执行你的代码，用笔把箭头改过来。循环几次之后你会发现，很多bug其实在你动笔之前就已经能预判到了。这个方法听起来土，但真的比瞪眼干看代码高效太多。

5. 写出高质量的链表代码

5.1 防御性编程：输入参数先判空

一个合格的函数，第一步应该是检查传入参数是否合法。比如遍历打印函数，如果head为NULL，直接返回。删除函数如果head为NULL或者目标值不存在，也要有相应的处理逻辑，不能默默崩溃或输出错误结果。

这些判断看似多余，但在实际项目中，链表往往在很复杂的业务流程里被反复调用，输入不可控是常态。你不写防御性判断，当场可能没问题，一旦数据异常，段错误直接甩给你，连个错误提示都没有。

5.2 函数拆分：一个函数只干一件事

观察我上面写的代码，你会发现每个函数都很短：createNode只负责创建节点，insertAtHead只负责头插，printList只负责遍历。这就是函数拆分的意义所在。

很多初学者喜欢把创建、遍历、删除全塞进一个main函数里，几百行代码连成一片。这种代码自己调试都费劲，更别说别人看了。分段拆细之后，每个函数都能单独验证，定位问题也快得多。

5.3 面试和考试里高频考法

链表是各大笔试面试的基础题，题型我列几个常见的：

• 反转一个单向链表
• 判断链表中是否有环（快慢指针法）
• 合并两个有序链表
• 找链表的中间节点（快慢指针法）
• 约瑟夫环问题（循环链表）
• 链表排序

这些题目我在面试中见过不少，基本功都在于你今天对单向链表和循环链表的理解。有的同学背题能背下来，稍微变一下条件就懵，本质原因还是对指针操作没形成直觉。

结尾

说实话，链表这套东西，光看文章是不够的。我自己的体会是，把上面这几十行代码照着敲一遍，再自己动手画一遍指针指向图，最后用valgrind查一遍内存泄漏，这一套流程走完，你对指针和动态内存的理解会上一个台阶。建议你写完这个简单版之后，再去试试反转链表、快慢指针找环这些进阶题目，你会发现它们其实都是基于“先接新的，再拆旧的”“记住前驱节点”“边界条件先判断”这几个最朴素的规律。写链表出错不可怕，可怕的是一直不自己动手写。