我最早意识到单向循环链表“没那么简单”是在某次给同学调试链表作业的时候。那时候有个同学交上来一个约瑟夫环的题目代码写得工工整整结果一运行就直接卡死。我盯着他的代码看了五分钟发现他把尾节点的 next 指向了 NULL却还在循环体里用while (p ! head)作为结束条件——链表倒是循环了条件判断却还停留在单链表的思路里不死循环才怪。这个细节让我印象很深。很多人学单向循环链表第一反应都是“这不就是把最后一个节点的 next 指回头节点吗”理解不算错但实际写起来插入、删除、遍历、判空、释放每一步都有和单链表完全不同的处理逻辑。这些差异如果不亲自踩一遍光看教科书上的示意图是真的记不住的。这篇文章就把我从“能写出代码”到“能写出不出 bug 的代码”这段过程里积累的东西全部摊开来讲。内容包括单向循环链表的本质拆解、手写每一步操作的完整代码、约瑟夫环的实战实现、三种链表结构的选型对比还有我调试过程中遇到的那些坑。适合正在学数据结构的学生、准备面试的求职者以及那些写了几年业务代码但想把链表底层逻辑彻底理清的后端开发。1. 单向循环链表究竟是啥先抛开教科书定义1.1 从最熟悉的单链表说起要理解循环链表最好的方式不是直接背定义而是先想清楚普通单链表在什么场景下“不够用”。单链表的结构大家都很熟每个节点包含一个数据域和一个指针域指针域指向下一个节点最后一个节点的 next 指向 NULL。这种结构的优点是插入删除不需要搬移数据缺点是访问第 i 个节点只能从头开始走平均时间复杂度是 O(n)没办法像数组那样直接下标访问。单链表还有个容易被忽略的“结构性限制”——它是一个“断头路”。你想从最后一个节点回头找前面的节点做不到你想从链表中间的某个节点出发遍历完整条链表也做不到。因为走到 NULL 就停了而 NULL 意味着“无路可走”。现实世界里很多数据天然就是环形的一圈人轮流报数、播放列表循环播放、操作系统里进程轮流占用 CPU、令牌环网里令牌在节点之间一遍遍转。这些场景用普通单链表表达建模起来总是差着那么一口气逻辑上需要额外的变量去记住“回头的路”。循环链表就是专门解决这个别扭感的。1.2 循环链表的结构与节点定义单向循环链表的核心改动只有一个最后一个节点的 next 指针不再指向 NULL而是指回头节点或第一个节点从而让整个链表形成一个环。这看起来是小改动但对所有操作的影响都是结构性的。以带头节点的循环链表为例空表的时候head-next head此时头节点自己形成一个环链表非空时最后一个节点的 next 指向头节点。也就是说遍历的时候判断是否走完一圈的标准不再是p NULL而是p head。用 C 语言定义一下节点结构typedef int ElemType; typedef struct Node { ElemType data; struct Node *next; } LNode, *LinkList;这个结构定义和普通单链表没有任何区别区别全部体现在操作逻辑上。带头节点和不带头节点两种写法我后面都会讲但我的建议非常明确初学阶段一律用带头节点的写法。原因也很简单带头节点时空表和非空表的操作可以统一处理不需要在插入删除时对“头节点位置是否变化”做特殊分支判断少写一半 if 分支也就少一半出错机会。我刚写循环链表的时候图省事用过不带头节点的版本结果每次删头节点都要重新赋值链表指针而删到尾节点又要额外处理代码丑到自己都不想看第二遍。后来老老实实换回带头节点世界清净了。2. 为什么需要循环链表死磕两次遍历就明白了2.1 循环带来的核心收益循环结构带来的第一个好处是从任意一个节点出发都能遍历整条链表。单链表你走到尾就只能原路返回起点从头出发循环链表不需要你在这条链上永远有“下一个”可走绕一圈自然回到出发点。很多算法比如判断链表是否成环的龟兔赛跑法反而要借助这种特性去做检测。第二个好处是尾部操作效率的质变。单链表在尾部追加节点如果不单独维护尾指针就得遍历整个链表才能找到最后一个节点。但循环链表有个巧妙用法如果维护一个 tail 指针指向尾节点那么tail-next就是头节点在尾部插入新节点只需要两次指针更新时间复杂度从 O(n) 降到 O(1)。第三个好处是天然具备“轮转”语义。进程时间片轮转、游戏里的回合制、负载均衡里的轮询本质都是在一组元素中无限循环地轮流访问。循环链表把“当前走到哪、下一步是谁”直接编码在结构里不需要额外维护状态。2.2 什么样的业务场景真的需要它我梳理了一下循环链表在几类场景中确实比其他数据结构顺手。第一类是经典数学模拟问题最典型的就是约瑟夫环。n 个人围成一圈从编号 k 的人开始报数报到 m 的人出列然后从下一个人重新开始直到所有人出列。这种“围成一圈、报数、移除、继续”的流程用循环链表建模最直观——链表本身的环形结构就是那个“圈”删除节点就是“出列”。第二类是操作系统的进程调度。分时系统给每个进程分配固定的时间片时间片用完就切换到下一个进程。这个“下一个进程是谁”的逻辑用循环链表来维护就特别自然当前指针指向正在运行的进程时间片切换时把指针往后移一个节点。第三类是音视频播放器里的循环播放队列。普通播放列表播完就停了循环播放则要求播完最后一首切回第一首。实现起来可以用游标数组加取模运算也能用循环链表区别在于链表对“增删一首歌”不需要搬移其他元素。第四类是游戏开发中的回合制或状态轮转。比如一堆玩家的行动顺序、一组技能特效的循环触发顺序用循环链表把实体串起来事件循环每轮走一个节点代码会非常直白。但也得提醒一句循环链表不是万能的。如果你只是需要一个环形队列用一个数组加两个整型变量维护头尾下标也就是所谓的环形缓冲区在性能和内存连续性上都优于链表。链表节点的指针开销在数据量小的时候不明显数据量大到几十万上百万的时候内存碎片和 cache miss 都是实际要面对的问题。数据结构选型从来不是“哪个结构高级选哪个”而是“哪个结构最贴合操作模式”。3. 核心操作实现照着抄就能跑通3.1 创建与初始化空表的正确打开方式带头节点的循环链表初始化要做两件事给头节点分配内存然后让head-next指向自己。LinkList createEmptyList() { LinkList head (LinkList)malloc(sizeof(LNode)); if (head NULL) { printf(内存分配失败\n); return NULL; } head-next head; // 关键空表时头节点自成环 return head; }这里head-next head是最容易写错的一行。很多人受单链表影响习惯性地写成head-next NULL然后后续所有判断条件全部跟着错。空表时头节点指向自己意味着“转一圈回到头节点”的逻辑从一出生就是成立的后续操作不需要区分“这是空表”的特殊状态。判断一个带头节点的循环链表是否为空标准写法是int isEmpty(LinkList head) { return head-next head; }这个判断和我前面说的初始化逻辑是自洽的。空表的唯一特征就是头节点的 next 指向自己。3.2 尾部插入最后一个节点怎么找尾部插入分两种情况讨论。第一种是最基本的链表不维护尾指针你得先找到最后一个节点。判断最后一个节点的方法很简单某个节点的 next 指向头节点它就是最后一个。int insertAtTail(LinkList head, ElemType data) { LNode *newNode (LNode*)malloc(sizeof(LNode)); if (newNode NULL) return 0; newNode-data data; LNode *p head; while (p-next ! head) { // 注意不是 p-next ! NULL p p-next; } newNode-next head; // 新节点的 next 指向头节点 p-next newNode; // 原来的尾节点指向新节点 return 1; }这段代码里有两个关键点。第一个就是 while 条件必须用p-next ! head而不是p-next ! NULL。第二个是新增节点的 next 要指向 head这一步忘掉的话新节点会成为“断点”整个环就断掉了。但如果你频繁在尾部插入每次都遍历到最后一个节点就太亏了。这时候可以维护一个尾指针 tail永远指向最后一个节点int insertAtTailWithTail(LinkList *tail, ElemType data) { LNode *newNode (LNode*)malloc(sizeof(LNode)); if (newNode NULL) return 0; newNode-data data; newNode-next (*tail)-next; // 新节点指向头节点 (*tail)-next newNode; // 尾节点指向新节点 *tail newNode; // 更新尾指针 return 1; }有了尾指针对尾部插入就是常数时间。这也是循环链表相比单链表在“尾部高频追加”场景下的核心优势。但维护尾指针要付出额外的代价每次删除节点时如果删掉的是尾节点你必须同步更新尾指针否则后面插入和遍历都会出问题。这属于典型的“空间换时间 逻辑复杂度换时间”。3.3 删除节点头节点和尾节点是重灾区删除操作的逻辑框架和单链表是一样的找到被删节点的前驱让前驱的 next 跨过被删节点。但在循环链表里边界情况特别多。删除指定位置的节点int deleteNode(LinkList head, int pos, ElemType *e) { // pos 从 1 开始计数 if (isEmpty(head) || pos 1) return 0; LNode *p head; for (int i 1; i pos p-next ! head; i) { p p-next; } // p 是待删节点的前驱 if (p-next head) return 0; // 位置超出链表长度 LNode *del p-next; if (del head) return 0; // 带头节点时不能删头节点本身 *e del-data; p-next del-next; free(del); return 1; }一个个坑来梳理。第一带头节点时头节点不参与业务数据所以循环里要判断p-next ! head防止 p 走到尾节点之后。第二前驱是最后一个节点、待删节点是第一个数据节点时删除后要把 head 的 next 更新成新的第一个节点这段代码通过p-next del-next自动完成了p 是 headdel-next 是原第二个节点。第三如果待删节点是尾节点删除后需要把前驱的 next 指向 headp-next del-next正好也完成了这一步因为尾节点的 next 就是 head。带头节点的好处在这里体现得很充分删除任意位置节点头节点指针本身不会变不用像不带头节点那样处理“删了头节点后链表的头指针要更新”的问题。如果不带头节点删除头节点的逻辑是另一套int deleteHeadNoHeadNode(LinkList *list, ElemType *e) { if (*list NULL) return 0; // 空表 if ((*list)-next *list) { // 只有一个节点 *e (*list)-data; free(*list); *list NULL; return 1; } LNode *del *list; LNode *tail *list; while (tail-next ! *list) { tail tail-next; } *e del-data; tail-next del-next; // 尾节点指向新的头 *list del-next; // 更新头指针 free(del); return 1; }可以看到不带头节点删除头节点时要先从头遍历找到尾节点再把尾节点指向新头同时更新头指针。一次操作 O(n) 起步代码量也多了一截。这就是我坚持推荐带头节点的原因。3.4 链表的遍历与判空细节遍历循环链表的基本框架是void traverse(LinkList head) { if (isEmpty(head)) { printf(空表\n); return; } LNode *p head-next; while (p ! head) { // 转回头部时停止 printf(%d , p-data); p p-next; } printf(\n); }这里判断结束的条件是p ! head当 p 从第一个数据节点一路走到最后一个数据节点的 next 时如果链表没被破坏最后必然指向 head循环终止。如果有人写着写着while条件是p-next ! head那会漏掉最后一个节点输出少一个数据。遍历里最常见的死循环就是某个节点的 next 被错误地指向了它自己或者环前面的节点导致永远转不回 head。排查思路我在后面专门讲。还有一个细节求链表长度。同样的逻辑条件用p ! head计数器从 0 开始每走一个节点加一回到 head 时结束。这段代码很容易在“最后一个节点是否被计入”上出错写完建议立刻用两三个节点的链表过一遍边界。4. 经典实战约瑟夫环问题4.1 约瑟夫环的问题描述约瑟夫环又常被叫作约瑟夫问题是一个经典的数学仿真题。描述是这样的n 个人编号为 1 到 n按顺时针围成一圈。从编号为 1 的人开始报数每报到 m 的人出列然后从他的下一个人开始重新报数。如此循环直到所有人都出列求所有人出列的顺序。这个问题的天然建模方式就是循环链表。每次报数相当于在链表中移动游标报到 m 的人出列相当于删除一个节点然后游标定位到被删节点的下一个节点继续下一轮。4.2 用循环链表实现的完整思路用带头节点的循环链表实现约瑟夫环步骤如下第一步创建包含 n 个数据节点的循环链表。编号 1 到 n按顺序插入尾部。第二步从第一个数据节点开始模拟报数。报数过程就是指针往后移动 m-1 次因为被删节点自己是报数中的第 m 个那么从当前节点往下数 m-1 个就找到了要删的节点。第三步删除被数到的节点记录编号。第四步重复第二步和第三步直到链表为空。完整代码#include stdio.h #include stdlib.h typedef struct Node { int number; struct Node *next; } LNode, *LinkList; LinkList buildCircle(int n) { LinkList head (LinkList)malloc(sizeof(LNode)); head-next head; LNode *tail head; for (int i 1; i n; i) { LNode *node (LNode*)malloc(sizeof(LNode)); node-number i; node-next head; tail-next node; tail node; } return head; } void josephus(int n, int m) { if (n 1 || m 1) { printf(参数不合法\n); return; } LinkList head buildCircle(n); LNode *pre head; // 指向被删节点的前驱 LNode *cur head-next; // 当前报数起点 while (head-next ! head) { // 报数从头节点算起向后移动 m 个人 // cur 此时指向报数起点 for (int count 1; count m; count) { pre cur; cur cur-next; if (cur head) { // 跳过带头节点 cur cur-next; } } // 此时 cur 指向被删节点 printf(%d , cur-number); pre-next cur-next; free(cur); cur pre-next; if (cur head) { cur head-next; } } printf(\n); free(head); } int main() { josephus(8, 3); return 0; }这段代码里我刻意写了两个跳过 head 判断这是带头节点版本的约瑟夫环最容易崩的地方。因为报数过程可能会绕到 head 上但 head 不参与编号所以必须跳过。另一种更清爽的写法是直接用不带头节点的循环链表存储编号这样报数时指针不用跳过任何节点。两种各有利弊带头节点的好处是删除逻辑更统一坏处是每轮循环都要判断是否遇到头节点浪费一点性能。有个同学问我为什么报数循环是count m而不是count m。这个推导很简单假设 m1报数报到第 1 个人就出列那当前节点直接出列不需要移动指针所以循环执行 0 次count1; count1不满足0 次正确。假设 m2需要移动到当前的下一个节点循环执行 1 次正确。所以count1; countm循环移动 m-1 次恰好对应“数到第 m 个”的语义。4.3 算法复杂度分析用这种模拟方式删除一个人需要报数 m 次一共要删 n 个人所以总时间复杂度为 O(n*m)。n100、m10 时执行 1000 次操作没压力但如果 n10万、m1万那就是 10 亿次操作程序会明显卡顿。数学上其实存在一个递推解法可以在 O(n) 时间内求出最后一个存活者的编号。递推关系为f(1)0f(i)(f(i-1)m) mod i最终f(n)1就是最后一个人的编号。如果题目只要求“最后一个存活的人”的编号用数学方法几乎瞬间出结果。但我建议每个学数据结构的人还是亲手用链表写一遍因为数值解法追求的是结果链表解法强迫你理解“删除节点时前驱怎么找”“环怎么闭合”这些本源性细节。这也是数据结构题目的通性考试和面试考链表本质是在考你有没有对“内存里有一串互相指向的节点”形成直觉。代码跑出来的结果只是表象代码背后对指针的控制能力才是核心竞争力。5. 和单链表、双向链表怎么选5.1 三种链表的结构对比单向循环链表、普通单链表、双向链表三者各有各的脾气。用一个表格来对比最直观对比维度单链表单向循环链表双向链表尾节点 next 指向NULL头节点通常 NULL 或头节点遍历结束条件p NULLp headp NULL 或 p head从尾到头遍历不支持不支持支持已知节点前驱的删除需遍历找前驱需遍历找前驱O(1) 直接通过 prev 指针尾部插入无尾指针O(n)O(n)O(n)有尾指针时 O(1)尾部插入有尾指针O(1)O(1)O(1)内存额外开销每节点 1 个指针每节点 1 个指针每节点 2 个指针结构复杂度低中高单链表的优势是简单遍历到头就停不会出现“意外成环”的问题。缺点是只能单向走处理尾节点总要花心思。双向链表的优势是任意方向都能走删除节点时可以快速拿到前驱代价是每个节点多一个指针的内存占用插入删除时也要多维护一组指向关系对初学者来说最容易写出前后指针不一致的 bug。单向循环链表刚好处在一个中间位置保留了单链表“每节点一个指针”的内存优势同时把“循环访问”这个能力补上了。但它没有解决“往前看”的问题你要找某个节点的前驱还是得从头开始遍历。5.2 选型建议结合实际开发经验我总结了一套简单的选型判断流程。先问自己数据是否需要在首尾之外频繁增删如果不需要数组往往就是最优解不要为了用链表而用链表。如果需要频繁增删再问第二个问题是否需要双向访问如果应用场景里频繁出现“给定一个节点删掉它前面的节点”或者“从末尾翻到开头”这类操作直接选双向链表省得自己维护一堆前驱指针。如果不需要双向访问第三个问题数据访问是否要求循环轮转如果答案是肯定的比如轮转调度、约瑟夫环、循环播放选单向循环链表。如果只是一条直线的序列单向链表就足够强行加循环反而多了成环的隐患。数据结构选型的本质是“用空间换时间、用复杂度换能力”的权衡。每次增加一种结构上的便利背后都有额外成本和潜在的 bug 风险。循环链表省了“回到起点”的计算却要你在每一次修改指针时都记得“别让环断开”。6. 从头到尾的坑调试排查实录6.1 死循环排查最常见的翻车现场我第一次写循环链表遍历时遇到程序卡死第一反应是检查遍历代码看了半天没看出问题最后才发现是初始化时把head-next写成了NULL。遍历条件写的却是while (p-next ! head)p 起初是 headp-next是 NULLNULL 不等于 head于是进入循环体但 p 永远找不到 head最终陷入死循环。死循环排查第一步检查是不是遍历的终止条件写错了。第二步检查是不是某次插入时新节点的 next 没有被正确指向 head导致链表“半截断环”。第三步用 IDE 断点或者手动打印节点指针值核心思路是观察每个节点的 next 指向找出那个指向不正确的节点。有一个非常实用的打印技巧遍历时加计数器到链表中节点数再加一个就强制停止同时打印出当前节点的指针地址和 next 地址。这样如果链表真的断了或者成环了能从指针地址上直接看出来到底是谁在搞鬼。6.2 头节点丢失问题不带头节点的循环链表里删除头节点后如果忘记更新 List 指针整个链表就找不到了后面的遍历和释放直接访问非法内存。这个问题在带头节点的版本里不存在所以再次推荐带头节点。即使带头节点也有一个隐蔽坑你想把整个链表清空重来写了个循环释放所有数据节点结果释放完发现 head 的 next 没重新指向 head后续对这个链表再次判空或插入时程序直接崩溃。清空链表的正确写法void clearList(LinkList head) { LNode *p head-next; while (p ! head) { LNode *temp p; p p-next; free(temp); } head-next head; // 恢复空表状态 }注意最后一行没有它这个链表就是一堆指向已释放内存的悬空指针任何后续操作都是未定义行为。6.3 内存泄漏与野指针循环链表的释放比单链表多一层麻烦。单链表从 head 开始逐个释放就完事了循环链表如果你还按单链表的思路写释放完最后一个数据节点它的 next 还指向头节点头节点里的指针也指向一个已释放的内存整个链表处于一个残缺状态。释放整个链表的正确思路是先把环断开再逐个释放。具体做法是让头节点的 next 指向 NULL让链表变成一个“残缺的单链表”然后按普通单链表的释放逻辑处理。约瑟夫环的每次删除则相对安全因为删除节点之前已经通过前驱节点把该节点的链接关系更新好了free 掉被删节点后不会影响剩余节点的环结构。另外还要提醒一点写链表代码时养成“释放后立即置空”的习惯。free(p)之后p 指针本身还在它指向的内存是“已回收”状态但如果你不小心再用 p 访问数据程序不会立刻报错而是产生一个难以复现的偶发崩溃。这种野指针 bug 在大型项目里定位成本极高。从我个人的教学和开发经验看单向循环链表最大的价值不在于“这道题你会不会写”而在于它强迫你建立“指针操作是全局性的”这个意识——你改的每一个 next 都可能影响链表其他位置的访问路径。你在单链表上可以靠直觉蒙混过关的错误在循环链表里会在下一次循环转回来时暴露无遗。扎扎实实地把循环链表写对了你对数据结构底层逻辑的理解会上一个台阶。