如果有人问我GESP 5级的数据结构考点里最容易被扣分的是哪一块我的答案一定是循环链表。很多同学把单链表背得滚瓜烂熟一看到“循环”两个字就开始发怵遍历怎么写终止条件是什么删除节点怎么搞其实循环链表和单链表在代码上只差一行指针但这一行指针改完之后整个思维模式都得跟着变。这篇内容就是围绕循环链表这个考点把我自己备考和辅导过程中反复踩过的坑、总结出来的写法一次讲透。无论你是正在准备GESP 5级考试还是刚学完单链表想进阶这篇文章都适用。我会从最基础的结构体定义讲起一直讲到约瑟夫环的完整实现再把删除、反转、内存释放这些容易翻车的操作拆开揉碎了说清楚。1. 循环链表到底是啥从单链表到循环链表只改了一行指针1.1 先把链表家族的关系捋清楚GESP 5级考试里链表家族常见的形态有四种单链表、双向链表、单向循环链表、双向循环链表。很多同学概念背得挺熟但一上机写代码就乱根子在于没有把它们的结构差异理清楚。普通单链表的结构是每个节点有一个数据域和一个 next 指针最后一个节点的 next 指向 nullptr。遍历的时候用一个 while(p ! nullptr) 就能从头走到尾走到空指针自然停。这是所有链表操作的地基。循环链表最大的区别就是一句话最后一个节点的 next 不再指向 nullptr而是指向链表的第一个节点。也就是说整个链表首尾相接变成了一个环。这个改动带来的连锁反应很明显遍历时没有了“终点”如果还用 p ! nullptr 判断程序就会一直转圈直到超时。用生活里的场景来类比单链表是一条单向火车线路开到终点站就没路了列车员可以下班循环链表是环形跑道没有终点这个概念你跑完一圈之后又会回到起点所以你必须自己记住“我已经跑了几圈”。下面这个表格把几个关键差异列出来复习的时候可以反复看对比项单链表单向循环链表双向循环链表尾节点 nextnullptr指向首节点指向首节点头节点 prev无无指向尾节点遍历终止条件p ! nullptrp ! headp ! head删除已知节点需要找前驱需要找前驱不需要找前驱空表判断head nullptrhead nullptr 或 head-next headhead nullptr 或 head-next head1.2 循环链表让 GESP 5级考点变难的三个原因第一个原因是终止条件变了。单链表里到处是 nullptr 判断循环链表里则没有天然的“停止标志”你必须自己设定一个停止点。很多考生在考场上习惯性写 while(p ! nullptr)结果一运行就死循环白丢分。第二个原因是指针修改顺序更容易出错。单链表中断链了最多是某个节点找不到了循环链表中断链轻则输出顺序错乱重则马上死循环。比如删除节点时如果先 delete 了节点再改前驱的 next程序大概率直接崩溃。第三个原因是循环链表的应用题场景多。约瑟夫环、猴子选大王、报数出列这类题目天然就适合用循环链表来模拟。命题人特别爱把“循环链表操作”和“模拟算法”结合起来考所以它不只是一个数据结构知识点还是一个高频算法题载体。1.3 结构体定义与初始化写代码前先把节点的结构体定义好。循环链表和单链表在结构体定义上完全一致没有任何特殊字段struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} };这里有一点要提醒用 new 创建节点后next 默认是 nullptr。如果你是在建环的过程中创建节点一定要记得在最后手动把尾节点的 next 指向 head否则你建出来的是一个普通单链表而不是循环链表。初始化空链表时最简单的方式是让头指针 head nullptr。但考试里还经常出现另一种形式带头结点。所谓带头结点就是额外分配一个 dummy 节点它的 data 不存有效数据next 指向真正的首节点不带头结点则是 head 直接指向首节点。这两种形式都能实现循环链表差别主要体现在空表判断和删除首节点的写法上。考试时一定要看清题目说的是“第一个节点”还是“头结点”别看漏了。2. 循环链表的构建与遍历写代码前必须想清楚的三件事2.1 尾插法建循环链表最后一步是灵魂构建循环链表最常用的方法是尾插法。所谓尾插就是每次把新节点挂在当前链表末尾。核心代码如下Node* createCircularList(int n) { if (n 0) return nullptr; Node* head new Node(1); Node* tail head; for (int i 2; i n; i) { Node* p new Node(i); tail-next p; tail p; } tail-next head; // 关键一步收尾相接 return head; }注意最后一行 tail-next head。这就是循环链表和普通单链表在代码上的唯一区别。前面插入的过程和单链表完全一样只有最后收尾时把尾指针接回头部才算是把环封上了。如果你用头插法建循环链表情况会更麻烦。头插法永远把新节点插在 head 前面每插入一个节点头部就变了最后还要让原来的尾节点指向新的 head。这个过程中“首节点是谁”一直在变容易把自己绕晕。所以建议考试时优先用尾插法。2.2 遍历的终止条件怎么写才不死循环有了循环链表遍历就变成了一件需要小心设计的事。普通单链表的遍历Node* p head; while (p ! nullptr) { // 处理节点 p p-next; }循环链表里不能这么写因为没有任何节点的 next 是 nullptr。正确的写法是利用“回到起点”来判断结束。常见写法有两种写法一先处理 head然后从 head-next 出发走到再次遇到 head 时停止。Node* p head-next; while (p ! head) { // 处理节点 p p p-next; }写法二用 do-while先执行一次循环体再判断避免一开始 p 就等于 head 导致循环体一次都不执行。Node* p head; do { // 处理节点 p p p-next; } while (p ! head);我自己的习惯是如果要遍历所有节点优先用 do-while因为代码逻辑最直白也不会漏掉 head 节点。如果只是从第二个节点开始遍历用 while 写法更干净。关键是你要在写之前就想清楚“遍历的起点是谁终点是谁”而不是写完再对着空指针一顿找。2.3 带头结点还是不带头结点考试怎么选这是个很现实的取舍问题。带头结点的循环链表空表时 head-next 指向自己也就是 head-next head。这样在插入、删除时边界判断更统一不需要专门处理 head 为空的情况。不带头结点的循环链表空表时 head nullptr。当链表只剩下一个节点时这个节点的 next 指向它自己形成自环。这种状态在删除操作时非常考验细节一旦处理不当头指针就丢了。我的建议是如果题目没有明确要求优先用带头结点版本。考试时少一个边界条件就少一分出错的可能。场景带头结点不带头结点空表判断head head-nexthead nullptr删除首节点操作统一需要更新头指针遍历终止p headp head只有一个节点容易处理自环需小心3. 用循环链表实战约瑟夫环GESP 5级最爱考的场景3.1 约瑟夫环的题意和报数步数怎么定约瑟夫环是循环链表最经典的练习题也是 GESP 5级考试里出现频率很高的算法题。题目通常是这样的n 个人编号从 1 到 n围成一圈坐好。从编号 1 的人开始报数数到 m 的人出列然后下一个人重新从 1 开始报数直到所有人出列。题目可能要求输出完整出列顺序也可能只要求输出最后一个幸存者。这题用循环链表模拟的思路非常自然人围成一圈正好对应循环链表的环。模拟过程是构建编号为 1 到 n 的循环链表。从 head 开始找到报数到 m 的那个人。删除这个人链表继续保持环形。重复第 2 步直到只剩一个人。这里最容易搞错的是报数步数。很多同学会写“走 m 步”结果发现删除的目标节点不对。道理很简单报数从当前节点自己开始当前节点就是报“1”的人所以要数到 m实际上是让指针向后移动 m-1 次。如果走 m 步你就多走了一个节点属于典型的 off-by-one 错误。3.2 完整代码实现与运行结果直接给出完整可运行的代码#include iostream using namespace std; struct Node { int data; Node* next; Node(int val) : data(val), next(nullptr) {} }; void josephus(int n, int m) { if (n 0 || m 0) return; // 1. 构建循环链表 Node* head new Node(1); Node* tail head; for (int i 2; i n; i) { Node* cur new Node(i); tail-next cur; tail cur; } tail-next head; // 2. 模拟报数出列 Node* prev tail; // prev 指向要删除节点的前一个节点 Node* cur head; int remaining n; while (remaining 1) { // 从 cur 开始报数走 m-1 步到达要删除的节点 for (int step 1; step m; step) { prev cur; cur cur-next; } // 输出并删除当前节点 cout cur-data ; prev-next cur-next; delete cur; cur prev-next; remaining--; } cout cur-data endl; delete cur; } int main() { josephus(5, 3); return 0; }运行结果3 1 5 2 4这里有个细节prev 初始指向 tail也就是 head 的前一个节点。这样在第一次删除时cur 从头开始走 m-1 步prev 能正确停留在 cur 前面。每次删除后cur 被更新为 prev-next也就是出列人的下一个节点下一轮报数自然从它开始。3.3 边界情况与复杂度分析约瑟夫环有几个边界情况容易翻车单独拎出来说。当 m 1 时不需要报数直接依次从头删到尾。上面的代码也能正确处理因为 for 循环走 m-1 0 步每次删除的就是 cur 自己。当 n 1 时建出来的链表只有一个节点它自己指向自己。while 循环条件 remaining 1 不成立直接输出唯一节点逻辑没问题。当 m 很大时比如 n 5m 100循环链表会绕上很多圈才删除一个人。链表模拟的时间复杂度是 O(n*m)如果 n 和 m 都很大考试就可能超时。GESP 5级通常不会故意给这种极端数据但你要知道这个瓶颈存在。如果题目只问最后一个幸存者可以用递推公式直接算不用链表模拟。4. 删除、反转与内存维护循环链表的进阶操作4.1 删除节点的标准三步删除循环链表中的某个节点最重要的前提是找到它的前驱节点。因为循环链表里的 next 指针是单向的你只知道当前节点无法直接拿到它的前驱。标准的删除过程是三步找到要删除节点的前驱节点 prev。让 prev-next 指向要删除节点的下一个节点。delete 掉目标节点。代码模板Node* deleteNode(Node* head, Node* target) { if (head nullptr || target nullptr) return head; Node* prev head; while (prev-next ! target) { prev prev-next; if (prev head) { // 遍历一整圈都没找到 target说明它不在链表中 return head; } } prev-next target-next; delete target; return head; }注意如果删除的是头节点本身并且是不带头结点的链表删除后头指针要更新为原来的第二个节点。一旦漏了这一步整个循环链表就找不到了。4.2 复制删除法的是与非有一种取巧的删除方法叫复制删除法把下一个节点的数据复制到当前节点然后删除下一个节点。这样不需要找前驱代码看起来更简洁。// 删除 cur但不知道 cur 的前驱 cur-data cur-next-data; Node* tmp cur-next; cur-next tmp-next; delete tmp;这个方法在约瑟夫环问题里特别好用因为当前的 cur 正好是要删除的节点你不需要额外维护 prev。但复制删除法有坑如果 cur 是链表中的唯一节点那么 cur-next 指向自己复制自己再删自己逻辑直接崩了。还有一种情况如果 cur 恰好是头节点复制后头节点的 data 会被覆盖成下一个节点的值这等于丢失了原来的头节点数据。所以用之前一定要判断节点数量和位置。4.3 循环链表的反转怎么处理链表反转是 GESP 里另一个高频操作循环链表也偶尔会考到。思路和单链表反转类似只是遍历时要通过环形终止条件来控制循环。参考实现Node* reverseCircular(Node* head) { if (head nullptr || head-next head) { return head; } Node* first head; Node* prev nullptr; Node* cur head; do { Node* next cur-next; cur-next prev; prev cur; cur next; } while (cur ! first); head-next prev; // 原 head 变成新链表的尾节点接回新头节点 return prev; // 新头节点是原链表的尾节点 }一开始我看到这个代码也愣了一会儿其实核心就两点把每个节点的 next 方向反过来然后把环重新封闭。原链表是 1-2-3-1反转后变成从 3 开始的 3-2-1-3。如果你还是从原来的 head1 开始打印顺序会变成 1,3,2所以反转后一定要接收返回值用新头节点开始遍历。4.4 内存释放与野指针new 出来的节点用完之后要 delete这是 C 考生的基本素养。但循环链表释放内存时有一个常见的坑不能像单链表那样一直访问 p-next 直到 nullptr因为根本没有 nullptr。安全的释放方式如下void destroyCircular(Node* head) { if (head nullptr) return; Node* p head; Node* nextNode p-next; while (nextNode ! head) { delete p; p nextNode; nextNode p-next; } delete p; // 最后删除头节点 }还有一个原则要刻在脑子里先让前驱的 next 跳过要删除的节点再 delete。很多人先 delete 再改指针导致链表里留下一个悬空指针后续遍历就会访问到已释放的内存轻则输出乱码重则段错误。5. 常见错误速查与调试心得5.1 高频错误对照表整理了一份高频错误对照表考试遇到问题直接照着排查错误现象可能原因排查方案遍历死循环还停留在 p ! nullptr 的思维改成 p ! head 或 do-while输出少了第一个节点遍历起点或 head 设置错误检查遍历起点是否包含 head删除节点后链表断开只删了节点没更新前驱 next先 prev-next cur-next 再 delete程序崩溃野指针或空指针打印每个操作前后的指针地址出列顺序不对报数步数多走了一步确认走 m-1 次而不是 m 次反转后打印顺序不对还在用旧的 head使用函数返回的新头节点5.2 指针流向打印法循环链表调试最有效的工具就是打印。我调试时特别喜欢在关键操作前后加输出看指针流向。cout before delete: cur cur-data prev prev-data endl; // 执行删除操作 cout after delete: cur cur-data prev prev-data endl;如果问题出在环形结构本身可以写一个专门的打印函数验证void printCircular(Node* head) { if (head nullptr) { cout empty endl; return; } Node* p head; do { cout p-data ; p p-next; } while (p ! head); cout endl; }只要这个打印能正常跑完不进入死循环就说明环的结构是闭合的。如果它卡住了那大概率是某个节点的 next 没有指向正确位置。5.3 几个考场小技巧第一个技巧是画图。遇到循环链表题先在草稿纸上画几个节点标出 next 的指向然后手动模拟两次删除操作。只要图画对了代码基本不会出错。第二个技巧是先处理边界条件。空链表、单节点链表、删除头节点这三个情况是循环链表最容易翻车的地方。写主逻辑之前先把这些边界判断写好。第三个技巧是删除前先存 next。任何删除操作之前都应该先把下一个节点的指针存下来不要等删除完了再去找。6. 最后的备考建议6.1 三步训练法第一步把单链表的基本操作完全练熟。循环链表本质上就是单链表加一个“尾接回头”的动作单链表不稳循环链表必崩。第二步把不带头结点的循环链表和带头结点的循环链表各写一遍。两个版本都要能跑通重点感受它们在空表判断和删除首节点时的差异。第三步用约瑟夫环当练手题。分别实现输出完整出列顺序、只输出最后一个幸存者、把 m 和 n 调大观察性能变化这三个版本。6.2 做题顺序和时间分配考试时如果遇到循环链表的大题我建议按这个顺序来先读清楚题目要求的是带头结点还是不带头结点再画结构图然后写构建链表和遍历打印的代码最后才写核心的删除或模拟逻辑。这样即使后面写崩了至少前面的基础分能拿到。从我个人的经验来说循环链表题最大的敌人不是题目本身而是“自以为是”。你觉得自己已经理解了环的结构结果写代码时少接了一根指针程序就开始无限循环。所以在备考阶段一定要亲手把每一个节点的 next 指向从头到尾走一遍尤其是双指针移动的前后顺序。这个习惯能让你在考场上少踩至少一半的坑。循环链表这部分说到底就是三个关键点尾插建环、遍历终止、删除维护。把这三个点练透GESP 5级考试里只要是和循环链表相关的题目你都不会再慌。