企业官网建设流程全解析

GESP 5级C++的链表单元里，循环链表是绕不过去的一道坎。单链表还能靠画图硬啃，循环链表一出现，很多人都卡在“遍历怎么判断结束”这个点上——普通链表看next是不是NULL就行，循环链表转一圈又回到起点，条件怎么写都不对。更别提约瑟夫环，表面看是一道模拟题，实际考的就是对环形结构的理解深度。这篇文章就把循环链表相关的考点一次讲透：单向循环链表怎么建、怎么遍历、怎么插入删除，双向循环链表为什么建议带头节点，约瑟夫环又该怎么写、怎么验证。准备备考GESP 5级的同学，或者刚开始学链表的C++初学者，都能直接照着敲代码。

1. GESP 5级为什么绕不开循环链表

1.1 考点定位：链表单元里真正的分水岭

GESP 5级的大纲里，链表不是简单提一下就过，它属于“结构体与指针综合应用”级别的内容。考点通常分布在几个固定位置：节点结构体的定义、链表的遍历、插入和删除操作，以及循环链表的应用。其中单链表部分多数人还能应付，真正拉开分数差距的，是循环链表相关的题目——尤其是约瑟夫环这一类必须用“环形思维”才能自然解决的题。

我辅导学生备考时观察到，单链表学得不错的人，第一次接触循环链表照样会懵。原因很简单：单链表的所有操作都在一条“断头路”上做，循环链表却把尾巴接回了头，形成了一个没有天然终点的环。人脑习惯线性思考，遇到环就不知道什么时候该停，于是各种死循环、错删、断链的bug全冒出来了。所以循环链表这一节，是检验一个人是不是真正理解指针和节点关系的好题目。

1.2 循环链表与普通链表：差了一个“环”，多了三条规则

普通单链表长这样：每个节点有一个data和一个next指针，最后一个节点的next指向NULL。循环链表呢？最后一个节点的next不指向NULL，而是指向链表的第一个节点。就这么一个改动，带来了三条必须刻在脑子里的规则。

第一，任意节点出发都能遍历整个链表。普通链表如果想找尾节点，必须从头走到NULL；循环链表从任何一个节点出发，绕一圈能访问到所有节点。这个特性在做轮转类题目时特别好用。第二，遍历时必须自己定义“终点”。没有NULL可判断了，你得判断“下一个节点是不是起点”，或者“我是不是又回到了起点”。第三，空表判断和边界操作比普通链表更微妙。普通链表空表就是head==NULL，循环链表的空表也是head==NULL，但一旦表中只剩下一个节点，它的next指向自己，这时候插入和删除都得小心处理。

这三条规则理解透了，循环链表的基本操作就有了根基。后面再写代码，你就知道每一步在干什么，而不是照着别人的代码抄。

1.3 哪些题在等循环链表：约瑟夫环与轮转场景

教材里循环链表的典型题，第一个就是约瑟夫环。n个人围成一圈，从某个人开始报数，报到m的人出列，再从下一个人重新报数，问最后剩下谁。这类题用数组处理当然也能做，但数组删除一个元素要移动后面的元素，效率差而且代码绕；用普通单链表又需要频繁维护头尾，写起来别扭。只有循环链表天然贴合“一圈人围坐”这个场景，因为节点的next指针指向的就是“下一个人”，出列就是删除当前节点，从下一个人开始就是删除指针落到的那个后继。整个逻辑写出来非常顺。

除了约瑟夫环，循环链表还适合处理轮转调度的场景，比如多个任务轮流占用CPU、发牌游戏里循环发牌、队列的环形缓冲区。GESP级别的考题里，直接考这些场景的可能性不大，但理解了循环链表的原理，遇到这类题就能举一反三。反过来，如果只背代码不理解结构，题目只要一变条件，比如从第k个人开始报数、m大于n，立刻就不会写了。

2. 单向循环链表手写全解：从创建到增删查改

2.1 节点结构体怎么定才顺手

写循环链表之前，先把节点结构体定义好。GESP考试里一般要求用struct来定义节点，成员通常就是数据域和指针域。

struct Node { int data; Node* next; Node(int x) : data(x), next(nullptr) {} };

我习惯在结构体里写一个构造函数，这样每次创建节点都直接new Node(5)，不用手动赋值。有些学生写Node* p = new Node; p->data = 5; p->next = nullptr;，也行，但语句多，后面代码一长就容易漏掉初始化。构造函数一步到位，省心。

