与队列详解)
上一篇讲解了单向链表基础：结构体封装、头插、尾插、尾删、valgrind 内存泄漏检测。本篇继续拓展环形链表判环、环长、环入口、双向链表、Linux 内核链表、链式队列，配套原理推导、核心逻辑，适合期末复习、嵌入式 C 面试准备。
一、单向链表 —— 环形链表问题
单向链表尾结点不再指向NULL，指向链表内部某个结点，就形成带环链表。常见三道面试题：判断是否有环、求环的长度、求环的入口点，核心算法：快慢指针（双指针）。
1. 判断链表是否有环：快慢指针法
定义两个指针：
pfast快指针，pslow慢指针，都从链表头出发。慢指针
pslow每次走 1 步；快指针pfast每次走 2 步。
如果快指针走到
NULL，链表无环；如果快慢指针在链表中相遇，链表一定存在环。
原理：环内，快指针速度大于慢指针，快指针会不断追赶慢指针，环内一定会相遇；无环链表快指针会率先抵达末尾
NULL。
2. 求有环链表的环长
环长：环形部分包含结点数量
快慢指针得到相遇点；
指针从相遇点开始遍历，循环计数；
当指针再次回到相遇点，统计得到结点个数就是环的长度。
3. 求环形链表环的入口结点（经典数学推导）
设：
l：链表头到环入口的结点距离；a：环入口到快慢指针相遇点距离；b：相遇点回到环入口的距离； 环总长：L = a + b。
相遇时：
慢指针路程：
s = l + a快指针路程：
2s = l + a + k*(a+b)，k 为快指针在环内绕的圈数
联立化简，得到关键结论：l = b
✅数学结论：链表起点到环入口距离 = 相遇点到环入口距离
算法实现步骤：
得到快慢指针相遇结点；
一个指针从相遇点出发，另一个指针从链表头部出发；
两个指针每次都只走一步；
两个指针第一次相遇的结点，就是环形链表的环入口。
⚠️注意：必须两个指针都一次走一步，不能继续快慢速度。
二、双向链表
单向链表结点只有后继指针pnext，只能向后遍历；双向链表每个结点增加前驱指针ppre，既可以向后遍历，也可以向前回溯。
1. 双向链表结构体定义
//数据域，可以自定义存储任意业务数据 typedef struct stu { char name[32]; int age; int score; }Data_t; //双向链表结点：前驱+后继+数据 typedef struct dnode { Data_t data; struct dnode *ppre; //指向前驱结点 struct dnode *pnext; //指向后继结点 }DNode_t; //双向链表管理对象，封装头指针与链表长度 typedef struct dlink { DNode_t *phead; int clen; }DLink_t;2. 双向链表优缺点
✅优点
支持正向、反向双向遍历；
已知某结点，可以直接找到它的前驱结点，单向链表必须从头遍历；
删除当前结点时，不需要遍历找前驱。
❌缺点
每个结点多一个指针域，内存开销变大；
插入、删除结点，要维护两个指针（ppre、pnext），代码逻辑比单链表复杂，指针顺序容易写错。
3. 双向链表 API 接口清单
创建双向链表
结点插入（头插、尾插、按位置插入）
结点删除
结点查找
结点数据修改
正向 / 反向遍历链表
链表销毁（循环 free 所有结点，释放链表对象，防止内存泄漏）
💡易错提醒：双向链表插入删除，要同时修改新结点、相邻结点的
ppre与pnext，指针赋值顺序不能乱。
三、Linux 内核链表
内核链表本质：双向循环链表，Linux 内核大量使用。
和普通双向链表核心区别
普通链表：结点内部包含数据域结点把业务数据直接包在结构体里面，一旦写死数据类型，链表就只能存这一种数据。如果要存新的数据类型，需要重新写一套链表代码。
内核链表：链表节点嵌入业务结构体
链表的
ppre、pnext指针不包裹数据；把链表小结构体，嵌入到你自己业务结构体内部。 同一套链表代码，可以挂载任意不同类型业务结构体，代码复用性极强。
核心两个内核宏：
offsetof(TYPE, MEMBER)获取结构体成员，距离结构体起始地址的字节偏移量。container_of(ptr, type, member)已知嵌入的链表成员地址，结合偏移量，反向得到整个业务结构体的首地址。
工作流程：通过链表指针 → container_of + offsetof → 拿到外层完整业务结构体。
内核链表没有 data 域，只负责串起结构体；业务数据放在外层结构体。一套链表算法适配多种数据类型，驱动、内核模块广泛使用。
四、队列（Queue）
1. 队列基础概念
队列是线性结构，特性：FIFO 先进先出。
队尾：执行插入操作，叫入队
队头：执行删除操作，叫出队
类比排队：先排队的人，先离开队伍。
2. 队列分类
顺序队列：数组实现，存在假溢出问题，一般优化为循环队列
链式队列：链表实现，本篇重点
链式队列管理结构体，一般保存：
phead：队头指针（出队在这里删结点）ptail：队尾指针（入队在这里新增结点）clen：当前队列元素个数
3. 链式队列核心操作
入队（队尾插入结点）新结点加到
ptail后面，更新队尾指针ptail指向新结点；队列为空时，phead和ptail都指向新结点。出队（队头删除结点）删除
phead指向的队头结点，更新队头指针； ⚠️边界：删除之后队列为空，需要将ptail置NULL，避免野指针。
4. 队列 API
创建队列
入队
队列遍历
判断队列是否为空
出队
获取队头元素（只读取，不删除）
销毁队列：释放全部结点、释放队列管理对象
5. 队列典型应用场景
数据缓冲、任务排队、消息队列，生产者消费者模型。
知识点总结思维导图
环形单向链表
判环：快慢指针；有环则相遇，无环 fast 走到 NULL
环长：相遇点循环计数回到原点
环入口：头指针、相遇点指针，同速步进，相遇即入口，数学推导
l=b
双向链表每个结点：
ppre前驱指针 +pnext后继指针；双向遍历；插入删除维护两组指针，内存开销增大。内核双向循环链表链表结点嵌入业务结构体；
offsetof求偏移，container_of反向获取结构体首地址；一套链表操作支持多种数据类型。队列 FIFO 先进先出队尾入队，队头出队；链式队列维护头指针、尾指针；常用于缓冲、消息队列。
拓展思考（面试常考）
快慢指针为什么快指针每次走 2 步，走 3 步行不行？
可以，但 2 步是最简单；步长过大，会增加错过相遇的概率，2 步是最优。
双向链表删除结点相比单向链表优势？
单向链表删除当前结点，需要从头遍历找前驱；双向链表直接
node->ppre拿到前驱。
内核链表相比普通链表最大优势是什么？
代码复用，不需要为每种数据类型重写一套链表插入删除。
链式队列出队后，什么时候 ptail 要置 NULL？
删除之后队列变空，如果不置空，ptail 会变成野指针，下次入队会产生逻辑错误。下一篇可以完整实现：环形链表判环代码、双向链表全套接口、内核链表模拟实现、链式队列完整 C 代码。