企业官网建设流程全解析

考试前看链表，很多人卡在“单链表明明已经够绕了，循环链表会不会更吓人”。其实正好相反，循环链表只是把链表的尾巴从nullptr改成指向头节点，本质上就是“环形跑道”，只不过跑道里没有终点线。GESP 5级C++考试对循环链表的考查点非常清晰：能看懂结构、会写基本操作、能解决约瑟夫环这类经典问题。这篇就把循环链表从结构原理到考场代码整个拆开讲一遍，重点是那些写代码时容易翻车的小细节。

1. 循环链表到底改了什么：从“断头路”变成“环形跑道”

1.1 普通单链表和循环链表的核心差异

先回忆一下普通单链表。每个节点里有数据域和指针域，最后一个节点的指针指向nullptr，相当于路走到底就没了，你想回头找头节点，必须从头重新遍历。循环链表的改动就一处：把最后一个节点的next从nullptr改成指向第一个节点。看似简单，但整个遍历逻辑、终止条件、操作边界全变了。

定义节点结构时，普通单链表和循环链表写出来的代码几乎一样，区别全在“尾指针怎么处理”：

struct Node { int data; Node* next; }; // 普通单链表：最后一个节点的 next 是 nullptr // 循环链表：最后一个节点的 next 指向第一个节点

考试时最容易丢分的地方就在这里：很多同学建好了循环链表，但遍历时还沿用单链表的写法，用p != nullptr作为循环条件，结果指针永远不为空，直接死循环。这是循环链表第一个要养成的肌肉记忆——判断链表结束，看的不是指针是否为nullptr，而是是否回到了头节点。

1.2 带头节点和不带头节点的循环链表应该选哪个

循环链表有两种常见形式：一种不带头节点，头指针直接指向第一个实际数据节点；另一种带头节点（也叫哨兵节点），头指针指向一个不放数据的空节点，这个空节点的next才指向真正的第一个数据节点。

考试写题时，我强烈建议你统一带头节点。原因有三个：

• 空链表时，头节点的next指向自己，判断条件统一成p == head，跟非空链表一致，不用额外处理“链表为空”这个分支。
• 删除第一个数据节点时，不需要修改外部头指针。如果不带头节点，删除头节点就必须把新的头指针传出去，要么用引用参数Node*& head，要么返回新头指针，多一层麻烦。
• 插入操作也简单，不需要区分“插在第一个位置”和“插在其他位置”，因为第一个位置的前驱就是头节点。

带头节点构造一个空循环链表的语句是这样的：

Node* head = new Node(); head->next = head; // 空循环链表，头节点指向自己

很多教材管这个叫“循环链表判空的标志”。写题时建议先写好这个初始化，再写插入函数。

1.3 用“火车轨道”理解头尾相接的节点关系

为了把这种结构讲得更直观，可以想象一列环形轨道上的火车。每一节车厢就是一个节点，车厢之间的挂钩就是next指针。普通链表像一条死路尽头的铁路，开到最后一节就不能再前进；循环链表则把最后一节车厢又挂回到第一节，火车可以无限绕圈。

那么“回到起点”这件事，在代码里怎么判定呢？加一个变量count，数到节点个数就停；或者保存起始节点start，一旦p->next == start就知道绕完一整圈。这两种方式在考试里都常见，但时间复杂度不一样：遍历整个循环链表本身是 O(n)，如果每次都调用while (p != head)，你在起点那个节点上要细心判断“是刚到起点，还是绕了一圈又回来”。

这也是循环链表最隐蔽的坑：“到没到起点”和“是否已经绕了一圈”是两个概念。仅仅判断p == head，在第一圈刚出发时也是成立的，必须在进入循环体前记录起始位置，否则写出来的遍历会提前退出或者死循环。

2. 循环链表的遍历：终止条件才是考点的灵魂

2.1 遍历时，“回到起点”怎么写才正确

先看一个标准遍历代码。在带头节点的循环链表中，从第一个数据节点开始，一个一个访问，直到回到头节点：

// 带头节点，遍历所有数据节点 void traverse(Node* head) { Node* p = head->next; // 第一个数据节点 while (p != head) { cout << p->data << " "; p = p->next; } cout << endl; }

