竞极 Ace

3 循环链表

GESP C++ 五级：循环链表精讲

核心目标：理解循环链表的逻辑结构与内存模型，掌握循环单链表、循环双链表的创建、遍历、插入、删除操作，重点掌握判空条件与遍历终止条件，能解决约瑟夫环等经典问题，能辨析循环链表与单链表、双链表的区别。
循环链表没有NULL，尾节点的next指回头节点；遍历用do-while，否则死循环；判空看“指向自己”而不是“指向NULL”；插入删除改指针，tail位置要分清。

一、考纲定位

GESP 五级官方考纲第3条明确要求：“掌握链表的创建、插入、删除、遍历和反转操作，理解单链表、双链表、循环链表的区别”。循环链表是五级链表模块的重要组成部分，考试中常以选择题、代码填空题的形式出现。

循环链表在五级考试中的考查分布：

考点 重要程度 典型考法
循环链表与单链表/双链表的区别 ★★★★★ 选择题高频
判空条件 选择题、代码填空
遍历终止条件（do-while） 代码填空、程序阅读
在头节点后插入 ★★★★☆ 代码填空
在尾部插入
循环双链表在p前插入 ★★★★★ 选择题高频
约瑟夫环问题 编程题、代码填空
循环链表反转 ★★★☆☆ 编程题
Floyd快慢指针判环 ★★★★☆ 选择题

五级还要求掌握双向循环链表和带头节点的循环链表，这些是循环链表模块的进阶内容。

二、循环链表基本概念

1. 什么是循环链表

循环链表就是在单链表的基础上，将链表中最后一个节点的next指针指回头节点，让链表的首尾相连，从而更自然地处理“循环访问”或“环形结构”的问题。使用循环链表可以从任意一个节点出发，一直沿着next走，都能绕一圈访问到所有节点。

2. 循环链表 vs 普通链表

对比项 单链表 双链表 循环链表
尾节点指针 nullptr 指向头节点
遍历方向 只能从头到尾 双向遍历 环形遍历
遍历终止 p != nullptr p != head
判空条件 head == nullptr head == head->next
插入删除复杂度 O(n)/O(1) O(1) O(n)/O(1)

高频易错辨析：循环链表与普通链表最大的区别就是最后一个节点的后继指向了头节点，而不是NULL。循环链表中每个节点的指针域通常不为空，但当链表为空时，头指针可能为null，因此循环链表中也可能存在空指针。

3. 节点定义

循环单链表的节点定义与单链表相同：

struct Node {
    int data;       // 数据域
    Node* next;     // 指针域
    Node(int d) : data(d), next(nullptr) {}
};

循环双链表的节点定义与双链表相同：

struct DNode {
    int data;       // 数据域
    DNode* prev;    // 指向前驱
    DNode* next;    // 指向后继
};

三、判空条件（高频考点）

1. 循环单链表判空

带头节点的循环单链表：

// 判空条件：头节点的next指向自己
bool isEmpty(Node* head) {
    return head->next == head;
}

不带头节点的循环单链表：

// 判空条件：头指针为nullptr
bool isEmpty(Node* head) {
    return head == nullptr;
}

带头节点和尾指针rear的循环单链表：

// 判空条件：尾指针指向头节点
bool isEmpty(Node* head, Node* rear) {
    return rear == head;
}

防错提醒：遇到“循环链表”的题目，一定要注意“循环链表无NULL”这个特点。判空条件一定是“指向自己”，而不是“指向NULL”。

2. 循环双链表判空

// 带头节点的循环双链表判空
bool isEmpty(DNode* head) {
    return head->next == head;
}

3. 真题示例

真题（2026年3月） ：

关于单链表、双链表和循环链表，下列说法正确的是（ ）。
A. 在单链表中，若已知任意结点的指针，则可以在O(1)时间内删除该结点
B. 循环链表中一定不存在空指针
C. 在循环双链表中，尾结点的next指针一定为nullptr
D. 在带头结点的循环单链表中，判定链表是否为空只需判断头结点的next是否指向自身
答案：D

解析：A错误，单链表删除已知节点需要找前驱，O(n)；B错误，不带头结点的循环单链表为空时头指针即为空指针；C错误，循环双链表的尾节点next指向头结点，不是nullptr；D正确。

四、循环链表的遍历（重点）

1. 为什么不能用 while (p != nullptr)

循环链表没有NULL，如果使用普通单链表的遍历方式：

while (p != nullptr) {   // ❌ 永远不会为NULL，死循环！
    cout << p->data;
    p = p->next;
}

这段代码永远不会为NULL，导致无限循环。

2. 正确的遍历方式

方法一：do-while（推荐）

void printList(Node* head) {
    if (head == nullptr) return;
    Node* p = head;
    do {
        cout << p->data << " ";
        p = p->next;
    } while (p != head);    // 回到起点停止
    cout << endl;
}

方法二：for循环

void printList(Node* head) {
    if (head == nullptr) return;
    for (Node* p = head; ; p = p->next) {
        cout << p->data << " ";
        if (p->next == head) break;
    }
}

3. 真题示例

真题（2025年12月） ：

