循环链表核心讲解：从原理到约瑟夫问题实战

数据结构里，单链表算是最基础的入门内容了。但很多人学完单链表会有一个疑惑：尾节点的 next 到底指向哪里？标准答案都是指向 NULL，整个链表到这就戛然而止。那如果我告诉你，有一种链表，它的尾节点不指向 NULL，反而绕回去指向头节点，整个数据结构首尾相连，像一个永远走不完的环，这就是我们今天要聊的循环链表（Circular Linked List）。

循环链表在数据结构课程里的地位很特殊，考研 408 也常考，它不是那种“花架子”知识点，在实际工程里是真的有用——进程调度的时间片轮转、内存管理里的环形缓冲区、音乐播放器的循环列表，背后都是它的影子。这篇博文我会把循环链表从原理、初始化、增删操作到经典应用约瑟夫问题全部带你走一遍，还顺带整理了我在写代码时踩过的坑，希望能帮到正在啃数据结构、准备期末复习或者考研的同学。

1. 循环链表是什么，为什么要让尾节点回头

1.1 单链表的“断点”问题

先从一个最直观的场景出发。假设用单链表存储一个班级的学生名单，你从头节点开始遍历，最后走到某个节点的 next 是 NULL，这就是终点。这个设计很自然，但当你需要“从头再来”的时候，问题就出现了：遍历到底之后，你必须把指针重置回 head，重新走一遍，这条路是断开的，不能“绕回去”。

这个断点会带来几个实际的麻烦。例如轮询场景中，操作系统要把 CPU 时间分配给多个进程，每个进程执行一小段时间再切到下一个，循环往复。用单链表来做的话，每次走到末尾都要把指针复位，这在逻辑上是别扭的，而且边界判断也要多写几条代码。再比如约瑟夫问题，一群人围成圈，从某个人开始报数，数到特定值的人出圈，剩下的人继续。这个“围成圈”的模型天然就是一个环，单链表那种线性的结构根本没法直接模拟。

循环链表就是针对这类“环状模型”而生的方案。它的核心定义只有一条：把单链表的尾节点的 next 指针从 NULL 改成指向头节点（或第一个节点），让整个链表首尾相接，形成一个逻辑上的环。

1.2 循环链表的核心定义

在数据结构教材里，循环链表通常分为两种：

• 单循环链表：每个节点只有一个 next 指针，最后一个节点的 next 指向头节点。
• 双向循环链表：每个节点有 prior 和 next 两个指针，头节点的 prior 指向尾节点，尾节点的 next 指向头节点。

这个“首尾相接”的设计，带来的第一个变化就是遍历条件。单链表的遍历终止条件是 p == NULL，而在循环链表中，你走到尾节点之后，如果继续 p = p->next，指针会回到 head，如果终止条件还是 p == NULL，那永远等不到这一天。所以循环链表的遍历终止条件变成了 p == head（或者 p == L，看你怎么定义头指针），也就是说“转了一圈回到了原点”。

还有一个很实用的附带好处：在带头节点的循环链表中，你可以做到 O(1) 的时间从尾节点回到头节点，也可以从任意节点出发遍历整个链表。这在某些算法场景里能简化很多逻辑。

1.3 循环链表解决了什么问题

说到底，循环链表解决的核心问题是“闭环访问”。它把“末尾”的概念从 NULL 变成了“回到起点”，适用于以下几类场景：

• 轮转调度：多个进程/任务轮流使用资源，循环链表天然支持“转一圈再来”。
• 约瑟夫环模拟：围成一圈报数出圈，循环链表是最直观的建模工具。
• 环形缓冲：音频流、视频流、日志系统里常见的 FIFO 缓冲区，用循环链表实现可以避免频繁的内存搬移。
• 播放器循环列表：歌单播完自动回到第一首。

不过也要提醒一句，并不是所有场景都适合循环链表。比如你需要频繁随机访问中间元素，那数组更合适；如果你只需要尾插和头删，队列结构就行，不必强行上循环链表。选型逻辑永远是：先看数据有没有“环状关系”，再看操作模式对不对路。

2. 单向循环链表与双向循环链表：结构与判空逻辑

2.1 单向循环链表的基本形态

