学完结构体、指针之后，就来到数据结构第一个重点：单向链表。 数组顺序存储，内存连续；链表是链式存储，内存分散，依靠指针把一个个节点串起来。 链表最大难点就是指针逻辑，写代码很容易出现段错误、内存泄漏、指针指向错乱。
一、基于链表的学生管理系统
1.知识回顾
节点结构
带头结点单链表，节点分为两部分：
- 数据域：存放业务数据，这里是学生信息（姓名、年龄、分数）
- 指针域：
next，存下一个节点的地址
头节点：不存放有效学生数据，作为链表入口。
首节点：第一个存真实业务数据的节点
尾节点：
next = NULL，代表链表结束空链表：
head->next == NULL
struct stu { char name[20]; int age; float score; }; typedef struct stu data_t; typedef struct node { data_t data; //数据域：学生信息 struct node *next; //指针域：下一个节点地址 }node_t;链表基础操作清单
- 创建空链表（malloc 头节点）
- 头插、尾插节点
- 判断链表是否为空
- 遍历打印链表
- 获取链表长度
- 根据 key 查找节点
- 修改节点数据
- 删除节点
- 菜单交互，学生管理系统业务逻辑
2.完整代码
#include <stdio.h> #include <stdlib.h> #include <string.h> struct stu { char name[20]; int age; float score; }; typedef struct stu data_t; typedef struct node { data_t data; struct node *next; }node_t; //创建带头节点空链表 node_t * linklist_create(void) { node_t * head = malloc(sizeof(node_t)); if (head==NULL) { printf("linklist_create malloc fail\n"); return NULL; } head->next = NULL; return head; } //头插新节点 int linklist_insert_head(node_t *phead,data_t *data) { if (phead == NULL) { return -1; } node_t *pnew = malloc(sizeof(node_t)); if (pnew==NULL) { return -1; } pnew->data = *data; pnew->next = phead->next; phead->next = pnew; return 0; } //判断链表是否为空 int is_empty(node_t *phead) { if (phead == NULL) { return -1; } return phead->next == NULL; } //打印单个学生 void printStu(void *p) { data_t q = ((node_t *)p)->data; printf("name = %s\n",q.name); printf("age = %d\n",q.age); printf("score= %.2f\n",q.score); } //遍历打印全部链表 int linklist_print(node_t *phead,void (*pprint)(void *)) { if (phead == NULL || is_empty(phead) == 1) { return -1; } node_t *p = phead->next; while (p!=NULL) { pprint(p); p = p->next; } putchar('\n'); return 0; } //获取链表节点个数 int length(node_t *phead) { if (phead == NULL) { return -1; } if (is_empty(phead) == 1) { return 0; } int cnt = 0; node_t *p = phead->next; while (p!=NULL) { cnt++; p = p->next; } return cnt; } //按key查找节点 node_t *linklist_find_key(node_t *phead,data_t key) { if (phead == NULL || is_empty(phead) == 1) { return NULL; } node_t *p = phead->next; while (p!= NULL) { if (memcmp(&p->data,&key,sizeof(data_t)) == 0) { return p; } p = p->next; } return NULL; } //更新节点数据 node_t *linklist_update(node_t *phead,data_t old,data_t new) { if (phead == NULL || is_empty(phead) == 1) { return NULL; } node_t *p = phead->next; while (p!= NULL) { if (memcmp(&p->data,&old,sizeof(data_t)) == 0) { p->data = new; return p; } p = p->next; } return NULL; } //头删 int linklist_delete_head(node_t *phead) { if (phead == NULL || is_empty(phead) == 1) { return -1; } node_t *p = phead->next; phead->next = p->next; free(p); p=NULL; return 0; } //打印菜单 void printMenu(void) { printf("-----------学生管理系统----------------\n"); printf(" 1.批量录入学生信息\n 2.打印学生信息\n 3.新增单个学生信息\n 4.删除头部学生信息\n 5.统计学生人数\n 6.退出\n"); printf("> "); } int main(int argc, const char *argv[]) { node_t *phead = linklist_create(); while(1) { printMenu(); int op = 0; scanf("%d",&op); switch (op) { case 1: printf("Input stu nums:"); int nums = 0; scanf("%d",&nums); int i = 0; for (i = 0; i < nums; ++i) { data_t d; printf("Input name,age,score:"); scanf("%s",d.name); scanf("%d",&d.age); scanf("%f",&d.score); linklist_insert_head(phead,&d); } break; case 2: linklist_print(phead,printStu); break; case 3: printf("Input name,age,score:"); data_t d; scanf("%s",d.name); scanf("%d",&d.age); scanf("%f",&d.score); linklist_insert_head(phead,&d); break; case 4: linklist_delete_head(phead); break; case 5: printf("stu nums: %d\n",length(phead)); break; case 6: printf("---退出-----\n"); goto exit; } } exit: return 0; }二、GDB 调试链表程序
链表大量指针操作，极易发生段错误 Segmentation fault，肉眼很难看出来，必须学会 GDB 调试。
带调试符号编译
必须加
-g -O0
-g：生成调试符号；-O0关闭编译器优化，防止代码行号错乱
gcc -g -O0 swap.c -o swap启动调试：
gdb ./stu_linklist出现(gdb)提示符代表进入调试器。
GDB 高频命令速查
表格
| 命令 (缩写) | 功能 |
|---|---|
r(run) | 从头运行程序 |
c(continue) | 继续运行到下一个断点 |
n(next) | 单步，不进入函数 |
s(step) | 单步，进入函数内部 |
finish | 执行完当前函数返回 |
b(break) main | 在 main 函数打断点 |
b 35 | 在 35 行打断点 |
info b | 查看全部断点 |
p 变量名 | 打印变量，p/x 变量十六进制打印 |
bt(backtrace) | 打印函数调用栈，崩溃必用 |
l(list) | 查看附近源代码 |
watch p | 观察点：变量被修改时停下，排查指针异常神器 |
q(quit) | 退出 gdb |
三、链表高频考点
1. 找到链表的中间节点
题目描述
给定一条带头单向链表，找出链表中间节点。 奇数个节点，返回正中间；偶数个节点，返回中间第二个节点。 示例：head->1-2-3-4-5-NULL，中间节点是3；head->1-2-3-4-5-6-NULL，中间节点是4
思路
两种方案：
- 方案 1：先遍历一遍统计链表总长度，再遍历
len/2次找到中点，需要遍历 2 次链表。 - 方案 2：快慢指针（推荐，只遍历 1 次链表）
- 快指针 p：一次走 2 步
- 慢指针 q：一次走 1 步 快指针走到末尾 NULL 时，慢指针刚好停在中点。
node_t *linklist_find_mid(node_t *phead) { //判断有效性 if (phead == NULL) { return NULL; } node_t *p = phead;//快指针，一次走两步 node_t *q = phead;//慢指针，一次走一步 //循环条件，链表元素为偶数p->next==NULL结束；奇数p==NULL结束 while (p->next != NULL && p != NULL) { p = p->next->next; q = q->next; } return q; }2. 找到链表的倒数第 k 个节点
题目描述
找到链表倒数第 k 个节点。例如链表1-2-3-4-5-6，k=2，倒数第 2 个节点是5。 要求：只遍历链表一次。
思路：前后双指针
- p、q 两个指针，都先指向头节点
- 让 p 指针先走 k 步
- 之后 p、q 同步向后一步一步走
- 当 p 走到 NULL 的时候，q 所在节点就是倒数第 k 个节点
边界坑：k 大于链表总节点数，直接返回 NULL。
node_t *linklist_find_behind_key(node_t *phead, int key) { if (phead == 0 || is_empty(phead) == 1) { return NULL; } node_t *p = phead; node_t *q = phead; //p先走key步 while (key > 0) { p = p->next; --key; } //p、q同步移动，当p=NULL，q所在位置为倒数第key个 while (p != NULL) { p = p->next; q = q->next; } return q; }3. 判断链表是否有环
题目描述
单向链表是否存在环。有环的链表尾节点不会指向 NULL，会指向链表内部某个节点，遍历会无限循环。
思路：快慢指针追击（Floyd 判圈算法）
- 快指针 pf 一次走 2 步，慢指针 ps 一次走 1 步
- 如果链表无环，快指针会率先走到 NULL，直接返回 0
- 如果链表存在环，快慢指针一定会在环内相遇（pf == ps），返回 1
int linklist_is_circle(node_t *phead) { if (phead == NULL || is_empty(phead) == 1) { return -1; } node_t *p = phead;//快指针，一次走两步 node_t *q = phead;//慢指针，一次走一步 //考虑链表元素有奇数或偶数两种情况，循环条件和找中间节点一样 while (p != NULL && p->next != NULL) { p = p->next->next; q = q->next; if (p == q)//快慢指针相遇，说明有环 { return 1; } } //p走到NULL，说明无环 if (p == NULL || p->next == NULL) { return 0; } }4. 链表的逆序（倒置，就地反转）
题目描述
将带头单向链表原地反转，不能新开链表。 原始：head ->1->2->3->4->NULL逆序后：head ->4->3->2->1->NULL
思路：头插法就地逆置
p指向第一个有效节点p = phead->next- 把头节点
next置 NULL，当成空链表 - 依次取出 p 指向节点，不断头插到 head 后面，直到 p 遍历完毕
int linklist_reverse(node_t *phead) { if (phead == NULL || phead->next == NULL) { return -1; } if (phead->next->next == NULL)//链表中只有一个数据，不进行逆序操作 { return 0; } node_t *p = phead->next;//p指向首元素 phead->next = NULL; //头节点变成空链表 node_t *q = NULL; //q临时保存p的下一个节点 //头插法 while (p != NULL) { q = p->next; p->next = phead->next; phead->next = p; p = q;//p向后移动 } return 1; }三指针法：
int linklist_reverse_threep(node_t*phead) { if (phead == NULL || phead->next == NULL) { return -1; } if (phead->next->next == NULL) { return 0; } node_t *curr = phead->next; node_t *prev = NULL; node_t *next = NULL; while (curr != NULL) { next = curr->next; curr->next = prev; prev = curr; curr = next; } phead->next = prev; return 1; }5. 链表排序（选择排序）
题目描述
对单向链表进行升序排序，这里采用选择排序。
数组选择排序思路：每一轮找到未排序区间最小值，放到当前确定位置。链表版本用指针实现，不交换节点数据，操作指针。
思路
- 用外层指针标记当前待填充位置
- 内层遍历，找到后面数据最小的节点
- 交换节点数据（简易版，面试快速手写；高级版本直接移动节点指针）
说明：链表选择排序，简易实现可以交换节点内部 data，简化代码。
int linklist_select_sort(node_t *phead) { if (phead == NULL || phead->next == NULL) { return -1; } if (phead->next->next == NULL) { return 0; } node_t *p = phead->next; node_t *q = p->next; int data; while (p->next != NULL) { while (q != NULL) { if (p->data > q->data) { data = p->data; p->data = q->data; q->data = data; } q = q->next; } p = p->next; q = p->next; } return 1; }刷题总结
快慢指针是链表笔试的核心技巧：找中点、判环都靠它，一定要吃透。
双指针（前后指针）专门解决倒数第 k 节点这类 “距离固定” 的问题。
链表逆置是必背手写代码，嵌入式 C 面试出现频率极高。
链表操作最容易踩坑：空指针判断，每一个函数入口先校验指针有效性。
写链表代码的好习惯：画图！方框代表节点，箭头表示 next 指针，指针逻辑一目了然。
四、总结
- 带头单向链表核心：节点 = 数据域 + 指针域，画图是理解链表最好的手段。不要光背代码，画方框 + 箭头模拟指针变化。
- 学生管理系统完整实践：创建、插入、删除、遍历、统计长度，熟悉链表整套流程。
- 链表大量指针操作，出现段错误不要瞎猜，学会GDB 调试，断点、单步、print 打印指针、bt 看调用栈，快速定位 bug。
- 笔试高频：链表逆置、判环、删除节点、头插尾插等，必须能手写。
