1. 项目概述为什么需要单向循环链表先聊个实际场景。某天我在处理一个轮播图需求要求无限循环切换左滑右滑都不能到头。第一反应是用普通链表但写到边界判断的时候发现逻辑又碎又乱尾节点要特判、头节点要特判、还得维护一个单独的指针指向当前节点。代码写完自己都不想看第二遍。后来换成了单向循环链表整个逻辑清爽得像是换了一个世界。那什么是单向循环链表通俗讲就是让链表的尾节点不再指向空NULL而是回过头指向头节点整个链表形成一个环。节点只有一个指针域所以叫“单向”所有节点首尾相接所以叫“循环”。它的核心价值在于从任意一个节点出发沿着指针走必然能遍历到所有节点永远不存在“走到头了”的情况。这个特性在需要周期性访问数据的场景里极其好用。这篇内容会从逻辑结构讲起把单向循环链表的定义、创建、插入、删除、遍历、销毁这些基本操作全部拆开讲透每一段都附上可以直接参考的C语言代码注释与图解说明。同时会结合实际场景——比如约瑟夫环问题、任务轮询调度、轮播图切换——来展示它到底在哪些地方能发挥真实作用。适合谁看刚学完单链表想继续进阶的初学者、期末复习数据结构正在为链表题目发愁的学生、还有那些工作中遇到“需要环形访问”但不知道用什么结构合适的开发者。这篇文章的目标是让每一个看完的人都能自己对单向循环链表下判断什么场景用它什么场景老老实实用单链表心里有数。2. 为什么单链表不够用循环链表的不可替代之处2.1 单链表的边界痛点很多初学者在学完单链表后会有一种“这东西什么都能干”的错觉。确实单链表支持O(1)时间插入删除只要找到了合适的位置存储空间按需分配结构灵活。但当你真正落到某个具体需求时比如“要把所有节点轮询一遍然后回到起点继续轮询”单链表就会暴露出明显的别扭之处。举个例子你用单链表存了一批任务每次调度都从头节点开始扫描。假设当前处理到了第3个节点下一次又要从头再走一遍到第4个节点整体效率直接就O(n²)了而且代码里全是“如果当前指针为空就回到头节点”这种边界判断。逻辑没错但写起来啰嗦读起来费劲维护起来更痛苦。再比如删除尾节点这个操作。在单链表里删除尾节点必须要找到它的前驱节点于是你得从头节点开始遍历到倒数第二个节点。这个O(n)的成本倒不是不能接受但配合上循环结构后你会发现很多边界情况可以直接消除代码的“形状”会变得更规整。2.2 循环链表的本质优势从“断头路”到“环形跑道”把尾节点的next从NULL改成指向头节点就完成了从单链表到单向循环链表的关键一步。这个改动看似微小带来的变化却是结构性的。第一任何节点都是“中间节点”。因为是环形结构你在任一点出发都能走完全程不存在“这之后没路了”的情况。这直观地简化了遍历、轮询、计数等操作的实现。第二插入和删除的边界逻辑大幅减少。比如在尾部插入新节点普通单链表需要遍历找尾然后置next但在维护尾指针的情况下循环链表只需要操作尾指针和头节点两个位置时间复杂度从O(n)降到O(1)。第三约瑟夫环这类数学问题的建模变得非常自然。让一个报数游戏对应到链表的节点删除过程不需要额外的“从头再走一遍”逻辑参与。整个算法就两个字循环。需要说的是循环链表并不是单链表的替代品而是它的补充。如果你的应用场景是一次性遍历、没有环形访问需求单链表依然是最优选择。别为了用而用结构选型永远是需求驱动。3. 准备开工结构体定义与基础工具函数3.1 节点结构体与循环链表头文件设计和单链表一样我们先从节点类型定义开始。C语言里定义一个单向循环链表节点需要两个要素数据域存数据和指针域存后继节点地址。最常见的写法如下typedef int ElemType; // 数据元素类型根据业务可换成任意类型 typedef struct Node { ElemType data; // 数据域 struct Node *next; // 指针域指向后继节点 } Node, *LinkList;这里有一个细节值得说。很多教材里会在链表结构体里附带一个“头节点”而头节点不存储实际数据只作为链表操作的锚点。这在单链表里很有用可以让空表和非空表的操作逻辑统一。但在循环链表中头节点的作用需要重新审视。如果带头节点那么空表就是只有一个头节点且它next指向自己循环条件比较明显p-next ! head时表示还有数据节点可访问。如果不带头节点空表就是简单的NULL插入和删除时对首元节点的处理需要单独写分支。两种风格各有利弊但为了代码可读性和操作统一性我建议初学者先带头节点。后面讲解的内容默认都是带头节点的单向循环链表。3.2 初始化、判空、求长度的三个小函数先看初始化。创建一个带头节点的空循环链表关键操作是让头节点的next指针指向它自己// 初始化创建头节点并使头节点的next指向自己空循环链表 void InitList(LinkList *L) { *L (Node *)malloc(sizeof(Node)); if (*L NULL) { printf(内存分配失败\n); exit(1); } (*L)-next *L; // 关键点空表时头节点的next指向自己 }判空和求长度的实现也顺带写上// 判空空表的标志是 head-next head int IsEmpty(LinkList L) { return L-next L; } // 求长度从第一个数据节点开始计数直到回到头节点为止 int ListLength(LinkList L) { int len 0; Node *p L-next; while (p ! L) { len; p p-next; } return len; }注意求长度时的循环条件。当p回到头节点L时说明已经走完了一圈计数结束。这个条件和单链表的p ! NULL有本质区别判断的不再是“地址是否为空”而是“是否绕了一圈回到起点”。4. 核心操作拆解插入、删除、遍历的写法与陷阱4.1 头插法和尾插法建表的两种姿势建表有两种常见方式头插法和尾插法。头插法每次把新节点插到头节点之后最终得到的链表顺序是逆序的。尾插法每次把新节点追加到当前尾部链表顺序和输入顺序一致。实现的关键差异在于“尾部”怎么找。头插法比较简单因为尾部天然由头节点的next来维护。假设插入节点s到头节点head之后// 头插法在头节点L后插入新节点s void InsertAtHead(LinkList L, Node *s) { s-next L-next; // 新节点的next指向原来第一个数据节点 L-next s; // 头节点的next指向新节点 }这个操作没有循环时间O(1)很好理解。尾插法如果不维护尾指针则需要通过while循环寻找尾节点但如果每次插入都从头走一遍多次插入就是O(n²)。所以正规的做法是要么额外维护一个尾指针要么在每次插入时从尾部插入。这里我给出维护尾指针更简洁。但考虑到很多教材考题不考尾指针这里仍然给出找尾的标准写法// 尾插法在循环链表尾部插入新节点 void InsertAtTail(LinkList L, Node *s) { Node *p L; while (p-next ! L) { // 注意是p-next ! L不是p ! L p p-next; } // 此时p是最后一个数据节点其next指向头节点L s-next L; // 新节点成为新的尾节点next指向头节点 p-next s; }一定要小心while的条件是p-next ! L。如果你写成了p ! L循环会多转一圈插入位置就会出错。这个错误特别隐蔽光看代码很容易忽略调试的时候却能让人抓狂半天。4.2 按值删除与按位删除别让指针走丢删除操作的核心是要找到被删节点的前驱节点。因为在单向链表中你只能通过前驱的next指针来“跳过”被删节点从而把被删节点从链中摘除。找到了前驱操作就三步保存被删节点、改前驱next、释放内存。按值删除假设删除第一个值为val的节点代码如下int DeleteByValue(LinkList L, ElemType val) { Node *prev L; Node *p L-next; while (p ! L) { // 遍历整个循环链表 if (p-data val) { prev-next p-next; // 跳过p节点 free(p); // 释放被删节点 return 1; // 删除成功 } prev p; p p-next; } return 0; // 未找到 }按位移除删除第i个节点与此类似核心区别只是把“判断data是否相等”换成“计数器是否到达i”。注意删除成功后如果被删节点是唯一数据节点删除后的空表状态应该是head-next head这个在前面初始化时已经约定好了不需要额外处理。这里有一个细节free(p)之后p指针已经变成了野指针所以下面要马上让p转向下一个节点。链表代码里养成“释放之后立刻改指针”的习惯很重要否则后面再用到p就是读取非法内存。4.3 遍历输出理解循环终止条件的本质遍历循环链表最常见的写法void Traverse(LinkList L) { Node *p L-next; if (p L) { // 空表 printf(链表为空\n); return; } while (p ! L) { printf(%d , p-data); p p-next; } printf(\n); }这个遍历的判断条件p ! L说白了就是“只要还没回到头节点就继续走”。在环形结构里从头节点出发走一圈沿途访问所有数据节点最后回到头节点遍历结束。这和单链表的“p ! NULL”判断本质相同但所指不同NULL表示空间尽头L表示结构起点。如果你需要只访问链表的一部分比如“从第k个节点开始访问接下来的n个节点”遍历条件就要跟着改。本质上循环链表可以模拟“无限长度”的序列只要你愿意沿着next永远能走下去。这个特性在后面讲约瑟夫环和轮询调度时会体现得淋漓尽致。5. 实战案例约瑟夫环问题与任务轮询调度的完整代码5.1 约瑟夫环数据结构的经典面试题约瑟夫环问题描述n个人围成一圈从第1个人开始报数报到m的人出列然后从出列者的下一个人重新报数报到m的人再出列直到所有人都出列为止。输出出列顺序。这个问题如果要写数组解法每次删除一个人都要“移动”后续元素复杂度O(n²)。用循环链表解每次删除都只需要改指针时间复杂度O(n)思路也更贴合“围成一圈”的语义。实现思路建立n个节点的循环链表节点编号1到n。从第1个节点开始计数每计数到m就删除当前节点然后从下一个节点继续。考虑用尾指针直接指向“当前位置”配合移动计数器。下面是一个完整实现#include stdio.h #include stdlib.h typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; } Node; // 创建n个节点(编号1..n)的循环链表返回头节点 Node* CreateJosephusList(int n) { Node *head (Node *)malloc(sizeof(Node)); Node *tail head; head-next NULL; for (int i 1; i n; i) { Node *s (Node *)malloc(sizeof(Node)); s-data i; s-next NULL; tail-next s; tail s; } tail-next head-next; // 最后一个节点指向第一个数据节点形成循环 // 释放头节点这里采用不带头节点的写法让第一个数据节点作为起点 Node *first head-next; free(head); return first; } void Josephus(int n, int m) { Node *p CreateJosephusList(n); // 让p指向尾节点方便统一删除逻辑 Node *prev p; while (prev-next ! p) { prev prev-next; } while (p-next ! p) { // 只剩一个节点时停止 for (int i 1; i m; i) { prev p; p p-next; } // 此时p是要出列的节点 printf(%d , p-data); prev-next p-next; Node *tmp p; p p-next; // 从下一个节点重新开始 free(tmp); } printf(%d\n, p-data); // 最后一个幸存者 free(p); } int main() { Josephus(7, 3); return 0; }这个实现里有一个很微妙的地方用一个prev指针始终跟在p后面这样删除p的时候才有人“记路”。如果你没有prev指针删除操作会非常痛苦因为单向链表没有办法找前驱。这属于典型的“写代码前先想清楚要什么”的例子。5.2 任务轮询调度从理论到业务落地约瑟夫环是纯算法题但循环链表在业务场景里同样有真实应用。任务轮询调度就是一个典型。设想一个轻量级的消息队列组件有多个消费者线程轮流从队列取消息。如果把消费者排列成循环链表调度器只在链表中维护一个“当前节点”指针每取一次消息就让指针后移一次。这样一轮调度完成时指针自然回到起始消费者不需要额外的重置逻辑。核心代码逻辑可以这样写伪代码片段// 假设已有循环链表存储消费者current指向当前待调度的消费者 // 每轮调度结束后current向后移动 void ScheduleTask(LinkList consumers, Node **current) { Node *p *current; // 将消息分发给p指向的消费者 dispatch(p); // 调度下一个消费者 *current p-next; // 注意如果下一个是头节点或空表需要跳过或重置 if (*current consumers) { *current (*current)-next; } }从我的实践经验来看循环链表在“规模不大、需要简单公平轮询”的场景里比复杂的加权轮询、哈希取模都要直接。代码量小、可读性高、调试成本低。5.3 轮播图无限循环背后的链表思维另一个贴近生活的场景是轮播图。假设有5张图要循环切换向左滑动时从第5张回到第1张向右滑动时从第1张回到第5张。如果用数组实现需要两个索引方向的分支判断如果用单向循环链表只要维护一个“当前图片”节点指针无论向前向后只需要走next就能完成循环——但注意单向循环链表只能单向走。严格来说轮播图需要双向循环链表才能真正做到两个方向的自由移动。单向循环链表只有next适合固定方向的情况比如“自动播放不断向后循环”。不过理解单向循环链表如何模拟无限序列是理解双向循环链表的基础。能把单向的搞明白双向的只是多一个prev指针代码逻辑是顺势长出来的。6. 易错点与调试技巧这几年踩过的坑6.1 死循环最隐蔽又最致命的错误循环链表里最容易出的问题就是死循环。人为把一个链表搞成环形结构后如果你没有在合适的位置设置终止条件循环将永不停止程序表现就是“运行很久都不退出”。最常见的死循环来源有两个一是遍历时把终止条件写错。比如你写while(p ! NULL)去遍历一个循环链表那从第一个数据节点开始p依次前进永远得不到NULL循环就永远不会结束。正确写法是while(p ! head)判断是否回到起点。二是插入或删除时忘记把新节点的next指向正确位置。最典型的是尾插法时忘记s-next L导致新节点接入后链表从尾部断开了整个结构不再是循环。这会导致遍历时出现空指针解引用程序直接崩溃。崩溃反而容易排查死循环更让人头痛。6.2 指针丢失改指针顺序决定代码生死链表中改指针遵循一个基本原则先接后断。也就是说先让新节点把前后连接“接住”再去断开原来的连接。顺序反了后面就没有地址可用了。在循环链表里插入节点s到p之后时正确顺序是s-next p-next; // 先把s接住原来的后继 p-next s; // 再把p的next指向s如果先执行p-next s那原本p-next指向的后继节点地址就丢了s-next就只能拿到一个错误的地址链表当场断裂。这个错误在单链表里同样会犯但在循环链表中因为目标节点本来就在环里断裂后会造成更诡异的访问错乱。6.3 调试技巧三步定位循环链表问题我调试链表问题时习惯按下面三步走先静态检查循环边界画出链表结构图标明每个节点的next指向。链表题用纸笔画图比任何调试器都高效。再动态观察在遍历循环处打印每个节点的data和next指针加上“第几次循环”的标记。这样死循环出现时能马上知道是哪个位置卡住了。最后看释放逻辑用了free后是否立刻更新指针。内存释放顺序错误会造成悬空指针后面访问时是随机崩溃。这套流程虽然朴素但真的能救急。特别是你在公司不熟悉别人的代码时先把循环边界画出来基本能避开80%的坑。7. 扩展与变式从单向循环链表到双向循环链表7.1 双向循环链表解决单向的“回不去”问题单向循环链表的所有节点只有一个后继指针这决定了它的行为是“指定方向永动”。但很多真实场景需要反向移动比如文本编辑器里的撤销重做、浏览器的前进后退、播放器的上一首下一首。双向循环链表在节点结构里加了一个prev指针指向直接前驱。这样从任何位置出发既能沿next正向走又能沿prev反向走。这极大地方便了“双向轮询”需求。代价是每一个节点多存储一个指针内存开销增加了插入和删除操作时的指针修改多了一步——因为你需要同时维护prev和next两个方向的连接。从维护角度看双向循环链表最麻烦的地方是删除操作。删除一个节点时除了要修改前驱的next还需要修改后继的prev。漏掉任何一边链表结构就破坏掉了。很多面试题目考察“给定双向循环链表的一个节点删除它”就不是靠遍历去找前驱了而是直接操作该节点自己的prev和next就能完成——这反而是双向结构的优势。7.2 循环链表的适用场景清单与选型建议综合看下来我建议用下面的标准来判断是否选择单向循环链表。先看你是否有“环形访问”的需求。如果数据一旦遍历到末尾就必须停下来重新开始说明需求是线性的用普通线性结构即可。如果数据处理是周期性的、不断环绕重复的——比如轮询、令牌传递、令牌桶算法里的令牌补发、音乐播放列表的循环播放——循环链表就是天然适配的结构。再看“是否需要双向”。如果业务只向一个方向移动交换机的轮询队列、操作系统的进程调度部分实现等单向就够了。如果还需要反向那就直接用双向循环链表。最后看“节点的增删频率”。循环链表和单链表的增删效率在头部和尾部都有优势但中间位置的删除都需要遍历。如果中间操作很多且频繁需要考虑用跳表、平衡树等更复杂结构不要硬用链表。有些问题本身可以用数组加取模运算解决比如轮询一组固定数量的消费者用数组下标取模也能实现环的效果。那什么时候选链表当消费者数量动态变化、经常增加或删除时链表能避免数组的扩容和数据搬移成本。这又回到了数据结构选型的老话结构不是越复杂越好而是越匹配需求越好。7.3 一个不算扩展的扩展循环链表的工程价值说句实在话即使你日常业务里碰不到要手写循环链表的场景这类结构性思维的训练依然有价值。它能帮你熟练地建立“数据之间如何组织关系”的直觉。写数组解法很容易但如果业务要求的是动态增删数组就会出现性能问题。链表操作里学到的“指针即引用”思想在后端开发里也非常常见——每个对象的地址连接本质上就是内存版的关联关系。我个人的一个小习惯是遇到“环形”两个字先想想能不能用循环链表建模。哪怕最终不用这个过程本身就能帮你理清数据的组织逻辑。数据结构不是面试前背一遍就丢的东西它会在你设计的每一个系统里缓慢地发挥作用。 
长河君 · 2026/10/20 6:15:27 · 阅读 1.2k 单向循环链表详解：从结构原理到约瑟夫环与任务轮询实践
1. 项目概述为什么需要单向循环链表先聊个实际场景。某天我在处理一个轮播图需求要求无限循环切换左滑右滑都不能到头。第一反应是用普通链表但写到边界判断的时候发现逻辑又碎又乱尾节点要特判、头节点要特判、还得维护一个单独的指针指向当前节点。代码写完自己都不想看第二遍。后来换成了单向循环链表整个逻辑清爽得像是换了一个世界。那什么是单向循环链表通俗讲就是让链表的尾节点不再指向空NULL而是回过头指向头节点整个链表形成一个环。节点只有一个指针域所以叫“单向”所有节点首尾相接所以叫“循环”。它的核心价值在于从任意一个节点出发沿着指针走必然能遍历到所有节点永远不存在“走到头了”的情况。这个特性在需要周期性访问数据的场景里极其好用。这篇内容会从逻辑结构讲起把单向循环链表的定义、创建、插入、删除、遍历、销毁这些基本操作全部拆开讲透每一段都附上可以直接参考的C语言代码注释与图解说明。同时会结合实际场景——比如约瑟夫环问题、任务轮询调度、轮播图切换——来展示它到底在哪些地方能发挥真实作用。适合谁看刚学完单链表想继续进阶的初学者、期末复习数据结构正在为链表题目发愁的学生、还有那些工作中遇到“需要环形访问”但不知道用什么结构合适的开发者。这篇文章的目标是让每一个看完的人都能自己对单向循环链表下判断什么场景用它什么场景老老实实用单链表心里有数。2. 为什么单链表不够用循环链表的不可替代之处2.1 单链表的边界痛点很多初学者在学完单链表后会有一种“这东西什么都能干”的错觉。确实单链表支持O(1)时间插入删除只要找到了合适的位置存储空间按需分配结构灵活。但当你真正落到某个具体需求时比如“要把所有节点轮询一遍然后回到起点继续轮询”单链表就会暴露出明显的别扭之处。举个例子你用单链表存了一批任务每次调度都从头节点开始扫描。假设当前处理到了第3个节点下一次又要从头再走一遍到第4个节点整体效率直接就O(n²)了而且代码里全是“如果当前指针为空就回到头节点”这种边界判断。逻辑没错但写起来啰嗦读起来费劲维护起来更痛苦。再比如删除尾节点这个操作。在单链表里删除尾节点必须要找到它的前驱节点于是你得从头节点开始遍历到倒数第二个节点。这个O(n)的成本倒不是不能接受但配合上循环结构后你会发现很多边界情况可以直接消除代码的“形状”会变得更规整。2.2 循环链表的本质优势从“断头路”到“环形跑道”把尾节点的next从NULL改成指向头节点就完成了从单链表到单向循环链表的关键一步。这个改动看似微小带来的变化却是结构性的。第一任何节点都是“中间节点”。因为是环形结构你在任一点出发都能走完全程不存在“这之后没路了”的情况。这直观地简化了遍历、轮询、计数等操作的实现。第二插入和删除的边界逻辑大幅减少。比如在尾部插入新节点普通单链表需要遍历找尾然后置next但在维护尾指针的情况下循环链表只需要操作尾指针和头节点两个位置时间复杂度从O(n)降到O(1)。第三约瑟夫环这类数学问题的建模变得非常自然。让一个报数游戏对应到链表的节点删除过程不需要额外的“从头再走一遍”逻辑参与。整个算法就两个字循环。需要说的是循环链表并不是单链表的替代品而是它的补充。如果你的应用场景是一次性遍历、没有环形访问需求单链表依然是最优选择。别为了用而用结构选型永远是需求驱动。3. 准备开工结构体定义与基础工具函数3.1 节点结构体与循环链表头文件设计和单链表一样我们先从节点类型定义开始。C语言里定义一个单向循环链表节点需要两个要素数据域存数据和指针域存后继节点地址。最常见的写法如下typedef int ElemType; // 数据元素类型根据业务可换成任意类型 typedef struct Node { ElemType data; // 数据域 struct Node *next; // 指针域指向后继节点 } Node, *LinkList;这里有一个细节值得说。很多教材里会在链表结构体里附带一个“头节点”而头节点不存储实际数据只作为链表操作的锚点。这在单链表里很有用可以让空表和非空表的操作逻辑统一。但在循环链表中头节点的作用需要重新审视。如果带头节点那么空表就是只有一个头节点且它next指向自己循环条件比较明显p-next ! head时表示还有数据节点可访问。如果不带头节点空表就是简单的NULL插入和删除时对首元节点的处理需要单独写分支。两种风格各有利弊但为了代码可读性和操作统一性我建议初学者先带头节点。后面讲解的内容默认都是带头节点的单向循环链表。3.2 初始化、判空、求长度的三个小函数先看初始化。创建一个带头节点的空循环链表关键操作是让头节点的next指针指向它自己// 初始化创建头节点并使头节点的next指向自己空循环链表 void InitList(LinkList *L) { *L (Node *)malloc(sizeof(Node)); if (*L NULL) { printf(内存分配失败\n); exit(1); } (*L)-next *L; // 关键点空表时头节点的next指向自己 }判空和求长度的实现也顺带写上// 判空空表的标志是 head-next head int IsEmpty(LinkList L) { return L-next L; } // 求长度从第一个数据节点开始计数直到回到头节点为止 int ListLength(LinkList L) { int len 0; Node *p L-next; while (p ! L) { len; p p-next; } return len; }注意求长度时的循环条件。当p回到头节点L时说明已经走完了一圈计数结束。这个条件和单链表的p ! NULL有本质区别判断的不再是“地址是否为空”而是“是否绕了一圈回到起点”。4. 核心操作拆解插入、删除、遍历的写法与陷阱4.1 头插法和尾插法建表的两种姿势建表有两种常见方式头插法和尾插法。头插法每次把新节点插到头节点之后最终得到的链表顺序是逆序的。尾插法每次把新节点追加到当前尾部链表顺序和输入顺序一致。实现的关键差异在于“尾部”怎么找。头插法比较简单因为尾部天然由头节点的next来维护。假设插入节点s到头节点head之后// 头插法在头节点L后插入新节点s void InsertAtHead(LinkList L, Node *s) { s-next L-next; // 新节点的next指向原来第一个数据节点 L-next s; // 头节点的next指向新节点 }这个操作没有循环时间O(1)很好理解。尾插法如果不维护尾指针则需要通过while循环寻找尾节点但如果每次插入都从头走一遍多次插入就是O(n²)。所以正规的做法是要么额外维护一个尾指针要么在每次插入时从尾部插入。这里我给出维护尾指针更简洁。但考虑到很多教材考题不考尾指针这里仍然给出找尾的标准写法// 尾插法在循环链表尾部插入新节点 void InsertAtTail(LinkList L, Node *s) { Node *p L; while (p-next ! L) { // 注意是p-next ! L不是p ! L p p-next; } // 此时p是最后一个数据节点其next指向头节点L s-next L; // 新节点成为新的尾节点next指向头节点 p-next s; }一定要小心while的条件是p-next ! L。如果你写成了p ! L循环会多转一圈插入位置就会出错。这个错误特别隐蔽光看代码很容易忽略调试的时候却能让人抓狂半天。4.2 按值删除与按位删除别让指针走丢删除操作的核心是要找到被删节点的前驱节点。因为在单向链表中你只能通过前驱的next指针来“跳过”被删节点从而把被删节点从链中摘除。找到了前驱操作就三步保存被删节点、改前驱next、释放内存。按值删除假设删除第一个值为val的节点代码如下int DeleteByValue(LinkList L, ElemType val) { Node *prev L; Node *p L-next; while (p ! L) { // 遍历整个循环链表 if (p-data val) { prev-next p-next; // 跳过p节点 free(p); // 释放被删节点 return 1; // 删除成功 } prev p; p p-next; } return 0; // 未找到 }按位移除删除第i个节点与此类似核心区别只是把“判断data是否相等”换成“计数器是否到达i”。注意删除成功后如果被删节点是唯一数据节点删除后的空表状态应该是head-next head这个在前面初始化时已经约定好了不需要额外处理。这里有一个细节free(p)之后p指针已经变成了野指针所以下面要马上让p转向下一个节点。链表代码里养成“释放之后立刻改指针”的习惯很重要否则后面再用到p就是读取非法内存。4.3 遍历输出理解循环终止条件的本质遍历循环链表最常见的写法void Traverse(LinkList L) { Node *p L-next; if (p L) { // 空表 printf(链表为空\n); return; } while (p ! L) { printf(%d , p-data); p p-next; } printf(\n); }这个遍历的判断条件p ! L说白了就是“只要还没回到头节点就继续走”。在环形结构里从头节点出发走一圈沿途访问所有数据节点最后回到头节点遍历结束。这和单链表的“p ! NULL”判断本质相同但所指不同NULL表示空间尽头L表示结构起点。如果你需要只访问链表的一部分比如“从第k个节点开始访问接下来的n个节点”遍历条件就要跟着改。本质上循环链表可以模拟“无限长度”的序列只要你愿意沿着next永远能走下去。这个特性在后面讲约瑟夫环和轮询调度时会体现得淋漓尽致。5. 实战案例约瑟夫环问题与任务轮询调度的完整代码5.1 约瑟夫环数据结构的经典面试题约瑟夫环问题描述n个人围成一圈从第1个人开始报数报到m的人出列然后从出列者的下一个人重新报数报到m的人再出列直到所有人都出列为止。输出出列顺序。这个问题如果要写数组解法每次删除一个人都要“移动”后续元素复杂度O(n²)。用循环链表解每次删除都只需要改指针时间复杂度O(n)思路也更贴合“围成一圈”的语义。实现思路建立n个节点的循环链表节点编号1到n。从第1个节点开始计数每计数到m就删除当前节点然后从下一个节点继续。考虑用尾指针直接指向“当前位置”配合移动计数器。下面是一个完整实现#include stdio.h #include stdlib.h typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; } Node; // 创建n个节点(编号1..n)的循环链表返回头节点 Node* CreateJosephusList(int n) { Node *head (Node *)malloc(sizeof(Node)); Node *tail head; head-next NULL; for (int i 1; i n; i) { Node *s (Node *)malloc(sizeof(Node)); s-data i; s-next NULL; tail-next s; tail s; } tail-next head-next; // 最后一个节点指向第一个数据节点形成循环 // 释放头节点这里采用不带头节点的写法让第一个数据节点作为起点 Node *first head-next; free(head); return first; } void Josephus(int n, int m) { Node *p CreateJosephusList(n); // 让p指向尾节点方便统一删除逻辑 Node *prev p; while (prev-next ! p) { prev prev-next; } while (p-next ! p) { // 只剩一个节点时停止 for (int i 1; i m; i) { prev p; p p-next; } // 此时p是要出列的节点 printf(%d , p-data); prev-next p-next; Node *tmp p; p p-next; // 从下一个节点重新开始 free(tmp); } printf(%d\n, p-data); // 最后一个幸存者 free(p); } int main() { Josephus(7, 3); return 0; }这个实现里有一个很微妙的地方用一个prev指针始终跟在p后面这样删除p的时候才有人“记路”。如果你没有prev指针删除操作会非常痛苦因为单向链表没有办法找前驱。这属于典型的“写代码前先想清楚要什么”的例子。5.2 任务轮询调度从理论到业务落地约瑟夫环是纯算法题但循环链表在业务场景里同样有真实应用。任务轮询调度就是一个典型。设想一个轻量级的消息队列组件有多个消费者线程轮流从队列取消息。如果把消费者排列成循环链表调度器只在链表中维护一个“当前节点”指针每取一次消息就让指针后移一次。这样一轮调度完成时指针自然回到起始消费者不需要额外的重置逻辑。核心代码逻辑可以这样写伪代码片段// 假设已有循环链表存储消费者current指向当前待调度的消费者 // 每轮调度结束后current向后移动 void ScheduleTask(LinkList consumers, Node **current) { Node *p *current; // 将消息分发给p指向的消费者 dispatch(p); // 调度下一个消费者 *current p-next; // 注意如果下一个是头节点或空表需要跳过或重置 if (*current consumers) { *current (*current)-next; } }从我的实践经验来看循环链表在“规模不大、需要简单公平轮询”的场景里比复杂的加权轮询、哈希取模都要直接。代码量小、可读性高、调试成本低。5.3 轮播图无限循环背后的链表思维另一个贴近生活的场景是轮播图。假设有5张图要循环切换向左滑动时从第5张回到第1张向右滑动时从第1张回到第5张。如果用数组实现需要两个索引方向的分支判断如果用单向循环链表只要维护一个“当前图片”节点指针无论向前向后只需要走next就能完成循环——但注意单向循环链表只能单向走。严格来说轮播图需要双向循环链表才能真正做到两个方向的自由移动。单向循环链表只有next适合固定方向的情况比如“自动播放不断向后循环”。不过理解单向循环链表如何模拟无限序列是理解双向循环链表的基础。能把单向的搞明白双向的只是多一个prev指针代码逻辑是顺势长出来的。6. 易错点与调试技巧这几年踩过的坑6.1 死循环最隐蔽又最致命的错误循环链表里最容易出的问题就是死循环。人为把一个链表搞成环形结构后如果你没有在合适的位置设置终止条件循环将永不停止程序表现就是“运行很久都不退出”。最常见的死循环来源有两个一是遍历时把终止条件写错。比如你写while(p ! NULL)去遍历一个循环链表那从第一个数据节点开始p依次前进永远得不到NULL循环就永远不会结束。正确写法是while(p ! head)判断是否回到起点。二是插入或删除时忘记把新节点的next指向正确位置。最典型的是尾插法时忘记s-next L导致新节点接入后链表从尾部断开了整个结构不再是循环。这会导致遍历时出现空指针解引用程序直接崩溃。崩溃反而容易排查死循环更让人头痛。6.2 指针丢失改指针顺序决定代码生死链表中改指针遵循一个基本原则先接后断。也就是说先让新节点把前后连接“接住”再去断开原来的连接。顺序反了后面就没有地址可用了。在循环链表里插入节点s到p之后时正确顺序是s-next p-next; // 先把s接住原来的后继 p-next s; // 再把p的next指向s如果先执行p-next s那原本p-next指向的后继节点地址就丢了s-next就只能拿到一个错误的地址链表当场断裂。这个错误在单链表里同样会犯但在循环链表中因为目标节点本来就在环里断裂后会造成更诡异的访问错乱。6.3 调试技巧三步定位循环链表问题我调试链表问题时习惯按下面三步走先静态检查循环边界画出链表结构图标明每个节点的next指向。链表题用纸笔画图比任何调试器都高效。再动态观察在遍历循环处打印每个节点的data和next指针加上“第几次循环”的标记。这样死循环出现时能马上知道是哪个位置卡住了。最后看释放逻辑用了free后是否立刻更新指针。内存释放顺序错误会造成悬空指针后面访问时是随机崩溃。这套流程虽然朴素但真的能救急。特别是你在公司不熟悉别人的代码时先把循环边界画出来基本能避开80%的坑。7. 扩展与变式从单向循环链表到双向循环链表7.1 双向循环链表解决单向的“回不去”问题单向循环链表的所有节点只有一个后继指针这决定了它的行为是“指定方向永动”。但很多真实场景需要反向移动比如文本编辑器里的撤销重做、浏览器的前进后退、播放器的上一首下一首。双向循环链表在节点结构里加了一个prev指针指向直接前驱。这样从任何位置出发既能沿next正向走又能沿prev反向走。这极大地方便了“双向轮询”需求。代价是每一个节点多存储一个指针内存开销增加了插入和删除操作时的指针修改多了一步——因为你需要同时维护prev和next两个方向的连接。从维护角度看双向循环链表最麻烦的地方是删除操作。删除一个节点时除了要修改前驱的next还需要修改后继的prev。漏掉任何一边链表结构就破坏掉了。很多面试题目考察“给定双向循环链表的一个节点删除它”就不是靠遍历去找前驱了而是直接操作该节点自己的prev和next就能完成——这反而是双向结构的优势。7.2 循环链表的适用场景清单与选型建议综合看下来我建议用下面的标准来判断是否选择单向循环链表。先看你是否有“环形访问”的需求。如果数据一旦遍历到末尾就必须停下来重新开始说明需求是线性的用普通线性结构即可。如果数据处理是周期性的、不断环绕重复的——比如轮询、令牌传递、令牌桶算法里的令牌补发、音乐播放列表的循环播放——循环链表就是天然适配的结构。再看“是否需要双向”。如果业务只向一个方向移动交换机的轮询队列、操作系统的进程调度部分实现等单向就够了。如果还需要反向那就直接用双向循环链表。最后看“节点的增删频率”。循环链表和单链表的增删效率在头部和尾部都有优势但中间位置的删除都需要遍历。如果中间操作很多且频繁需要考虑用跳表、平衡树等更复杂结构不要硬用链表。有些问题本身可以用数组加取模运算解决比如轮询一组固定数量的消费者用数组下标取模也能实现环的效果。那什么时候选链表当消费者数量动态变化、经常增加或删除时链表能避免数组的扩容和数据搬移成本。这又回到了数据结构选型的老话结构不是越复杂越好而是越匹配需求越好。7.3 一个不算扩展的扩展循环链表的工程价值说句实在话即使你日常业务里碰不到要手写循环链表的场景这类结构性思维的训练依然有价值。它能帮你熟练地建立“数据之间如何组织关系”的直觉。写数组解法很容易但如果业务要求的是动态增删数组就会出现性能问题。链表操作里学到的“指针即引用”思想在后端开发里也非常常见——每个对象的地址连接本质上就是内存版的关联关系。我个人的一个小习惯是遇到“环形”两个字先想想能不能用循环链表建模。哪怕最终不用这个过程本身就能帮你理清数据的组织逻辑。数据结构不是面试前背一遍就丢的东西它会在你设计的每一个系统里缓慢地发挥作用。