先看单循环链表的节点定义。在 C 语言里，节点结构体和单链表一模一样：

c复制typedef struct Node {
    int data;
    struct Node *next;
} Node;

区别在于链表的组织形态。如果是不带头节点的单循环链表，头指针 head 指向第一个节点，最后一个节点的 next 指向 head。如果带头节点，头节点是空的哨兵节点，真正的数据从 head->next 开始，尾节点的 next 指回头节点。

带头节点的好处是：空表的判断变得非常简单。你只需要写 L->next == L，就表示这是一个空的循环链表。如果不带头节点，你面对空表时 head 为 NULL，判断逻辑要写 head == NULL，两种表示混在一起容易乱。考研和考试里更倾向于考察带头节点的版本，因为它逻辑统一、边界清晰。

2.2 双向循环链表的结构

双向循环链表在节点定义上多了一个 prior 指针：

c复制typedef struct DNode {
    int data;
    struct DNode *prior;
    struct DNode *next;
} DNode;

对于带头节点的双向循环链表，两个核心不变量是：

• L->next == L 时链表为空（只看 next 方向）
• L->prior == L 时链表也为空（只看 prior 方向）

当链表非空时，有 L->next 是第一个节点，L->prior 是最后一个节点。这意味着你可以 O(1) 拿到链表两端，这在频繁需要“队尾插入、队头删除”的场景里特别有价值。

2.3 带头节点和不带头节点的选择

很多初学者会纠结这个问题：到底要不要带头节点？我个人的建议很明确：无脑带头节点。

原因有三点。第一，带头节点的空表判断统一，L->next == L 一眼就能看出来。第二，在头部插入、删除时，不需要单独处理 head 指针的变化，因为 head 始终指向那个哨兵节点，不会变。第三，尾节点的 next 永远指向头节点，逻辑上有唯一的“锚点”。不带头节点的话，每次操作都要判断 head 是否需要更新，代码量上去不说，bug 率也明显增加。

实际考试或者面试里，如果题目没有特殊要求，我建议你直接声明“采用带头节点的循环链表实现”，然后按这个思路去写，结构清晰，不容易丢分。

3. 实操：从零构建一个可用的单循环链表

3.1 节点定义与初始化

在开始构建之前，先想清楚整个链表需要提供哪些操作。一个基础的循环链表至少应该有：初始化、构建（尾插创建）、遍历打印、插入、删除这几个核心操作。

初始化带头节点的单循环链表：

c复制Node *initList() {
    Node *L = (Node *)malloc(sizeof(Node));
    if (L == NULL) {
        printf("内存分配失败\n");
        return NULL;
    }
    L->data = 0;      // 头节点数据域一般不用，或者用来存储长度
    L->next = L;      // 关键：头节点的 next 指向自己
    return L;
}

注意这行 L->next = L，它让头节点自成一个环。这样初始化之后，这个空链表就是一个合法的循环链表，L->next == L 成立，后面所有操作都可以以这个不变量为基准来写，不用再特殊处理空表的情况。

3.2 尾插法构建循环链表

尾插法就是每次把新节点挂到链表的尾部。在单循环链表中，“尾部”不是靠记住一个 tail 指针来定位的，而是通过 L->prior 或者遍历找到最后一个节点。但为了效率，实现的时候可以额外维护一个 tail 指针，也可以每次从头遍历。这里我们先用最直观的写法：遍历到尾节点，再插入。

c复制void insertAtTail(Node *L, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = value;

    // 找到尾节点：它的 next 指向头节点
    Node *p = L;
    while (p->next != L) {
        p = p->next;
    }

    // 新节点接到尾部
    p->next = newNode;
    newNode->next = L;   // 尾节点指向头节点，闭环
}

这个写法最清晰，适合理解和考试。但效率是 O(n) 的，因为每次插入都要从头跑到尾。如果一次性要插入大量数据，可以维护一个 tail 指针，让插入变成 O(1)，后面我会讲到这个优化。

3.3 遍历输出与计数

遍历循环链表是最容易写错的地方。很多人下意识会用 while (p != NULL)，结果程序直接死循环跑飞了。正确写法是用“回到头节点”作为终止条件：