注意next的类型是Node*，不是int，很多刚学的同学会写成int* next，编译直接报错。指针类型必须和它指向的类型一致，这是链表代码第一道门槛。

2.2 尾插法构建循环链表：从空链表到成环

创建循环链表最常用的方式是尾插法，也就是每次把新节点追加到链表末尾。核心思路是：维护一个tail指针指向尾节点，每次插入时让tail原来的next指向新节点，再让新节点的next指向头节点，最后更新tail。

#include <iostream> using namespace std; struct Node { int data; Node* next; Node(int x) : data(x), next(nullptr) {} }; Node* createCycleList(int arr[], int n) { Node* head = nullptr; Node* tail = nullptr; for (int i = 0; i < n; ++i) { Node* newNode = new Node(arr[i]); if (head == nullptr) { head = tail = newNode; newNode->next = head; // 第一个节点的next指向自己 } else { tail->next = newNode; newNode->next = head; // 维持环结构 tail = newNode; } } return head; }

为什么第一个节点的next要指向自己？因为空表插入第一个节点时，头节点就是尾节点，如果只有一个节点，它自己必须和自己形成环。很多新手在这里把next写成nullptr，后面遍历就死循环或者直接断链了。这一行是循环链表和普通单链表最明显的区分点，值得用注释标出来。

第二个关键点：每次尾插都要重新设置newNode->next = head。尾插的过程本质上是：旧尾节点不再指向头节点，先指向新节点，然后让新节点接替它指向头节点。如果漏掉这一行，新节点就会指向nullptr，环就断了，链表变成普通单链表加一个多余节点。

2.3 遍历的终止条件：为什么 while(p != head) 会直接跳过

循环链表遍历是最容易出问题的地方。很多学生照搬单链表的写法，写成while (p != nullptr)，结果死循环。因为在循环链表里，永远走不到nullptr。

正确的写法有几种。最推荐的是do-while版本：

void printList(Node* head) { if (head == nullptr) { cout << "empty" << endl; return; } Node* p = head; do { cout << p->data << " "; p = p->next; } while (p != head); cout << endl; }

do-while先执行一次循环体再判断，对于“至少有一个节点”的循环链表来说非常合适。从head出发，打印head，走到下一个节点，判断是否回到了head；如果没回到，继续打印。整个过程完整又不会死循环。

那能不能用while写？可以，但要注意起点问题。如果写成Node* p = head; while (p != head) { ... }，判断在第一次执行前就触发了，等于一次都不打印，直接跳过。正确的while写法应该这样：

if (head == nullptr) return; Node* p = head->next; while (p != head) { cout << p->data << " "; p = p->next; } cout << head->data << endl; // 头节点最后打印

先处理完头节点，再从第二个节点开始while。这个写法理解起来稍微绕一点，但能帮你想清楚“环终点在哪”。我个人建议考试直接用do-while，少出错。做题的关键不是炫技，是稳定拿分。

2.4 插入与删除的边界陷阱

插入操作里，如果要在某个节点prev后面插入新节点x，核心代码其实和普通单链表类似：

Node* x = new Node(99); x->next = prev->next; prev->next = x;

但在循环链表里，多了个尾巴问题：如果prev是原尾节点，插入后x就变成了新的尾节点，x的next应该指向头节点。而上面那段代码里x->next = prev->next，此时prev->next指向的是head（因为原尾节点next指向head），所以x->next自动就是head，环没有被破坏。只是需要注意，如果有tail指针，得记得把tail更新到x。这一步很容易漏，漏了之后下次尾插就会从旧tail后面接，导致链表的末尾出现断点。

删除操作更麻烦，因为要处理的情况更多。假设要删除节点p的后继节点q：

