一、基础概念类
提问：循环链表和普通线性链表的核心区别？有什么优劣？适用场景？
回答：
可以把普通线性链表理解成直线跑道，有明确的起点和终点，跑到头就结束；循环链表是环形跑道，跑完一圈会回到起点，首尾相连。
核心优劣对比
| 遍历逻辑 | 遇 null 终止，单向遍历 | 遇头节点终止，可循环遍历 |
| 首尾访问 | 单链表尾访问需 O (n) 遍历 | 带头哨兵可 O (1) 直接访问首尾 |
| 边界复杂度 | 空链表、头尾操作需单独判断 | 哨兵模式下无特殊边界，逻辑统一 |
| 内存开销 | 和对应单 / 双向链表一致 | 仅多 1 个哨兵节点，开销可忽略 |
| 适用场景 | 通用线性存储 | 环形遍历、周期调度、循环淘汰类场景 |
两类循环链表的分工
单向循环链表：适合仅需正向循环遍历、操作简单的场景（如约瑟夫环）
双向循环链表：工业级首选，兼顾双向遍历 + O (1) 首尾操作，绝大多数工程场景用这个
二、核心操作类
节点定义
// 单向循环链表
struct CListNode {
int val;
CListNode* next;
CListNode(int v) : val(v), next(nullptr) {}
};
// 双向循环链表
struct CDListNode {
int val;
CDListNode* next;
CDListNode* prev;
CDListNode(int v) : val(v), next(nullptr), prev(nullptr) {}
};
初始化
DCListNode* initDCList() {
DCListNode* head = new DCListNode(0);
head->next = head;
head->prev = head;
return head;
}
头部插入节点（O (1)）
void addToHead(DCListNode* head, DCListNode* node) {
node->prev = head;
node->next = head->next;
head->next->prev = node;
head->next = node;
}
尾部插入节点（O (1))
void addToTail(DCListNode* head, DCListNode node) {
node->next = head;
node->prev = head->prev;
head->prev->next = node;
head->prev = node;
}
删除指定节点（O (1)）
void removeNode(DCListNode* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
node->next = nullptr;
node->prev = nullptr;
}
遍历
void traverse(DCListNode* head) {
DCListNode* curr = head->next;
while(curr != head) {
curr = curr->next;
}
}
三、进阶理解类
提问：循环链表最容易踩的坑是什么？怎么规避？
回答：
最高频的两个坑：
遍历死循环：忘记循环链表没有 null 尾节点，沿用普通链表的curr != nullptr做终止条件，直接陷入死循环。规避方法：统一用头哨兵做终止标记，写遍历前先明确结束条件。
首尾节点指针维护遗漏：不带头哨兵的循环链表，插入 / 删除头 / 尾节点时，容易忘记修改尾节点的 next 指针，导致环断开。规避方法：工程实现一律加头哨兵，所有操作都等价于中间节点操作，逻辑完全统一。
提问：约瑟夫环问题为什么首选循环链表实现？
回答：
约瑟夫环的核心逻辑是「环形循环计数 + 定点删除」，和循环链表的特性完全匹配：
-
天然支持环形遍历，不用手动处理到头折返的逻辑
-
删除节点只需修改指针，不用挪动数据，时间效率高
-
双向循环链表可以 O (1) 删除当前节点，单向循环链表也只需找到前驱即可删除
如果用数组实现，每次删除元素都要挪动后续数据，时间复杂度高很多；用普通链表要自己处理尾接头的环形逻辑，代码冗余。
四、项目实战知识
经典算法实战
约瑟夫环（面试手写高频题）
题目：n 个人围成一圈，从第 1 个人开始报数，报到 m 的人出列，求最后剩下的人的编号。
// 单向循环链表实现
int lastRemaining(int n, int m) {
if(n == 0) return -1;
// 1. 构建带哨兵的单向循环链表
CListNode* head = new CListNode(0); // 头哨兵
CListNode* curr = head;
for(int i = 1; i <= n; i ++ ) {
curr->next = new CListNode(i);
curr = curr->next;
}
curr->next = head; // 尾节点接哨兵，完成成环
CListNode* prev = head; // 待删除节点的前驱
int count = 0;
while(head->next != head) {
if(count == m – 1) {
CListNode* del = prev->next;
prev->next = del->next;
delete del;
count = 0;
} else {
prev = prev->next;
count ++ ;
}
}
int res = prev->val;
delete head;
return res;
}
提醒：链表版逻辑直观贴合考点，时间复杂度 O (n*m)，适合 n 不大的场景；n 极大的场景可补充数学公式法做优化。
核心项目应用：时间轮定时器
场景说明：后端开发中高频使用的定时器组件（如 Netty、Kafka、Skynet、Redis 的定时任务），绝大多数基于循环链表实现的时间轮，是循环链表最核心的工业落地场景。
实现原理
-
用循环结构（数组模拟环形槽位，每个槽位挂一条定时任务链表）代表时间轮，每个槽位对应一个时间刻度
-
指针按固定时间步长在环形槽位上循环移动，走到哪个槽位，就执行该槽位里的所有到期定时任务
-
新增定时任务时，根据超时时间计算对应的槽位，挂到对应链表上
为什么用循环链表结构？
-
时间是周期性的，环形结构天然适配时间的循环特性，不用频繁重置指针
-
新增 / 删除定时任务都是 O (1) 的链表操作，到期批量执行也是 O (k)（k 为当前槽任务数），性能远高于用堆实现的定时器
-
高并发场景下，时间轮的精度和吞吐量都能满足服务端调度需求
极简单层时间轮框架
#include <list>
#include <vector>
#include <functional>
using namespace std;
class SimpleTimeWheel {
private:
int slotNum; // 槽位总数，例如60个槽对应60秒
int currentSlot; // 当前指针指向的槽位
vector<list<function<void()>>> slots; // 每个槽位对应一条任务链表，数组索引模拟循环
public:
SimpleTimeWheel(int n) : slotNum(n), currentSlot(0) {
slots.resize(slotNum);
}
// 添加定时任务,delay秒后执行
void addTask(int delay, function<void()> task) {
int targetSlot = (currentSlot + delay) % slotNum;
slots[targetSlot].push_back(task);
}
// 每过1个时间刻度走一步，执行当前槽的到期任务
void tick() {
for(auto& task : slots[currentSlot]) {
task();
}
slots[currentSlot].clear();
currentSlot = (currentSlot + 1) % slotNum;
}
}
其他常见落地场景
操作系统时间片轮转调度：就绪进程排成双向循环链表，CPU 按时间片依次调度，跑完一圈回到队首
环形消息队列：用双向循环链表实现无界环形队列，适配生产者消费者模型，头尾操作都是 O (1)
游戏回合制战斗：角色排成循环链表，按顺序轮流行动，天然适配回合循环逻辑
令牌桶限流：用循环结构维护令牌生成周期，循环补充令牌
