企业官网建设流程全解析

如果有人问我，GESP 5级的数据结构考点里最容易被扣分的是哪一块，我的答案一定是循环链表。很多同学把单链表背得滚瓜烂熟，一看到“循环”两个字就开始发怵：遍历怎么写？终止条件是什么？删除节点怎么搞？其实循环链表和单链表在代码上只差一行指针，但这一行指针改完之后，整个思维模式都得跟着变。这篇内容就是围绕循环链表这个考点，把我自己备考和辅导过程中反复踩过的坑、总结出来的写法，一次讲透。

无论你是正在准备GESP 5级考试，还是刚学完单链表想进阶，这篇文章都适用。我会从最基础的结构体定义讲起，一直讲到约瑟夫环的完整实现，再把删除、反转、内存释放这些容易翻车的操作拆开揉碎了说清楚。

1. 循环链表到底是啥：从单链表到循环链表只改了一行指针

1.1 先把链表家族的关系捋清楚

GESP 5级考试里，链表家族常见的形态有四种：单链表、双向链表、单向循环链表、双向循环链表。很多同学概念背得挺熟，但一上机写代码就乱，根子在于没有把它们的结构差异理清楚。

普通单链表的结构是：每个节点有一个数据域和一个 next 指针，最后一个节点的 next 指向 nullptr。遍历的时候用一个 while(p != nullptr) 就能从头走到尾，走到空指针自然停。这是所有链表操作的地基。

循环链表最大的区别就是一句话：最后一个节点的 next 不再指向 nullptr，而是指向链表的第一个节点。也就是说，整个链表首尾相接，变成了一个环。这个改动带来的连锁反应很明显：遍历时没有了“终点”，如果还用 p != nullptr 判断，程序就会一直转圈，直到超时。

用生活里的场景来类比，单链表是一条单向火车线路，开到终点站就没路了，列车员可以下班；循环链表是环形跑道，没有终点这个概念，你跑完一圈之后又会回到起点，所以你必须自己记住“我已经跑了几圈”。

下面这个表格把几个关键差异列出来，复习的时候可以反复看：

1.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 指向它自己，形成自环。这种状态在删除操作时非常考验细节，一旦处理不当，头指针就丢了。

我的建议是：如果题目没有明确要求，优先用带头结点版本。考试时少一个边界条件，就少一分出错的可能。

3. 用循环链表实战约瑟夫环：GESP 5级最爱考的场景

3.1 约瑟夫环的题意和报数步数怎么定

约瑟夫环是循环链表最经典的练习题，也是 GESP 5级考试里出现频率很高的算法题。题目通常是这样的：n 个人编号从 1 到 n，围成一圈坐好。从编号 1 的人开始报数，数到 m 的人出列，然后下一个人重新从 1 开始报数，直到所有人出列。题目可能要求输出完整出列顺序，也可能只要求输出最后一个幸存者。

这题用循环链表模拟的思路非常自然：人围成一圈，正好对应循环链表的环。模拟过程是：

1. 构建编号为 1 到 n 的循环链表。
2. 从 head 开始，找到报数到 m 的那个人。
3. 删除这个人，链表继续保持环形。
4. 重复第 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 = 5，m = 100，循环链表会绕上很多圈才删除一个人。链表模拟的时间复杂度是 O(n*m)，如果 n 和 m 都很大，考试就可能超时。GESP 5级通常不会故意给这种极端数据，但你要知道这个瓶颈存在。如果题目只问最后一个幸存者，可以用递推公式直接算，不用链表模拟。

4. 删除、反转与内存维护：循环链表的进阶操作

4.1 删除节点的标准三步

删除循环链表中的某个节点，最重要的前提是找到它的前驱节点。因为循环链表里的 next 指针是单向的，你只知道当前节点，无法直接拿到它的前驱。

标准的删除过程是三步：

1. 找到要删除节点的前驱节点 prev。
2. 让 prev->next 指向要删除节点的下一个节点。
3. 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。如果你还是从原来的 head=1 开始打印，顺序会变成 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 高频错误对照表

整理了一份高频错误对照表，考试遇到问题直接照着排查：

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级考试里只要是和循环链表相关的题目，你都不会再慌。