数据结构 - 循环链表
循环链表是链表结构的一种变体，其核心特点是链表的最后一个节点不再指向 NULL，而是重新指向第一个节点，从而使整个链表在逻辑上形成一个环状结构。
循环链表的结构特点
循环链表 — 单向循环与双向循环
单向循环链表
10
→
20
→
30
↺ tail.next = head (回到起点)
每个节点只有 next 指针，尾节点指向头节点形成闭环
双向循环链表
10
⇄
20
⇄
30
↺ head.prev = tail, tail.next = head
每个节点有 prev + next，头尾互连形成双环
普通链表：末尾 next = NULL，遍历终止条件为 cur == NULL
循环链表：末尾 next = head，遍历终止条件为 cur == head（回到起点）
常见操作：插入头节点 O(n) — 需先找到尾节点 | 遍历使用 do...while 循环
插入尾节点 O(1)（维护 tail 指针）| 删除同理
循环链表主要分为两种类型：
- 单向循环链表：每个节点只保存一个 next 指针，最后一个节点的 next 重新指向头节点
- 双向循环链表：在双向链表的基础上，最后一个节点的 next 指向头节点，头节点的 prev 指向最后一个节点
循环链表结构最大的特点在于它天然支持首尾相接的连续遍历。
判断遍历结束的条件不是"是否到达 NULL"，而是"是否回到了起始节点"。
基本操作
实例
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* 创建新节点 */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = newNode; /* 单节点时，next 指向自身，自成环 */
return newNode;
}
/* 在循环链表头部插入节点
时间复杂度：O(n) — 需要先找到尾部节点来更新其 next 指针 */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
return newNode; /* 空链表，新节点自成环 */
}
/* 找到尾部节点（即 next 指向 head 的节点） */
struct Node* tail = head;
while (tail->next != head) {
tail = tail->next;
}
newNode->next = head; /* 新节点的 next 指向原头节点 */
tail->next = newNode; /* 尾节点的 next 指向新节点（新头） */
return newNode; /* 新节点成为新的头节点 */
}
/* 遍历循环链表（一圈）
从头节点开始，直到再次回到头节点时停止 */
void traverse(struct Node* head) {
if (head == NULL) return;
struct Node* cur = head;
printf("循环链表: ");
do {
printf("%d -> ", cur->data);
cur = cur->next;
} while (cur != head); /* 回到起点时结束 */
printf("(回到起点)\n");
}
int main() {
struct Node* head = NULL;
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverse(head);
/* 输出: 循环链表: 10 -> 20 -> 30 -> (回到起点) */
return 0;
}
#include <stdlib.h>
struct Node {
int data;
struct Node* next;
};
/* 创建新节点 */
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = newNode; /* 单节点时，next 指向自身，自成环 */
return newNode;
}
/* 在循环链表头部插入节点
时间复杂度：O(n) — 需要先找到尾部节点来更新其 next 指针 */
struct Node* insertAtHead(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
return newNode; /* 空链表，新节点自成环 */
}
/* 找到尾部节点（即 next 指向 head 的节点） */
struct Node* tail = head;
while (tail->next != head) {
tail = tail->next;
}
newNode->next = head; /* 新节点的 next 指向原头节点 */
tail->next = newNode; /* 尾节点的 next 指向新节点（新头） */
return newNode; /* 新节点成为新的头节点 */
}
/* 遍历循环链表（一圈）
从头节点开始，直到再次回到头节点时停止 */
void traverse(struct Node* head) {
if (head == NULL) return;
struct Node* cur = head;
printf("循环链表: ");
do {
printf("%d -> ", cur->data);
cur = cur->next;
} while (cur != head); /* 回到起点时结束 */
printf("(回到起点)\n");
}
int main() {
struct Node* head = NULL;
head = insertAtHead(head, 30);
head = insertAtHead(head, 20);
head = insertAtHead(head, 10);
traverse(head);
/* 输出: 循环链表: 10 -> 20 -> 30 -> (回到起点) */
return 0;
}
循环链表遍历的关键是使用
do...while语句而不是while。因为使用while (cur != head)时，初始状态 cur 就等于 head，循环根本不会执行。而do...while保证至少执行一次循环体，再检查终止条件。
经典应用：约瑟夫环问题
约瑟夫环问题 (n=7, m=3)
初始状态：7 个人围成一圈，从 1 开始报数，每数到第 3 人淘汰
1开始
2
3第1轮
4
5
6
7
↻ 报数方向 1, 2, 3, ...
淘汰顺序与最终结果 (n=7, m=3)
3
第1轮6
第2轮2
第3轮7
第4轮5
第5轮1
第6轮4
幸存者约瑟夫环问题（Josephus Problem） 是一个经典的数学问题：
假设 n 个人围成一圈，从第 1 个人开始报数，每数到第 m 个人就将其淘汰出圈，然后从下一个人重新开始报数，如此循环，直到只剩下最后一个人。
这个问题天然契合循环链表"首尾相连、循环访问"的结构特性。
实例
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data; /* 人的编号 */
struct Node* next;
};
/* 约瑟夫环求解
参数：n 总人数, m 每次数到 m 的人出圈
使用循环链表模拟整个过程 */
void josephus(int n, int m) {
if (n <= 0) return;
/* 步骤 1：创建包含 n 个人的循环链表（编号 1~n） */
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = head; /* 只有一个人时，自环 */
struct Node* tail = head;
for (int i = 2; i <= n; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->next = head; /* 新节点的 next 始终指向头 */
tail->next = newNode; /* 前一个节点的 next 指向新节点 */
tail = newNode; /* tail 后移 */
}
/* 步骤 2：模拟淘汰过程 */
struct Node* cur = head;
struct Node* prev = tail; /* prev 指向 cur 的前驱，初始为尾节点 */
printf("约瑟夫环 (n=%d, m=%d) 淘汰顺序: ", n, m);
while (cur->next != cur) { /* 只剩一个节点时（自环）结束 */
/* 报数：数 m-1 次，让 prev 和 cur 同时前进 */
for (int count = 1; count < m; count++) {
prev = cur;
cur = cur->next;
}
/* 数到 m，cur 被淘汰 */
printf("%d ", cur->data);
prev->next = cur->next; /* 跳过 cur */
free(cur); /* 释放被淘汰的节点 */
cur = prev->next; /* 从下一个人重新开始报数 */
}
printf("=> 最后幸存者: %d\n", cur->data); /* 输出最后一个人 */
free(cur);
}
int main() {
josephus(7, 3);
/* 输出: 约瑟夫环 (n=7, m=3) 淘汰顺序: 3 6 2 7 5 1 => 最后幸存者: 4 */
return 0;
}
#include <stdlib.h>
struct Node {
int data; /* 人的编号 */
struct Node* next;
};
/* 约瑟夫环求解
参数：n 总人数, m 每次数到 m 的人出圈
使用循环链表模拟整个过程 */
void josephus(int n, int m) {
if (n <= 0) return;
/* 步骤 1：创建包含 n 个人的循环链表（编号 1~n） */
struct Node* head = (struct Node*)malloc(sizeof(struct Node));
head->data = 1;
head->next = head; /* 只有一个人时，自环 */
struct Node* tail = head;
for (int i = 2; i <= n; i++) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = i;
newNode->next = head; /* 新节点的 next 始终指向头 */
tail->next = newNode; /* 前一个节点的 next 指向新节点 */
tail = newNode; /* tail 后移 */
}
/* 步骤 2：模拟淘汰过程 */
struct Node* cur = head;
struct Node* prev = tail; /* prev 指向 cur 的前驱，初始为尾节点 */
printf("约瑟夫环 (n=%d, m=%d) 淘汰顺序: ", n, m);
while (cur->next != cur) { /* 只剩一个节点时（自环）结束 */
/* 报数：数 m-1 次，让 prev 和 cur 同时前进 */
for (int count = 1; count < m; count++) {
prev = cur;
cur = cur->next;
}
/* 数到 m，cur 被淘汰 */
printf("%d ", cur->data);
prev->next = cur->next; /* 跳过 cur */
free(cur); /* 释放被淘汰的节点 */
cur = prev->next; /* 从下一个人重新开始报数 */
}
printf("=> 最后幸存者: %d\n", cur->data); /* 输出最后一个人 */
free(cur);
}
int main() {
josephus(7, 3);
/* 输出: 约瑟夫环 (n=7, m=3) 淘汰顺序: 3 6 2 7 5 1 => 最后幸存者: 4 */
return 0;
}
其他应用场景
| 场景 | 说明 |
|---|---|
| 操作系统时间片轮转调度 | CPU 按时间片轮流分配给各个进程，一个进程用完时间片后轮到下一个，形成循环 |
| 多人游戏轮流出牌 | 棋牌类游戏中，玩家按顺时针（或逆时针）顺序轮流操作 |
| 循环缓冲区 | 音频/视频数据流的循环缓冲区，写满后回到开头覆盖旧数据 |