下面代码遍历并输出一个循环单链表，其中head指向链表的第一个节点，横线处应填入（ ）。

void printList(Node* head) {
 if (head == nullptr) return;
 Node* p = head;
 _______________________
 cout << endl;
}

A. while (p != nullptr) { cout << p->data << " "; p = p->next; }
B. while (p->next != nullptr) { cout << p->data << " "; p = p->next; }
C. do { cout << p->data << " "; p = p->next; } while (p != head);
D. for(; p; p=p->next) { cout << p->data << " "; }
答案：C

解析：循环单链表的遍历需要保证从头结点开始，直到再次回到头结点才结束。选项C保证至少输出一次，并在p回到head时停止，防止无限循环。

五、循环链表的插入操作

1. 在循环单链表头部插入

void insertHead(Node*& head, int value) {
    Node* newNode = new Node(value);
    if (head == nullptr) {
        head = newNode;
        newNode->next = head;   // 自己指向自己
    } else {
        newNode->next = head->next;
        head->next = newNode;
    }
}

2. 在循环单链表尾部插入

void insertTail(Node* head, int value) {
    Node* p = head;
    while (p->next != head) {    // 找到尾节点
        p = p->next;
    }
    Node* newNode = new Node(value);
    newNode->next = head;        // 新节点指向头节点
    p->next = newNode;           // 尾节点指向新节点
}

真题示例（2025年12月） ：

在循环单链表尾部插入新结点的代码中，while (p->next != head) { p = p->next; } 的作用是（ ）。
答案：找到尾节点。

3. 循环双链表在p之前插入s

void insertBefore(DNode* p, DNode* s) {
    s->next = p;                    // ① s的next指向p
    s->prev = p->prev;              // ② s的prev指向p的原前驱
    p->prev->next = s;              // ③ p的原前驱的next指向s
    p->prev = s;                    // ④ p的prev指向s
}

真题示例（2026年3月） ：

双向循环链表中要在结点p之前插入新结点s（均非空），以下指针操作正确的是（ ）。
A. s->next = p; p->prev = s; p->next = s; s->prev = p;
B. s->prev = p; s->next = p->next; p->next->prev = s; p->next = s;
C. s->next = p; s->prev = p->prev; p->prev->next = s; p->prev = s;
D. s->next = p; s->prev = nullptr; p->prev = s;
答案：C

解析：在双向链表中结点p之前插入结点s，需要修改四个指针的方向且不能丢失原有的前驱结点引用。首先处理新结点s的两端：s->next = p; 以及 s->prev = p->prev;。接着修改原链表中的指针，必须先修改p的原前驱结点的后继：p->prev->next = s;，最后修改p的前驱指向新结点：p->prev = s;。

六、循环链表的删除操作

1. 删除循环单链表中值为x的节点

void deleteNode(Node*& head, int x) {
    if (head == nullptr) return;

    Node* cur = head;
    Node* prev = nullptr;

    do {
        if (cur->data == x) {
            if (prev == nullptr) {
                // 删除的是头节点
                if (cur->next == head) {
                    // 只有一个节点
                    delete cur;
                    head = nullptr;
                    return;
                }
                // 找到尾节点，更新尾节点的next
                Node* tail = head;
                while (tail->next != head) tail = tail->next;
                tail->next = cur->next;
                head = cur->next;
                delete cur;
                return;
            } else {
                prev->next = cur->next;
                delete cur;
                return;
            }
        }
        prev = cur;
        cur = cur->next;
    } while (cur != head);
}

2. 删除循环双链表中已知节点p

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

注意：循环双链表中删除节点不需要判断头尾边界，因为头尾节点也有有效的前驱和后继指针。

七、约瑟夫环问题（重点）

约瑟夫环是循环链表的经典应用场景，GESP五级考试中多次出现。

问题描述：n个人围成一圈，从第一个人开始数，每次数到第k个人就出圈，求最后留下的人的编号。

#include <iostream>
using namespace std;

struct Node {
    int id;
    Node* next;
    Node(int i) : id(i), next(nullptr) {}
};

int main() {
    int n, k;
    cin >> n >> k;

    // 构建循环链表
    Node* head = new Node(1);
    Node* tail = head;
    for (int i = 2; i <= n; i++) {
        Node* newNode = new Node(i);
        tail->next = newNode;
        tail = newNode;
    }
    tail->next = head;   // 首尾相连

    Node* cur = head;
    Node* prev = tail;

    while (cur->next != cur) {   // 只剩一个节点时停止
        // 数到第k个人
        for (int i = 1; i < k; i++) {
            prev = cur;
            cur = cur->next;
        }
        // 删除cur
        prev->next = cur->next;
        Node* temp = cur;
        cur = cur->next;
        delete temp;
    }

    cout << cur->id << endl;
    delete cur;
    return 0;
}

真题示例（2025年6月） ：

下列C++代码用循环链表解决约瑟夫问题，即假设n个人围成一圈，从第一个人开始数，每次数到第k个人就出圈，输出最后留下的人的编号。

八、循环链表反转（难点）

循环链表的反转需要先将其变为普通链表，再反转，最后重新接回头节点。