这段代码最核心的是while (p != head)。因为每次访问完一个节点后p = p->next，当p再次等于head时，说明已经回到哨兵节点，也就是绕完了整圈。这种做法比“数次数”更简洁，也是循环链表遍历的标准写法。

但要注意一个细节：如果链表只有头节点没有数据节点，p = head->next后p == head，循环一次都不执行，这正好是空链表的遍历结果，零个数据，输出空行。这个行为在带头节点的结构下非常自然，不用额外判断链表是否为空。

2.2 do-while 写法在循环链表里的特殊地位

不带头节点的循环链表遍历，很多人容易写成这样：

// 错误示范：当链表只有一个节点时，while 条件在一开始就不成立 Node* p = head; while (p != head) { // p 等于 head，循环体根本不会执行 cout << p->data << " "; p = p->next; }

问题很明显：不带头节点时，head本身就是数据节点，一进来p == head，按while的判断直接退出，结果一个节点都没输出。对于这种情况，就应该改用do-while：

// 不带头节点，至少有一个节点 Node* p = head; do { cout << p->data << " "; p = p->next; } while (p != head);

do-while保证“先访问一次，再判断是否回到起点”，巧妙绕开了初始条件尴尬。考试如果考不带头节点的循环链表遍历，十有八九就是想看你有没有区分while和do-while的适用场景。

我记得有个朋友第一次写这段代码，直接拿while去跑单节点循环链表，输出为空，调试了半天才发现是初始判断就把自己挡在门外了。这种坑不实际踩一次，光看书基本看不出来。

2.3 遍历中的死循环警报：指针漏更和条件漏写

循环链表遍历最常见的两个死循环原因：

• 循环体里忘记写p = p->next;，指针永远停在同一个节点上。
• 判断条件写成了while (p != nullptr)，永远成立，因为循环链表中没有一个指针是nullptr。

第二种情况在考场非常容易手滑，尤其是平常写单链表写多了，nullptr判断成了肌肉记忆。一旦发现程序卡住不结束，第一反应先查遍历条件是不是还在用nullptr。

另外，如果遍历时要在中途做删除操作，删除完当前节点后不要急着p = p->next，因为当前节点已经被delete，它的next已经是野指针了。正确做法是先把p->next存下来，或者利用“删除后移”的经典手法。这一点放到后面插入删除部分细讲。

3. 循环链表的插入与删除：从头到尾的完整C++实现

3.1 尾插法：为什么维护一个 tail 指针更划算

普通链表尾插法如果不记录尾指针，每次都要从头遍历到尾，时间复杂度 O(n)。循环链表也一样，如果不记录尾指针，在尾部插入同样需要从头走一圈。但如果维护一个tail指针，尾部插入就能做到 O(1)。

带头节点加尾指针的循环链表，尾部插入的完整代码如下：

struct Node { int data; Node* next; }; // 创建空循环链表：头节点 next 指向自己，tail 指向头节点 Node* head = new Node(); head->next = head; Node* tail = head; // 尾插法：把新节点插到 tail 后面 void insertTail(Node* tail, int value) { Node* newNode = new Node(); newNode->data = value; newNode->next = tail->next; // 新节点指向头节点 tail->next = newNode; // 原尾节点指向新节点 tail = newNode; // 更新尾指针 }

注意这里tail->next的含义。空链表时，tail == head，此时tail->next == head，所以新节点的next指向头节点，它既是第一个数据节点也是最后一个，链条依然闭合。插入第二个节点时，tail已经是第一个数据节点，tail->next还是头节点，新节点插在尾节点和头节点之间，也符合循环结构。

有的同学会问：为什么不直接改head而用一个tail变量？那是因为insertTail函数内部要修改tail的值，传参得用引用Node*& tail，否则函数里的tail改变不会传回调用者。如果只用一个头指针，插入后还得重新遍历找新的尾节点，那尾部插入又变回 O(n)，好处全没了。

3.2 删除指定节点：先找前驱，再处理边界

删除循环链表中的某个节点，核心操作和普通单链表完全一样：找到要删节点的前驱，让前驱的next指向要删节点的后继，然后释放节点。唯一要小心的是删除头节点后的第一个数据节点时，外部头指针是否需要更新。

带头节点版本删除第一个数据节点的代码：