if (head->next == head) { // 只剩一个节点 delete head; head = tail = nullptr; } else { Node* q = p->next; p->next = q->next; if (q == head) head = q->next; // 删的是头节点 if (q == tail) tail = p; // 删的是尾节点 delete q; }

这段代码有四个要点。第一，只剩一个节点时，直接删除并把head和tail都置空，否则后面访问空指针必崩。第二，如果删除的是头节点，新的头节点应该是q->next，也就是原链表的第二个节点。第三，如果删除的是尾节点，tail必须回退到p，因为tail始终要指向真正的尾节点。第四，如果删除的是中间的节点，head和tail都不用动。

很多学生只写中间两行，不处理删头删尾的情况，导致后续操作全乱。我的建议是：把这段代码背到形成条件反射的程度，然后每次练习都自己推一遍“如果删的是第一个/最后一个/唯一一个节点会怎样”。

2.5 保留尾指针，循环链表才算好用

普通单链表一般只保留head指针就够用了，因为找尾节点只要遍历到NULL。循环链表不一样——如果只保留head，想尾插就得遍历一整圈找到尾节点，太亏了。

循环链表的最佳实践是额外维护一个tail指针。有了tail，我们可以O(1)做到三件事：在尾部插入、获取头节点（tail->next）、判断空表（tail==nullptr）。尤其是获取头节点，循环链表里tail->next就是head，这在很多算法里是点睛之笔。

实际使用时，我习惯把head和tail作为一组信息来维护。函数参数里要传头尾的情况，就都传进去；用类封装的话，就都作为成员变量。不要只传一个head，然后在函数内部重新找tail，那样等于放弃了循环链表最大的优势。

3. 双向循环链表：考场加分项的优雅实现

3.1 双指针结构：每个节点都有“后视镜”

双向链表在单向链表的基础上，给每个节点加了一个prev指针，指向前一个节点。双向循环链表则让头节点的prev指向尾节点、尾节点的next指向头节点，形成双向环形结构。

struct DNode { int data; DNode* prev; DNode* next; DNode(int x) : data(x), prev(nullptr), next(nullptr) {} };

GESP 5级考试里双向链表出现频率比单向低，但一旦出现，往往是拉开差距的题目。因为双向链表能解决的问题，比如“从后往前遍历”“在任意位置快速插入删除”，用单向链表也能做，只是更麻烦。考双向循环链表，本质上是在考你对指针方向的敏感度：每个操作都要同时维护prev和next两个方向，漏改一个就断链。

3.2 哑头节点：让首尾操作不再写两份代码

双向链表写起来最烦人的是边界处理：在头部插入和在尾部插入逻辑不同，删除头节点和删除尾节点逻辑也不同。为了统一这些操作，一个常用技巧是加一个哑节点（dummy node），也叫头哨兵。它不存储实际数据，只作边界标记。

初始化时让哑节点的next和prev都指向自己：

DNode* dummy = new DNode(0); dummy->next = dummy; dummy->prev = dummy;

此时链表为空，判断条件是dummy->next == dummy。插入第一个真实节点后，dummy->next指向它，它的next又指回dummy，整个结构首尾相接。这个设计的精妙之处在于：首节点也有前驱（dummy），尾节点也有后继（dummy），所以对首尾的操作和对中间节点的操作完全一样，不需要写额外的if分支。

3.3 插入与删除的完整模板

在双向循环链表中，在某个节点p之前插入新节点x，可以写成：

void insertBefore(DNode* p, int val) { DNode* x = new DNode(val); x->next = p; x->prev = p->prev; p->prev->next = x; p->prev = x; }

四行代码，四个方向全部维护到了。x的next指向p，x的prev指向p原来的前驱；然后让p原来的前驱的next指向x，再让p的prev指向x。顺序不能乱，否则会丢失p的原前驱地址。我让学生记一个口诀：“先接新节点，再拆旧连接”。先设置x的两个指针，再修改周围节点的指针，这样不会把原有链改坏。

删除节点p的代码更简洁：

void removeNode(DNode* p) { p->prev->next = p->next; p->next->prev = p->prev; delete p; }

这两行分别把p前驱的next接到p的后继，把p后继的prev接到p的前驱。完成之后p就从链表中脱离，再delete释放就行。因为存在dummy，p即使首节点或尾节点，它的前驱或后继也一定是有效节点，所以不需要任何特殊判断。

3.4 双向链表调试：先画箭头，再改代码

我见过太多学生写双向链表时debug到崩溃，最后发现只是某个.和->写错了地方，或者漏了一行p->next->prev = p->prev。这类问题靠看代码很难发现，最好的办法是画箭头图。

具体做法：纸上画几个方框代表节点，方框左右各伸出一个箭头，分别标prev和next。插入或删除时，用铅笔把要断开的箭头划掉，再画上新的箭头。每画一步，对照代码检查一行。这个方法看起来原始，但对双向链表极其有效，因为双向链表的指针方向比单向多一倍，脑内模拟很容易出错。

画图几次之后，你会形成一个直觉：双向链表的每个操作必须成对修改，一边是“前驱的next”，一边是“后继的prev”。养成这个直觉，考试遇到双向循环链表就稳了。

4. 约瑟夫环实战：循环链表最经典的出场方式

4.1 题目基线与解题思路

约瑟夫环的经典描述是：n个人编号1到n，围成一圈坐好，从编号1的人开始报数，报到m的人出列，然后下一个人重新从1报数，重复这个过程，直到只剩一个人，问最后留下的人的编号。

解题思路就是模拟整个过程。把n个人放进循环链表里，当前指针cur指向报数的人。每次要找到“报到m的人”，就让cur移动m-1步——因为cur自己已经算报了第1个数，移动m-1次正好落在报第m个数的人身上。找到后删除该节点，再让cur移动到被删节点的next，也就是下一位报数者。

为什么这个题用循环链表这么自然？因为“围成一圈”直接对应环结构，“从下一个人开始报数”对应删除后指针落在后继上，“人出列”对应删除节点。整个代码流程就是题目的逐步翻译。

4.2 完整代码实现

下面是一份可以直接跑通的完整代码，包含建表、模拟、释放。

#include <iostream> using namespace std; struct Node { int data; Node* next; Node(int x) : data(x), next(nullptr) {} }; int josephus(int n, int m) { // 创建编号 1~n 的循环链表 Node* head = new Node(1); Node* tail = head; for (int i = 2; i <= n; ++i) { Node* x = new Node(i); tail->next = x; tail = x; } tail->next = head; // 成环 Node* cur = head; int left = n; while (left > 1) { // cur 是当前报数的人，找到要出列的人的前驱 Node* prev = cur; for (int i = 1; i < m; ++i) { prev = cur; cur = cur->next; } // 此时 cur 是报到 m 的人，prev 是它的前驱 prev->next = cur->next; if (cur == head) head = cur->next; // 如果删的是头节点，更新头 delete cur; cur = prev->next; // 从下一个节点重新报数 --left; } int ans = head->data; delete head; return ans; } int main() { cout << josephus(5, 2) << endl; // 输出 3 return 0; }

里面有一个细节值得单独讲：为什么要维护prev？因为单链表删除一个节点必须知道它的前驱。在环里，cur从头到尾移动，prev始终跟在cur后面一步。循环结束后，prev就是cur的前驱。这样删除cur的代码就变成标准的“p指向要删除节点的前驱，然后删除p->next”模式，好理解也好写。

4.3 手动模拟验证，确保没有边界遗漏

写完代码别急着交，手工跑一遍小数据是最快的验算方式。拿n=5、m=2来推：

初始环：1 -> 2 -> 3 -> 4 -> 5 -> 1。

cur指向1。报数开始，1报到1，2报到2，所以2出列。prev是1，删除2，cur变为3。剩余：1 3 4 5。

第二轮从3开始，3报到1，4报到2，4出列，cur变为5。剩余：1 3 5。

第三轮从5开始，5报到1，1报到2，1出列，cur变为3。剩余：3 5。

第四轮从3开始，3报到1，5报到2，5出列，cur变为3。剩下3。所以答案确实是3。

这段模拟过程虽然简单，但能验证代码里几个关键行为：删除后cur是否成功跳到next、头节点被删时head更新是否正确、最后剩余的节点是否真的还留在环里。建议你以后做这类题，都挑一组小数据手推一遍再跑程序，能省大量调试时间。

4.4 循环链表模拟和递推公式怎么选

约瑟夫环还有一个著名的数学递推解法：f[1]=0，f[i]=(f[i-1]+m)%i，最终答案是f[n]+1（从1编号）。这个解法O(n)跑完，看起来更快。那考试到底写链表模拟还是套公式？

我的建议是：如果题目没有强制要求用链表，并且你对递推公式非常熟悉，可以用公式法省时间。但GESP 5级考察的重点是数据结构，很多题目明确要求“设计一个循环链表来模拟”，或者有大题分值放在链表操作上，这时候写链表模拟才是正确答题方向。即使题目不强制，链表模拟的优点是思路直观、不容易记错公式；缺点是当n和m都很大时，O(n*m)可能超时。

如果n=1000、m=10000，nm=1e7，C++跑起来没问题。但如果n=10000、m=1000000，nm=1e10，显然超时。真遇到这种极端数据，说明题目原本希望你用数学方法，链表模拟可能会超时。备考阶段我的态度是：链表模拟必须练到熟练，递推公式也要会推导，考场上根据题目约束和分值灵活选。

4.5 m大于n以及从第k个人开始报数怎么办

约瑟夫环的变体经常出现两个条件：报数m可以大于人数n；不是从编号1开始，而是从第k个人开始。

m大于n时，链表模拟天然没问题。因为cur一直沿着环走，走m-1步相当于多绕了几圈，落到的人依然正确。你不需要对m做任何取模处理，for循环就是一圈一圈转，代码逻辑不变。

从第k个人开始时，只需要在模拟前让cur先移动k-1步：

Node* cur = head; for (int i = 1; i < k; ++i) { cur = cur->next; }

之后报数从cur开始，代码其他部分完全不变。这正是循环链表“任意节点都能作为起点”特性的体现。如果你之前理解的是“循环链表就是首尾相连的单链表”，遇到这种变体就能明白为什么它能直接支持。

5. 高频报错与考场避坑记录

5.1 常见错误速查表

我整理了循环链表练习和考试里最常出现的几类错误，直接对照就能认清自己的问题。

这张表里的错误，我在不同学生身上反复见到。每一种错误背后，其实都是“对环结构特点理解不够”或者“边界条件没想全”。考前把这张表过一遍，比盲目多刷十道题管用。

5.2 调试循环链表的三板斧

第一板斧：写完就打印。建好链表后，先调用一个遍历函数把整条链打印出来。插入或删除每个节点后，也打印一次。循环链表的问题很有特点——断链通常发生在某个节点上，打印结果会让你立刻看到断点在哪。如果你发现打印链表时死循环，十有八九是终止条件没写好。

第二板斧：设置循环保护。调试时在while循环里加一个计数器，比如int cnt = 0; while (cnt++ < 10000 && 条件) { ... }，这样即使逻辑错了，程序也会在有限步数内退出，不至于卡死整个IDE。定位问题后，再把计数器删掉还原代码。

第三板斧：小数据手推对照。拿n=5、m=2这种规模，在纸上手动模拟出结果，然后让程序输出每一步删除的节点编号。两步对照，马上知道是哪一轮开始跑偏。这个方法尤其适合约瑟夫环，因为它的过程本身就是一个序列，对比输出序列非常直观。

5.3 考场上的时间分配与测试用例建议

GESP 5级是上机考试，时间很紧。遇到循环链表大题，我建议按三个阶段分配：先花5分钟确定用哪种链表结构、画一下节点关系草图；再花15到20分钟写建表和核心操作代码；最后留5到10分钟构造测试用例验证。不要一上来就埋头写代码，结构都没想清楚，后面改起来时间翻倍。

测试用例至少要覆盖四类：n=1的情况，这个最容易崩；n=5、m=2的常规中等数据，用来验证核心逻辑；m=1的情况，验证只删当前报到者时指针移动是否正确；m大于n的情况，比如n=5、m=7，验证多圈报数是否正确。这四类跑过，边界就稳了。

考场临场还有一个实用习惯：命名尽量用head、tail、cur、prev这类一眼能看懂的名字。判卷时代码可读性占分，更重要的是你自己调试时也不容易搞混。别写a、b、c这种无意义命名，链表题里指针一多，名字没有含义，写着写着就不知道自己指的是什么了。

5.4 一点个人经验：循环链表怎么练才真正掌握

我带过的学生里，进步最快的人有个共同点：不靠看，靠写。他们每天会手写一遍单向循环链表的创建、遍历、插入、删除，再写一遍约瑟夫环的完整代码。连续一周，这些操作就变成肌肉记忆了。考试时候不用现场想“next怎么指”，下笔就能写对。

另一个个人体会是：遇到调试不出来的时候，一定要先画图再改代码。很多学生卡在循环链表，不是智商问题，是脑子里没有那张“环”的图。你一旦在纸上把节点箭头画出来，指针的指向清清楚楚，bug基本一眼就看穿了。画图看起来慢，实际是节省时间最快的办法。

最后说一句：链表这道坎，迈过去之后你会发现数据结构很多复杂题都变简单了。循环链表是一个绝佳的思维训练场——它强迫你从“线性思考”切换到“环形思考”。GESP 5级考它，考的不只是语法，更是你有没有建立起这种抽象能力。把这篇内容消化掉，自己动手写完几个版本的代码，考试时遇到循环链表，你就不会慌了。