Node* reverseCircular(Node* head) {
    if (head == nullptr || head->next == head) return head;

    // 1. 找到尾节点，断开环
    Node* tail = head;
    while (tail->next != head) tail = tail->next;
    tail->next = nullptr;    // 断开环，变为普通链表

    // 2. 普通链表反转
    Node* prev = nullptr;
    Node* curr = head;
    while (curr != nullptr) {
        Node* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }

    // 3. 重新接成环
    head->next = prev;       // 原头节点变成尾节点，指向新头节点
    return prev;             // 返回新的头节点
}

九、Floyd快慢指针判环（了解）

Floyd判环算法用于判断一个单链表中是否存在环，是循环链表相关的重要扩展知识。

bool hasCycle(Node* head) {
    Node* slow = head;
    Node* fast = head;
    while (fast != nullptr && fast->next != nullptr) {
        slow = slow->next;         // 慢指针每次走1步
        fast = fast->next->next;   // 快指针每次走2步
        if (slow == fast) return true;   // 相遇，存在环
    }
    return false;
}

原理：若存在环，快指针终会追上慢指针（相遇）；若无环，快指针先到达末尾（NULL）。

十、GESP五级循环链表真题清单

题号/来源 题目内容 核心考点
2026年3月 第1题 关于单链表、双链表和循环链表的说法判断 判空条件、尾节点指针
2026年3月 第2题 双向循环链表中在p之前插入s 四指针操作顺序
2025年12月 第1题 循环单链表遍历代码填空 do-while遍历
2025年6月 第4题 约瑟夫环循环链表代码填空 约瑟夫环删除逻辑
2025年3月 第3题 双向循环链表删除节点判断 删除操作
2025年3月 第6题 空的双向循环链表初始化 哨兵节点
2025年6月 第6题 is_empty()判断方法 判空条件

十一、易错点汇总

  1. 遍历死循环：循环链表没有NULL，用 while (p != nullptr) 会死循环，必须用 do-while 或判断 p != head。
  2. 判空条件错误：循环链表判空是“指向自己”（head->next == head），不是“指向NULL”。
  3. 尾节点指针理解错误：循环链表的尾节点 next 指向头节点，不是 nullptr。
  4. 插入时指针顺序错误：在p之前插入，必须先处理新节点的两端，再修改原链表的指针。
  5. 删除时忘记更新尾节点：删除头节点时，需要找到尾节点并更新其 next。
  6. 空链表初始化错误：创建一个节点的循环链表时，head->next = head，不能写 head->next = nullptr。
  7. 混淆循环单链表和循环双链表的删除：循环单链表删除头节点需要遍历找尾节点，循环双链表不需要。
  8. 遍历时忘记判空：传入的head可能为nullptr，遍历前必须检查。
  9. 内存泄漏：删除节点后忘记 delete。
  10. 约瑟夫环边界错误：只剩一个节点时循环终止条件应为 cur->next != cur。

十二、速查表

需求 写法 关键注意
创建单节点循环链表 head->next = head; 自己指向自己
尾节点指向 tail->next = head; 不是nullptr
判空（带头节点） head->next == head 指向自己
判空（不带头节点） head == nullptr 头指针为空
遍历（do-while） do { ... p = p->next; } while (p != head); 防止死循环
遍历（for） for (p = head; ; p = p->next) { ... if (p->next == head) break; } 等价写法
在头部插入 newNode->next = head->next; head->next = newNode;
在尾部插入 newNode->next = head; tail->next = newNode; 需要先找尾节点
循环双链表在p前插入s s->next = p; s->prev = p->prev; p->prev->next = s; p->prev = s; 四指针
删除循环双链表节点p p->prev->next = p->next; p->next->prev = p->prev; delete p; 不需要判边界
约瑟夫环终止 while (cur->next != cur) 只剩一个节点
反转 先断环→反转→重新接环 三步

十三、总结

循环链表是GESP五级链表模块的核心内容，也是与单链表、双链表形成对比的重要考点。

  1. 循环链表没有NULL，尾节点的 next 指回头节点。
  2. 遍历必须用 do-while 或判断 p != head，否则死循环。
  3. 判空条件是“指向自己”（head->next == head），不是“指向NULL”。
  4. 循环双链表的尾节点 next 指向头节点，不是 nullptr。
  5. 在循环单链表尾部插入时，需要先遍历找到尾节点。
  6. 循环双链表在p之前插入需要改四个指针，顺序不能乱。
  7. 循环单链表删除头节点需要遍历找尾节点，循环双链表不需要。
  8. 约瑟夫环是循环链表的经典应用，终止条件是 cur->next != cur。
  9. 循环链表反转需要先断环，再反转，最后重新接环。
  10. 多练“判空条件”“遍历终止条件”“在p前插入”“约瑟夫环”四类题。

复习建议：先理解循环链表与单链表的本质区别（尾节点指向头节点），再重点突破判空条件和遍历终止条件两个高频考点；然后练习插入删除操作，注意指针顺序；最后攻克约瑟夫环编程题。考试中先看清是循环单链表还是循环双链表，再判断操作是在p之前还是之后，最后逐条检查指针是否都更新正确。