void deleteFirst(Node* head) { if (head->next == head) { cout << "链表为空，无法删除" << endl; return; } Node* first = head->next; head->next = first->next; // 头节点跳过第一个节点，指向第二个 delete first; // 释放原第一个节点 }

这里不会出现“删除后头指针失效”的问题，因为数据操作节点是挂在head之后的，head本身始终是一个稳定的哨兵。如果你不带头节点，删除第一个节点就得写成：

// 不带头节点，删除头节点 Node* deleteHead(Node* head) { if (head->next == head) { delete head; return nullptr; // 链表删空 } Node* old = head; // 先找到最后一个节点，因为它的 next 要指向新的头节点 Node* p = head; while (p->next != head) { p = p->next; } p->next = old->next; // 最后一个节点指向原第二个节点 head = old->next; // 更新头指针 delete old; return head; }

你看，只删一个头节点，不带头节点的版本就要先把尾部节点找到，更新它的next，再换头指针，复杂度瞬间上去了。这也是为什么我反复强调考场带头节点的写法更稳。

3.3 断链和野指针：写插入删除最容易犯的三种错

我总结了循环链表写插入删除时最容易踩的三个坑：

错误一：插入时先修改了原节点的next，导致后半段丢失。比如尾插时先写tail->next = newNode;再写newNode->next = tail->next;，此时tail->next已经变成newNode，新节点next指向了自己，链表瞬间变成一个“带自环的残链”。正确顺序一定是先让新节点接管原链接，再修改原节点的指针。

错误二：删除后没有把删除节点的next置空。虽然循环链表里的节点最终会被delete，但如果不把p->next = nullptr，而p恰好是尾节点，后面的遍历可能通过它的野指针意外访问到已释放内存。严格来说，delete后置空是防御性编程的好习惯。

错误三：链表中只有一个节点时，删除操作后 head/tail 没有回到“空链表状态”。带头节点版本中，删除唯一数据节点后，head->next要重新指向head；如果不重指向，后续判空会失败。

4. 约瑟夫环问题：循环链表在考试里最常出现的应用

4.1 题目原型与解题思路

约瑟夫环的经典描述是：n 个人围成一圈，从第 1 个人开始报数，报到 k 的人出列，然后从下一个人重新报数，直到所有人都出列，求输出顺序或最后剩下的人。

这道题和循环链表简直是天生一对：人围成一圈就是循环链表，出列就是删除节点，从下一个人继续报数就是删除后指针后移一步。解题步骤可以固定成四步：

1. 建一个带头节点或不带头节点的循环链表，节点编号从 1 到 n。
2. 用一个指针p指向“当前报数的人”。
3. 从 1 报数到 k-1，每次把p向后移一步，p此时指向要出列的人的前一个节点，方便删除。
4. 记录出列者编号，删除该节点，p指向被删节点的下一个节点，重新报数。

第三步为什么要走 k-1 而不是 k？因为循环链表删除某个节点需要知道它的前驱，而约瑟夫环问题的报数从当前节点开始算第 1 个，报到 k 时，从当前位置到目标节点刚好要移动 k-1 步。这个细节非常容易算错，建议动笔前先在草稿纸上模拟一个 n=5、k=2 的小例子。

4.2 带头节点的约瑟夫环完整 C++ 代码

下面给出一版可以直接抄的带头节点实现。代码里我用一个findPrev的辅助思路，让删除逻辑更清晰。

#include <iostream> using namespace std; struct Node { int id; Node* next; }; // 删除 p 的下一个节点，返回被删除节点的编号 int removeNext(Node* p) { Node* victim = p->next; int ret = victim->id; p->next = victim->next; delete victim; return ret; } int main() { int n, k; cin >> n >> k; // 带头节点的循环链表 Node* head = new Node(); head->next = head; Node* tail = head; // 建链：编号 1 到 n for (int i = 1; i <= n; ++i) { Node* newNode = new Node(); newNode->id = i; newNode->next = tail->next; // 新节点指向头节点 tail->next = newNode; tail = newNode; } cout << "出列顺序: "; Node* p = head; // n 个人全部出列 for (int i = 0; i < n; ++i) { // 从当前节点的下一个开始报数，报到 k 则删除下一个 for (int cnt = 1; cnt < k; ++cnt) { p = p->next; if (p->next == head) { // 跳过哨兵节点 p = p->next; } } cout << removeNext(p) << " "; // 此时 p 已经指向出列节点的前驱，且 p->next 是被删节点的后继 // 如果 p 的下一个节点就是头节点，需要把 p 移到数据节点上 if (p->next == head) { p = head; } } cout << endl; return 0; }

这里处理哨兵节点的方式可能跟你在其他教材上见到的不太一样。很多教材直接用“不带头节点”的循环链表写约瑟夫环，虽然代码短，但对删除头节点这类边界要写额外分支。用带头节点的写法，哨兵节点不参与报数，每次遇到p->next == head就多跳一次，逻辑上更统一。

谈谈运行过程。以 n=5、k=2 为例：初始p指向头节点，内层循环cnt=1时p=p->next指向节点 1，此时p->next是节点 2，不是头节点，所以删除节点 2。接着p->next指向节点 3，继续报数，cnt=1后p指向节点 3，删除节点 4。依次删掉 2、4、1、5，最后剩下节点 3。如果没想明白，完全可以自己手推一遍，胜过背十遍代码。

4.3 约瑟夫环的数学解法和链表解法，考场怎么选

循环链表的实现属于“模拟解法”，复杂度 O(nk)，因为每个出列的人要移动 k 步。当题目中的 n、k 都很大，比如 n=10^5、k=10^5，O(nk) 会超时。这类题在 GESP 5级考试里一般不要求优化到 O(n)，但你要知道还存在一个递归/递推公式解：

f(1) = 0 f(i) = (f(i-1) + k) % i

最终最后剩下的人的编号是f(n) + 1。这个公式是约瑟夫环的经典结论，不依赖任何链表结构。

那么考场到底选哪种？如果你是 5 级水平，优先写链表模拟：思路直观，代码不容易错，数据范围小时稳过。只有当数据范围特别大，明确看到“n 达到十万级别”这种字眼时，才考虑递推公式。说到底，考试考的是链表应用，不是考你记不记得数学公式，模拟能跑对才是硬道理。

5. 快慢指针判断循环链表：从“会不会死循环”到“找入口”

5.1 慢指针和快指针为什么一定能相遇

循环链表里有一个高频考点：给定一个链表，判断它是否存在环。做法是快慢指针：一个慢指针slow每次走一步，一个快指针fast每次走两步。如果链表无环，fast会先遇到nullptr；如果有环，fast迟早能和slow相遇。

为什么一定能相遇？可以这么理解：假设slow进入环时，fast已经在环里某个位置。此后slow每走 1 步，fast走 2 步，两者的距离就缩短 1 步。环的长度有限，距离迟早减到 0，也就是相遇，这个过程和“两辆车在环形跑道上一快一慢追赶”完全一样。

代码实现很精炼：

bool hasCycle(Node* head) { Node* slow = head; Node* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) { return true; } } return false; }