c复制void printList(Node *L) {
    Node *p = L->next;   // 从第一个数据节点开始
    if (p == L) {
        printf("空链表\n");
        return;
    }
    while (p != L) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

这段代码的逻辑是：p 从头节点的下一个开始走，每走一步打印一个数据，直到 p 再次回到头节点 L，说明把整圈走完了。这里有一个非常关键的细节：p 的初始值是 L->next，终止条件是 p != L，两者配合正好遍历全部数据节点且只走一圈。很多人在写的时候会把终止条件写成 p->next != L，这样会漏掉最后一个节点，后面我会在常考问题部分专门展开对比。

4. 核心操作：插入、删除的细节与常见坑

4.1 插入节点：头部、尾部和中间位置

循环链表的插入操作，关键点在于“先把新节点接好，再拆旧链条”，这个顺序不能反。以在 p 节点之后插入 newNode 为例，标准三步：

c复制newNode->next = p->next;
p->next = newNode;

如果 p 恰好是尾节点，p->next 是指向头节点的，那么新节点插入后会继承这个指向，新的尾节点变成 newNode，链表依然是闭环。这正是循环链表比单链表在处理尾部插入时更优雅的地方：不需要特殊判断 p 是不是尾节点，代码可以一套逻辑走天下。

头部插入时，做法是 L->next 之后插入，即 p = L，然后执行同样的两步。因为头节点本身就是哨兵，所以头部插入和中间位置插入在代码上是同一个操作。

4.2 删除节点：边界条件别踩坑

删除节点要分三种情况考虑，但说白了都是两步：找到目标节点的前驱，然后让前驱的 next 跳过目标节点。

c复制int deleteNode(Node *L, int value) {
    Node *p = L;
    // 找到值等于 value 的节点的前驱
    while (p->next != L && p->next->data != value) {
        p = p->next;
    }
    if (p->next == L) {
        printf("没有找到该值\n");
        return 0;
    }
    Node *target = p->next;
    p->next = target->next;
    free(target);
    return 1;
}

这段代码里的 while (p->next != L && p->next->data != value) 是两个条件的联查：第一个条件确保没有走到头，第二个条件判断当前节点的下一个是否匹配。有一个常见的坑是：当链表只有一个数据节点时，p->next 指向 L，如果这时你写 p->next->data 就会访问到头节点的 data 域。虽然头节点的 data 一般不参与比较，逻辑上不会出错，但代码的语义会变得混乱。

还有一个更隐蔽的坑：如果链表中只有一个数据节点并且要删掉它，删完之后 L->next 应该重新指向 L，即恢复空表状态。上面的代码里，p 是头节点，target 是唯一的数据节点，执行 p->next = target->next 后，target->next 本身指向 L，所以 p->next 变成 L，空表不变量 L->next == L 自动恢复。这就是带头节点的好处：你不需要写额外代码去修复空表状态。

4.3 带头节点和不带头节点的复杂度对比

我见过不少人在不带头节点的链表上写删除，head 指针在每次删除后要不要更新，判断半天，最后 debug 到怀疑人生。带头节点版本就不会有这个问题，因为 head 永远指向哨兵，不会被删除。

一个额外的优化思路：如果你频繁做尾部插入，可以维护一个 tail 指针指向尾节点。这样尾部插入 O(1)，且从 tail 到 head 也 O(1)。但代价是插入、删除时要保证 tail 指针的正确性，代码复杂度会上升。考研里如果你的目标是“稳妥写出正确答案”，用遍历找尾节点的方式是最不容易出错的。

5. 经典应用：约瑟夫问题完整实现与解析

5.1 问题描述与模型选择

约瑟夫问题是一个非常经典的循环链表应用场景。题目描述有很多版本，核心模式是这样的：n 个人围成一圈，从第 k 个人开始报数，报到 m 的人出圈，然后从下一个人重新报数，直到所有人都出圈，输出出圈顺序。

为什么这个问题适合用循环链表？因为“围成一圈”这个模型本身就是环状结构，你用一个数组当然也能模拟，但每次出圈都要把数组元素往前搬，时间复杂度会变成 O(n^2)。而循环链表删除一个节点是 O(1)（前提是定位到它的前驱），整个过程只需要遍历和删除，非常契合。

5.2 代码实现：完整的约瑟夫环求解

稍微规划一下整体逻辑：

1. 创建 1 到 n 的循环链表。
2. 从第 k 个节点开始，数 m-1 步，找到要出圈的节点的前驱。
3. 删除该节点，输出其编号。
4. 从下一个节点继续报数，重复直到链表为空。

动手写代码：

c复制#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

// 创建带头节点的循环链表，数据为 1~n
Node* createList(int n) {
    Node *L = (Node*)malloc(sizeof(Node));
    L->next = L;  // 空表自环
    Node *tail = L;

    for (int i = 1; i <= n; i++) {
        Node *p = (Node*)malloc(sizeof(Node));
        p->data = i;
        tail->next = p;
        p->next = L;
        tail = p;
    }
    return L;
}

void josephus(int n, int k, int m) {
    Node *L = createList(n);
    Node *p = L;

    // 先找到第 k 个人的前驱节点
    // p 从 L 开始，每前进 k 步，p->next 就是第 k 个节点
    for (int i = 0; i < k; i++) {
        p = p->next;
    }
    // 此时 p 指向第 k 个节点（或第 k 个节点的前驱？需要再斟酌）

    // 更稳妥的做法：先让 p = L，走 k-1 步，使得 p->next 是第 k 个节点
    p = L;
    for (int i = 1; i < k; i++) {
        p = p->next;
    }

    while (L->next != L) {
        // 报数 m，找到第 m 个节点的前驱
        for (int i = 1; i < m; i++) {
            p = p->next;
        }
        Node *out = p->next;      // out 是要出圈的人
        printf("%d ", out->data);
        p->next = out->next;      // 删除 out
        free(out);

        // 如果删完链表为空，跳出
        if (L->next == L) break;
    }
    printf("\n");

    free(L);
}

int main() {
    josephus(7, 3, 3);  // 7个人，从第3个开始，数到3出圈
    return 0;
}

关于指针定位这里有一个很容易出错的细节，我专门多说两句。要让 p 最终指向“要出圈节点的前驱”，你得先明确 p 的初始指向。以“从第 k 个人开始数 1”为例：如果 p 指向第 k-1 个人，那么 p->next 就是第 k 个人，报数 m 次之后，p->next 就是要出圈的人。所以正确的做法是先把 p 移动到第 k-1 个节点（即从头走 k-1 步），然后循环 m-1 次，每次都执行 p = p->next。因为第 k 个人自己念“1”，所以只需要走 m-1 步就能让 p->next 指向报 m 的人。上面代码里我用了 for (int i = 1; i < m; i++)，效果是一样的，每次走一步，循环 m-1 次。

如果你把“走到第 k 个人”和“报数 m 次”的步数算错一位，结果就会整个错掉。这里建议大家动手推演一遍，比如 n=7、k=3、m=3，第一轮出圈的人应该是 5，你可以手动验证一下代码的输出是否符合。

5.3 约瑟夫问题的复杂度分析与数学扩展

上面的循环链表实现，时间复杂度是 O(n*m)：每删除一个人需要数 m 次，总共要删 n 个人。空间复杂度是 O(n)，用于存储指针。

如果 m 特别大，这个 O(n*m) 可能会比较慢。但约瑟夫问题有一个著名的数学递推解法：设 f(n, m) 表示 n 个人报数 m 的出圈者编号（从 0 开始），则：

code复制f(1, m) = 0
f(n, m) = (f(n-1, m) + m) % n

这个递推可以做到 O(n) 求出最后一个幸存者的编号，不需要真正模拟删除过程。但它的推导比较绕，考研里如果题目只问“最后剩下谁”，用数学方法更快；如果题目要求输出完整的出圈序列，那循环链表的模拟更直观。两种思路都建议掌握，面试时如果能从链表模拟讲到数学优化，会是一个加分项。

6. 常见问题与排查技巧实录

6.1 死循环：最常见的翻车现场

我教过不少学生写循环链表，第一个 bug 十有八九是死循环。表现是程序跑起来之后光标一直闪，Ctrl+C 才能停下来。

原因往往是遍历终止条件写成了 p != NULL。在单链表里这是对的，但在循环链表里永远成立不了，因为环里面没有 NULL。排查方法也很简单：检查所有 while 循环的终止条件，凡是遍历链表的循环，终止条件必须是 p == L 或 p->next == L，而不是 p == NULL。

另一处容易死循环的是插入操作。如果你在尾插时忘了把新节点的 next 指向头节点，即写成了 newNode->next = NULL，那下一次遍历走到这个节点时就会越界访问，最终程序崩掉或者陷入不可预期的行为。这属于“闭环断了”的问题，调试方法是在纸上画出每一步的指针指向，特别是新节点插入前后的 next 变化。

6.2 遍历时少一个节点：p != L 和 p->next != L 的区分

这是另一个高频错误。很多人写打印函数时会把终止条件写成 while (p->next != L)，然后发现最后一个节点没打出来，或者最后多打了一个头节点。

原因在于：p != L 表示“p 已经回到头节点就停”，此时 p 走了完整一圈，包含所有数据节点。而 p->next != L 表示“p 的下一个是头节点就停”，此时 p 是最后一个数据节点，循环体执行完打印最后一个节点就停了，所以用这个条件配合先打印再移动，其实是能打印全部节点的。但是如果你在循环体内先移动指针再打印，两者结果就完全不同了。

我建议统一记住一个原则：终止条件只看当前指针 p 是否回到了头节点。初始 p = L->next，循环体打印并移动，终止 while (p != L)，这三者是配套的，一眼就能确认边界，不会数错。

6.3 删除节点后指针悬空

删除节点后，如果只是执行了 free(target) 而没有把前驱节点的 next 接到 target->next 上，链表就断了。更隐蔽的是，如果删的是尾节点，你没有把新的尾节点指向头节点，环也会被破坏。我在第 4.2 小节里的 deleteNode 函数是能正确处理尾节点的，原因是它先定位前驱再统一执行 p->next = target->next，而 target->next 本身已经指向了正确位置，不需要额外判断。如果你写的是一套“分情况讨论”的版本，请务必检查尾节点分支是否把 next 指回了 L。

6.4 考研与面试高频考点镜像

结合最近的热搜词，这里帮大家划个重点。408 考研里循环链表的考察频率不低，常见的出题角度有：

• 约瑟夫环问最后剩余者的编号。
• 判断一个单链表中是否存在环，以及找环入口。
• 双向循环链表的插入、删除代码补全题。
• 利用循环链表实现队列或栈。
• 对比顺序表和链表在插入、删除、访问上的复杂度。

面试里则更喜欢考“判断链表有没有环”这个题。常见的快慢指针解法是：slow 每步走一格，fast 每步走两格，如果它们能相遇，说明链表有环；相遇后让 slow 从头再出发，fast 保持当前位置，两者同速走，再次相遇的节点就是环入口。这个想法不算难，但要把证明逻辑讲清楚，核心是 fast 比 slow 多走的路程恰好是环长的整数倍。

如果你准备的是考研，建议把书上的循环链表代码亲手敲两遍，一遍照着书抄，一遍合着书写。手写代码和看代码完全是两个难度层级的技能，考试时你需要在半小时内写出无 bug 的完整实现，这个熟练度没有捷径。

结尾

聊到这里，循环链表的核心内容基本都过了一遍。它本质上就是在单链表上多做了一点点改动——尾指针指向头节点——但就是这一点改动，让它在轮转调度、约瑟夫问题、环形缓冲区等场景里变得极其顺手。我个人在实际教学中最深的感触是：很多人一开始觉得循环链表复杂，其实是因为脑子里总被“NULL 才是终点”的思维定式束缚住了。真正常见的坑就那么几个，死循环、少遍历一个节点、删除断链，先把这几个问题想透，代码自然就稳了。

最后给你一个练习建议：不要急着写高深的应用，先把无头节点的单循环链表实现一遍，再把带头节点的实现一遍，对比两者的代码量差异。然后尝试用双向循环链表实现一个 deque（双端队列），在头部和尾部都能 O(1) 插入删除。这些基础练扎实之后，你会发现后面学栈、队列、树都会顺很多。数据结构这种东西，不动手敲代码是永远学不会的。