说实话单链表大部分人都能写但一到“单循环链表”就懵。我在辅导同学的时候发现大家不是不理解“最后一个节点指向头节点”这个概念而是不会处理那个“环”——循环遍历时容易死循环删除最后一个节点时容易断链插入时老是搞不清要不要更新尾指针。这篇文章我不打算把教材再抄一遍而是带着具体的C语言函数实现把单循环链表从头到尾拆开为什么用尾指针而不是头指针插入删除的边界到底怎么判约瑟夫问题怎么用它解以及我自己调试时总结出来的几个易错点。这篇文章适合正在学数据结构、准备期末考或者应付面试手写代码的读者。跟着把代码敲一遍把注释读进去基本上就能把单循环链表这块吃透了。1. 单循环链表它到底比单链表强在哪里1.1 结构上的一个小改动带来的是遍历方式的质变单循环链表和普通单链表的差别看起来小得不能再小普通单链表的最后一个节点next指向NULL单循环链表的最后一个节点next指回第一个节点。但就是这一根“回指”的线改变了整个链表的遍历逻辑。普通单链表的遍历本质上是一个“单向走到底”的过程。你要判断是否走完只能看当前节点是不是NULL。而单循环链表的遍历起点和终点是同一个节点判断条件变成了“是否回到起点”。这意味着什么意味着只要你手里有任意一个节点的地址你就可以走遍整个链表不需要头指针也能完成遍历、查找、计数这些操作。另一个容易被忽略的好处是头尾操作的速度。普通单链表想做“在尾部插入”必须从头节点一路遍历到尾节点时间复杂度是 O(n)。如果你写的是单循环链表并且你持有的是尾指针那么尾插操作只需要改两个指针时间复杂度直接变成 O(1)。这个提升在很多实际场景里非常关键。1.2 单链表的尾巴就是循环链表的头描述单循环链表时我习惯用一个说法它没有绝对的“头”和“尾”只有“当前节点”和“下一个节点”。尾巴的下一个就是头头的前一个逻辑上的就是尾。在实际编码中这个特性带来一个思维定势的改变。普通单链表你写p-next时心里默认它是一个“单向箭头”但在循环链表里你必须时刻提醒自己p-next总有一天会指回你已经访问过的节点。举个最简单的场景你想在循环链表中查找某个值。在单链表里你写while (p ! NULL)到了循环链表这个条件会失效——因为 p 永远不会变成 NULL它只会转圈。正确做法是先记录下起始节点然后do...while (p ! start)或者先走while (p-next ! start)。很多初学者的死循环都是从这里来的。1.3 循环链表适合解决的三个典型场景从实际应用看单循环链表最值得关注的三个场景分别是轮流调度操作系统里的时间片轮转、游戏里的出牌顺序这类“转一圈回到原点”的逻辑天然适合用循环链表建模。约瑟夫问题一群人围成一圈报数出列每次淘汰后要继续从下一个位置开始数。这个场景用循环链表实现几乎不用思考“怎么回到开头”。环形缓冲区如果数据量不大但要求按顺序循环覆盖循环链表比数组取模运算更直观。这篇文章的重点还是“函数实现”我会把大量篇幅放在代码上。但你知道它解决什么问题之后看代码会更容易理解为什么这么设计。2. 表示方式的选择尾指针而不是傻等首尾相接2.1 节点结构怎么定义C语言里单个节点的定义和单链表完全一样没有任何特殊之处typedef struct Node { int data; struct Node *next; } Node;data这里用int是为了示例简单。实战中你可以改成任意业务数据类型甚至用一个void *去存通用对象。但数据结构学习阶段int最合适因为它方便打印验证。真正有讲究的地方在于这条链表怎么“被表示”。同样是循环链表不同的表示方式实现难度差别很大。2.2 三种表示方案对比我见过的实现方案大致有三种方案一头指针表示。就是用一个head指针指向首节点空表时head NULL。这是最贴近单链表习惯的写法但有个尴尬问题你想在尾巴上插入还是得从头遍历到尾那循环链表相对于单链表的性能优势就没了。方案二尾指针表示。用一个tail指针指向尾节点tail-next就是首节点。空表时tail NULL。这种方案下头插和尾插都是 O(1)找首节点也是 O(1)代价是你的大脑要习惯“尾指针的下一个节点才是头节点”这个绕弯。方案三带哨兵节点的循环链表。给链表增加一个固定的头节点这个节点不存数据只作为整个链表的“锚点”。哨兵的next指向真正的首节点空表时它的next指向自身。这三个方案的取舍我做了个表方案空表判断尾部插入删除首节点遍历终止条件代码难度头指针head NULLO(n) 遍历O(1)p head容易尾指针tail NULLO(1)O(1)p tail-next中等哨兵节点head-next headO(1)O(1)p head中等我个人在写算法题和教学实践里最喜欢尾指针表示。原因很简单它让头插和尾插的代码几乎一样而且当你需要“从某个节点开始走一圈”的时候起止条件写起来很自然。接下来所有函数我都基于尾指针表示来写。2.3 接口约定统一返回尾指针基于尾指针的写法有一个大坑就是函数返回值必须设计成“新尾指针”。因为很多操作都会改变尾节点尾插后新节点变成尾节点函数要返回新节点地址。删除尾节点后原来的倒数第二个节点变成新的尾节点函数要返回它。删除最后一个节点后链表变空函数要返回NULL。如果函数不把新的尾指针返回来调用方手里的tail就失效了后续操作全部会崩。所以这套接口我统一约定所有可能改变链表结构的函数都返回新的tail调用方必须用返回值重新赋值。我先列出这套接口后面逐个实现Node *initList(void); // 初始化直接返回 NULL int isEmpty(Node *tail); // 判空 void printList(Node *tail); // 遍历打印 Node *insertAtHead(Node *tail, int val); // 头插 Node *insertAtTail(Node *tail, int val); // 尾插 Node *insertAtPos(Node *tail, int val, int pos); // 从0开始计数插入 Node *deleteAt(Node *tail, int pos, int *val); // 按位置删除 Node *deleteByValue(Node *tail, int key, int *found); // 按值删除 Node *destroyList(Node *tail); // 销毁全部节点这里的“头插”和“尾插”都是逻辑上的叫法。循环链表中头插的本质是在尾节点后面插入新插入的节点成为新的首节点但尾指针不变尾插的本质也是尾节点后面插入只是新节点成为新的尾节点。3. 基础函数逐一实现初始化、插入、删除、遍历、销毁3.1 初始化和判空代码越简单越容易错初始化逻辑特别简单空表就是没有节点直接返回NULLNode *initList(void) { return NULL; }判空也简单int isEmpty(Node *tail) { return tail NULL; }但这里有个隐含问题既然空表就是NULL那初始化函数还有必要存在吗从纯实现角度说确实没必要。但从接口统一角度说我宁愿保留。因为后续如果某天你决定改为哨兵节点方案initList就要真正创建一个节点了接口不变改动成本才会低。遍历打印是调试循环链表最常用的工具void printList(Node *tail) { if (tail NULL) { printf([空链表]\n); return; } Node *start tail-next; Node *p start; do { printf(%d , p-data); p p-next; } while (p ! start); printf(\n); }注意我用了do...while而不是while。原因是一个节点的链表也要打印出来。如果写成while (p ! start)单节点会正常走完一次因为你进循环前已经确定 p 不等于 start但如果写成while (p ! tail)这种形式最后一个节点永远打印不到很多人的 bug 就从这里来的。3.2 头插与尾插一模一样的操作只是返回值不同先看头插Node *insertAtHead(Node *tail, int val) { Node *p (Node *)malloc(sizeof(Node)); if (p NULL) { fprintf(stderr, malloc failed\n); exit(EXIT_FAILURE); } p-data val; if (tail NULL) { p-next p; // 只有一个节点自己指向自己 return p; } p-next tail-next; // 新节点指向当前的首节点 tail-next p; // 尾节点指向新节点 return tail; // 尾节点没变返回原来的 tail }再看尾插Node *insertAtTail(Node *tail, int val) { Node *p (Node *)malloc(sizeof(Node)); if (p NULL) { fprintf(stderr, malloc failed\n); exit(EXIT_FAILURE); } p-data val; if (tail NULL) { p-next p; return p; } p-next tail-next; // 新节点指向当前的首节点 tail-next p; // 旧尾节点指向新节点 return p; // 新节点成为尾节点 }你仔细对比这两段代码会发现中间那三行几乎一模一样唯一的区别就是最后return的是谁。头插把新节点放到tail-next的位置上尾巴还是原来那个所以return tail尾插把新节点接在旧尾巴后面新节点变成尾巴所以return p。很多初学者写循环链表时最容易在“头插”里把返回值写成p。结果就是调用方手里的 tail 指向的已经不是尾节点了下一次insertAtTail时新节点会接在错误的位置上链表顺序直接乱掉。3.3 按位置插入边界条件多的函数位置编号我约定从 0 开始pos 0表示插入后新节点在首节点位置。为了体现循环链表的特色我没有写“越界终止”而是采用“越界就自动变成尾部插入”的策略。Node *insertAtPos(Node *tail, int val, int pos) { if (pos 0) { return insertAtHead(tail, val); } if (tail NULL) { // 本来空表任何位置都是第一个节点 return insertAtTail(tail, val); } // 先找到“第 pos-1 个节点”它的后面就是插入位置 Node *prev tail; int i 0; while (i pos - 1) { prev prev-next; i; if (prev tail) { // 已经绕回尾部说明 pos 超出了链表长度改为尾插 return insertAtTail(tail, val); } } Node *p (Node *)malloc(sizeof(Node)); if (p NULL) { fprintf(stderr, malloc failed\n); exit(EXIT_FAILURE); } p-data val; p-next prev-next; prev-next p; // 如果插入位置发生在尾节点之后新节点就是新的尾节点 if (prev tail) { return p; } return tail; }这里的技巧在于prev的初值是tail。你可能会奇怪为什么找第 0 个位置的前驱会是尾巴因为在循环链表里首节点的前驱本来就不是一个“真正的节点”它就是尾节点。这一点恰好是循环链表的美妙之处也是很多人一时转不过弯的地方。插入后如果prev tail说明新节点插在了“尾巴后面”别忘了此时新节点已经实际成为尾节点函数必须把p返回回去。3.4 按位置删除先绕圈再断链删除节点的核心是先找到“待删节点”再通过它的前驱节点修改next指针。循环链表的特殊之处在于尾的前驱不是 NULL而是倒数第二个节点首的前驱则是尾。所以删除逻辑以下要特别注意“删的是首节点”还是“删的是尾节点”。Node *deleteAt(Node *tail, int pos, int *val) { if (tail NULL) { *val 0; return NULL; } Node *prev tail; // 待删节点的前驱一开始是尾节点 Node *cur tail-next; // 待删节点一开始是首节点 int i 0; // 让 cur 前进到第 pos 个节点prev 跟着它同步移动 while (i pos) { prev cur; cur cur-next; i; if (cur tail-next) { // 绕回到起点说明 pos 越界不删 *val 0; return tail; } } // 如果链表只有一个节点删完就空了 if (cur tail prev tail) { *val cur-data; free(cur); return NULL; } prev-next cur-next; if (cur tail) { tail prev; // 删的是尾节点新的尾节点是 prev } *val cur-data; free(cur); return tail; }这段代码里最容易被忽略的就是“链表只有一个节点”这种情况。此时cur tail且prev tail如果直接走下面的prev-next cur-next那cur-next cur相当于把tail-next指向了它自己然后 free 掉cur就变成野指针访问了。所以必须单独判断让返回值变成NULL。还有一个常见的想法是“按值删除”即删除第一个 data 等于 key 的节点。我个人在函数实现中更推荐按位置删除因为它在测试时更容易确认结果。如果确实需要按值删除逻辑其实差不多先记下起点然后do...while扫一圈找到节点后用同样的“改前驱的 next”机制处理。这里不贴完整代码了原理是一样的。3.5 销毁链表别忘了把环先“解开”销毁函数最容易犯的错误是只把tailfree 掉剩下的节点全部泄漏。循环链表的销毁必须走完一整圈Node *destroyList(Node *tail) { if (tail NULL) { return NULL; } Node *p tail-next; Node *q; while (p ! tail) { q p; p p-next; free(q); } free(tail); return NULL; }这段代码的逻辑是从首节点开始遍历遇到尾节点就停下来之前的每个节点都释放。最后单独释放尾节点。这个写法在“只有一个节点”的时候也能正常工作——while 条件不满足直接释放 tail。调试时你可以在destroyList前后打点。释放完成后一定要把外部变量重新赋值为NULL。很多程序崩溃不是销毁函数写错了而是调用完没有tail destroyList(tail);后面又去访问已经释放的内存。4. 约瑟夫问题循环链表最经典的考题4.1 问题描述与建模思路约瑟夫问题Josephus Problem的经典描述是这样的n 个人围成一圈从某个人开始报数报到 m 的人出列然后从下一个人开始重新报数报到 m 的人再出列直到最后只剩一个人。这个人的编号就是答案。用单循环链表解决约瑟夫问题几乎是“量身定做”的因为“围成一圈”就是循环链表的结构。每个人是一个节点节点里存编号。出列就是删除节点。下一轮从下一个人开始数就是让指针从当前节点的next继续往前走。题目要求“从第一个人开始报数报到 m 出列”在链表里怎么定位“从某个人开始报数”如果我们在实现中把尾指针作为“当前节点”的哨兵让待删节点始终是“当前节点的下一个”每次移动 m-1 步报数逻辑就会清晰很多。4.2 基于尾指针的完整实现直接给出完整函数void josephus(int n, int m) { Node *tail NULL; // 1. 建立从 1 到 n 的循环链表 for (int i 1; i n; i) { tail insertAtTail(tail, i); } // 2. 开始淘汰节点直到只剩一个 Node *prev tail; // prev 永远指向待删节点的前驱 while (tail ! NULL tail-next ! tail) { // 报数 m 次相当于让 prev 前进 m-1 步 for (int i 1; i m; i) { prev prev-next; } // 待删节点是 prev 的下一个 Node *q prev-next; printf(%d 出列\n, q-data); prev-next q-next; if (q tail) { tail prev; // 如果删的是尾节点更新尾指针 } free(q); } if (tail ! NULL) { printf(最后剩下%d\n, tail-data); free(tail); } }如果你在 main 里调用josephus(7, 3)会看到很多教材上的经典输出序列先从 3 开始出列接着 6、2、7、5、1最后剩下 4。这个结果也是验证实现正确性的一个标准用例。4.3 为什么 prev 指针能避免边界判断地狱很多同学第一次写约瑟夫问题时喜欢直接用一个 cur 指针“数到谁就删谁”。这会导致一个大麻烦当你删掉 cur 指向的节点后cur已经指向了被释放的内存你必须立刻把cur重定向到它的后继并且下一次报数要从这个后继开始。用prev指向“待删节点的前驱”就不会有这个问题。因为q prev-next删掉 q 之后prev还在链表里prev-next已经指向了下一个报数人。下次循环只需要继续prev prev-next走 m-1 步即可。这段实现里最值得注意的一行是tail prev。如果待删节点是当前的尾节点那么它的前驱prev才是删除后新的尾节点。要在 free 之前判断因为 free 之后就不能再访问q-data了。这属于指针使用的“常识”但恰恰是初学最容易翻车的地方。5. 调试单循环链表最容易踩的坑和定位方法5.1 四个典型错误清单写单循环链表出错的规律性很强。我把平时见到的错误整理成一张表典型错误表现原因遍历时写成while (p ! tail)尾节点永远不打没有理解尾指针指向的才是尾节点循环条件不记录起点打印无限循环程序卡死不知道什么时候该停删除唯一节点后还访问旧指针不确定的崩溃删空链表后没有把 tail 置为 NULL插入尾部后没有接收返回值尾插变成头插链表顺序乱忽略了函数返回新尾指针的约定其中第一个错误很好修复但理解起来有点绕。我举个例子如果你用一个tail指针表示链表那么while (p ! tail)会在 p 走到尾节点时停下这意味着尾节点的数据没有被处理。而你又不能简单改成while (p ! NULL)因为循环链表永远不会 NULL。正确写法就是我在printList里示范的do...while (p ! start)——先把当前节点处理掉再判断是否回到起点。5.2 辅助调试三件套我不管写什么链表都会在调试阶段固定加三个辅助函数void printNode(Node *node) { printf(当前节点地址%p, data%d, next%p\n, (void *)node, node-data, (void *)node-next); } void printFullList(Node *tail) { if (tail NULL) { printf(链表为空\n); return; } Node *p tail; do { printNode(p); p p-next; } while (p ! tail); } void checkSelfLoop(Node *tail) { if (tail ! NULL tail-next tail) { printf(警告只有一个节点且它自己指向自己\n); } }printNode能帮你确认每个节点的地址和 next 指向。printFullList比printList更能暴露循环链表的“链接顺序问题”因为你会看到每个节点的指针值。checkSelfLoop则专门揪出“只有一个节点时指针指向自己”的边界情况。5.3 用最小数据复现问题链表调试最忌讳一上来就搞 n 1000 的约瑟夫问题。我建议永远先用 n 1、n 2、n 3 跑一遍。n 1 时检查自循环n 2 时检查头尾互指n 3 时检查删除尾节点后尾指针的更新。举个例子如果你要验证insertAtTail是否正确可以写这样一段测试代码Node *tail NULL; tail insertAtTail(tail, 1); printFullList(tail); // 应该打印 1且 next 指向自己 tail insertAtTail(tail, 2); printFullList(tail); // 应该打印 1-2-(1) tail insertAtTail(tail, 3); printFullList(tail); // 应该打印 1-2-3-(1)每次打印后立刻肉眼比对尾节点。发现顺序不对基本能锁定是在哪一步丢掉了返回值或者哪一步的next指错了。定位问题后再去看具体函数效率比自己从头读代码高得多。6. 从练习代码到工程模块接口改进与扩展方向6.1 用一个结构体把 tail 和 length 打包上面的实现全部围绕Node *tail展开函数返回值也是Node*这样写教学代码很直观实战里却容易出问题——万一调用方忘了接收返回值尾指针就错了。更工程化的做法是定义一个链表管理器typedef struct { Node *tail; int length; } CircList;所有操作都接收CircList *list函数内部去修改list-tail和list-length。这样就不再依赖返回值了调用方也不容易用错。代价是接口变重每个函数都要多包一层结构体。这其实是“轻量指针式”和“封装式”编程风格的一次取舍。如果是刷题、考试手写代码建议直接用我前面示范的纯尾指针式简短清晰。如果是在公司写一个长期维护的模块我会毫不犹豫选择封装结构体。因为length字段会带来一个额外好处判断越界时不用再绕一圈去数节点个数了pos list-length就可以提前返回。6.2 加哨兵节点到底值不值前面提到了哨兵节点方案很多人问加一个哨兵是不是比尾指针更“正规”。我的看法是哨兵节点最大的优点是让“空表”也有一个稳定节点遍历和删除的终止条件统一成p head写起来不容易出错。但代价是浪费一个节点空间并且插入时要想清楚“哨兵之后第一个带数据的节点”才是真正的头节点。如果你自己练习两种方案会发现很有意思带哨兵的循环链表空表时哨兵的 next 指向自己这其实就是在告诉读者“这个链表是空的转一圈回到了原点”。我觉得学数据结构不能只认一种写法至少要知道三种方案的存在。面试时能主动说出“我选尾指针是因为尾插 O(1)如果项目里频繁删除且需要判空前置我会考虑哨兵”考官很难挑出毛病。6.3 循环链表在实际项目中的落点最后聊聊实际场景。我在平时工作中遇到过的最典型应用是定时器轮询。一批任务需要按照时间片依次执行执行完最后一个任务后要从头再开始。用循环链表存储任务节点核心调度函数只需要保存一个“当前任务指针”每轮结束执行current current-next代码非常优雅。另一个常见场景是消息队列的“广播重播”。如果有一条消息需要发给所有订阅者而订阅者列表恰好是循环链表发送程序只需要拿到任意一个节点然后一圈圈遍历直到回到起点。这个逻辑比数组遍历多了一个好处动态增删订阅者时不会像数组那样引起大量数据搬移。如果你把循环链表和双链表结合还能改造出更高级的“双向循环链表”。C语言的std::list如果你用 C底层就是双向循环链表加哨兵节点。理解了单循环链表的实现细节再看那些容器源码会轻松很多。我个人在实际写代码时最深的感受是循环链表并不比单链表难多少难的是“转换思路”。一旦你把“终点是 NULL”这个惯性丢掉接受“终点就是起点”所有函数都会变得自然起来。建议你拿到这篇代码后不要只读打开编译器从initList开始敲每敲完一个函数就打印一次链表结构。把代码跑顺了再把这一段代码转换成双向循环链表。那时候你就不是“会背”循环链表而是真正理解它了。