注意这里的head指的是整条链表的起点，不要求一定是循环链表，任何单链表都可能带环。这个考点本身和“循环链表”是双向呼应的：考试既可能给你一个标准循环链表，让你直接遍历输出；也可能给你一个不知道有没有环的链表，让你判断有没有环。两个方向都要练。

5.2 判断“有没有环”之后，还常考“环入口在哪”

进阶一点的题目会问：如果链表有环，找出环的入口节点。这需要再补一个数学关系。

第一次相遇时，设链表起点到环入口的距离为 a，入口到相遇点距离为 b，相遇点再走到入口距离为 c，环周长 L = b + c。慢指针走了a + b，快指针走了a + b + kL，因为快指针速度是慢指针两倍，所以：

2(a + b) = a + b + kL => a + b = kL => a = kL - b = (k-1)L + (L - b) = (k-1)L + c

这个式子的含义是：从起点走 a 步，等价于绕环若干圈后再从相遇点走 c 步，正好在入口相遇。所以代码解法是：第一次相遇后，让一个指针回到起点，另一个停在相遇点，两个指针都一次走一步，再次相遇的位置就是环的入口。

Node* detectCycle(Node* head) { Node* slow = head; Node* fast = head; while (fast != nullptr && fast->next != nullptr) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } if (fast == nullptr || fast->next == nullptr) return nullptr; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; }

考场遇到这个进阶题，先别慌，把上面这个公式记在草稿纸边上，一步步推导一遍，代码就顺理成章写出来了。数学表达式看起来唬人，其实核心就一句：相遇点那里，一个指针从头走，一个指针从相遇点走，速度相同，就会在环入口碰上。

