上一篇讲解了单向链表基础结构体封装、头插、尾插、尾删、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*(ab)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 域只负责串起结构体业务数据放在外层结构体。一套链表算法适配多种数据类型驱动、内核模块广泛使用。四、队列Queue1. 队列基础概念队列是线性结构特性FIFO 先进先出。队尾执行插入操作叫入队队头执行删除操作叫出队类比排队先排队的人先离开队伍。2. 队列分类顺序队列数组实现存在假溢出问题一般优化为循环队列链式队列链表实现本篇重点链式队列管理结构体一般保存phead队头指针出队在这里删结点ptail队尾指针入队在这里新增结点clen当前队列元素个数3. 链式队列核心操作入队队尾插入结点新结点加到ptail后面更新队尾指针ptail指向新结点队列为空时phead和ptail都指向新结点。出队队头删除结点删除phead指向的队头结点更新队头指针 ⚠️边界删除之后队列为空需要将ptail置NULL避免野指针。4. 队列 API创建队列入队队列遍历判断队列是否为空出队获取队头元素只读取不删除销毁队列释放全部结点、释放队列管理对象5. 队列典型应用场景数据缓冲、任务排队、消息队列生产者消费者模型。知识点总结思维导图环形单向链表判环快慢指针有环则相遇无环 fast 走到 NULL环长相遇点循环计数回到原点环入口头指针、相遇点指针同速步进相遇即入口数学推导lb双向链表每个结点ppre前驱指针 pnext后继指针双向遍历插入删除维护两组指针内存开销增大。内核双向循环链表链表结点嵌入业务结构体offsetof求偏移container_of反向获取结构体首地址一套链表操作支持多种数据类型。队列 FIFO 先进先出队尾入队队头出队链式队列维护头指针、尾指针常用于缓冲、消息队列。拓展思考面试常考快慢指针为什么快指针每次走 2 步走 3 步行不行可以但 2 步是最简单步长过大会增加错过相遇的概率2 步是最优。双向链表删除结点相比单向链表优势单向链表删除当前结点需要从头遍历找前驱双向链表直接node-ppre拿到前驱。内核链表相比普通链表最大优势是什么代码复用不需要为每种数据类型重写一套链表插入删除。链式队列出队后什么时候 ptail 要置 NULL删除之后队列变空如果不置空ptail 会变成野指针下次入队会产生逻辑错误。下一篇可以完整实现环形链表判环代码、双向链表全套接口、内核链表模拟实现、链式队列完整 C 代码。