5.3 循环链表与“带环链表”的概念边界

很多初学者会把“循环链表”和“带环链表”当成一回事。严格说，标准循环链表是尾节点指向头节点的整链环，而带环链表可能是中间某个节点形成了一个局部环，环外还挂着一段节点，比如 1->2->3->4->2 这种。

考试里这两种概念会交替出现：

• 标准循环链表：尾连头，遍历时用while (p != head)，重点考遍历和插入删除。
• 带环链表：环不一定从头开始，重点考快慢指针判断与入口计算。

如果题目让你判断“一个节点个数为 n 的链表是不是标准循环链表”，不能直接套hasCycle，因为带环但环入口不在头节点的链表也会判成 true。标准循环链表的判断要麻烦一点，需要先遍历一圈确认每个节点都访问到了，再检查最后一个节点的next是否等于第一个节点。做题时先看清题目到底问的是哪种环。

6. 双向循环链表：5级考试里的进阶结构与代码优化

6.1 双向循环链表的结构：每个节点多条一条链

双向循环链表在循环链表的基础上增加一个前驱指针prev，让每个节点既能向后走也能向前走，并且最后一个节点的next指向头节点，头节点的prev指向最后一个节点。

结构体的定义是：

struct DNode { int data; DNode* prev; DNode* next; };

双向循环链表的空链表初始化：

DNode* head = new DNode(); head->prev = head; head->next = head;

别看只是多了一个prev，插入删除的代码逻辑比单向链表复杂不少，因为你要同时维护两条链。考试如果考双向链表，重点一般就两个：插入后要同时更新四个指针，删除后要同时更新两个指针。

6.2 双向循环链表的插入删除：四个指针的更新顺序

以在节点p后面插入新节点newNode为例：

void insertAfter(DNode* p, int value) { DNode* newNode = new DNode(); newNode->data = value; newNode->next = p->next; newNode->prev = p; p->next->prev = newNode; p->next = newNode; }

这里四行代码的顺序是有讲究的：先设置新节点的next和prev，再修改原后继节点的prev，最后才修改p->next。把最后两步换过来会怎么样？如果先写p->next = newNode，那么第三步p->next->prev = newNode时，p->next已经指向新节点，再设置新节点的prev等于自己，整个链表结构就断了。

删除节点p（假如p不是头节点或尾节点）则更短：

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

这段代码的思路就是“把前后两个节点直接接起来”。如果删除尾节点，要额外判断并更新相关头尾标记；如果删除唯一数据节点，则要回到head->prev = head; head->next = head;。考场上写双向链表的删除，建议先在草稿纸上画出四个指针的连线图，再动笔，直接硬写很容易漏链。

6.3 考场实战：循环链表题型的审题清单

这段时间我帮身边备考 GESP 5级的朋友梳理了一份“循环链表审题清单”，写在这里，希望能帮你少踩几个坑：

1. 题目要求带头节点，还是不带头节点？正文里出现“第一个数据节点”“空头指针”等字眼要敏感，先确定结构。
2. 尾插还是头插？如果同时给了tail指针，八成希望用 O(1) 尾插；如果只给head，尾插就得遍历。
3. 遍历终止条件是p != head，还是数次数？p != head最适合标准循环链表；数次数适合不知道会不会出现环的题目。
4. 删除节点前，有没有备份下一个节点？这决定删除后还能不能继续遍历。
5. 快慢指针判断环时，fast每次走两步，有没有先判fast->next是否为nullptr？漏掉这个，fast = fast->next->next一行就会访问空指针，直接程序崩溃。

这套清单其实来自一次真实的模拟题。有个朋友做“删除循环链表最大值节点”的题目，卡了很久，最后发现他遍历时用while (p != nullptr)，导致刚进循环就死循环。那次之后我们把这几个检查点固定下来，后面写循环链表题的正确率明显上去。

最后忍不住说一点：循环链表不是靠“看懂”就能过关的知识点，一定要亲手建一个链表，输出一遍，删除几个节点，再回头写约瑟夫环。GESP 5级考试考的其实不是记忆力，而是你在有限时间内能不能稳定写出不出错的代码。如果你现在能把带哨兵节点的循环链表增删改查写得又快又对，再花半天把约瑟夫环和快慢指针练熟，循环链表这块就算彻底拿下了。