1. 为什么循环链表值得单独写一篇它和普通链表的本质差异很多初学者学完单链表之后觉得循环链表只是把尾结点的 next 指向头结点这么一个小改动没什么值得深究的。这个想法我当年也有直到自己在实际项目里因为一个循环链表的边界条件调试到凌晨两点才意识到这个小改动背后藏着完全不同的思维模式。先说循环链表到底解决什么问题。普通单链表的尾结点 next 指向 nullptr这意味着你从 head 出发遍历完整个链表之后必须停下来想再回头只能重新从头开始走。这种结构在只需要线性扫描一遍的场景里完全够用但如果你面对的是轮询调度、环形缓冲区、约瑟夫环、消息队列的循环消费这类需求普通链表就非常别扭。你需要在遍历到尾部时手动把指针拨回头部代码里到处是 if (p nullptr) p head; 这种分支写多了不仅啰嗦还容易漏判。循环链表把这些分支全部消灭掉了。尾结点的 next 直接指向头结点整个链表成为一个环遍历可以用一个 do-while 或者带哨兵条件的 while 完成不需要为尾部回头单独写逻辑。数据结构的本质是用结构表达逻辑循环链表就是用结构本身的闭合性把周而复始这个语义固化下来而不是靠每次使用时的判断条件去维持。但代价也随之而来。普通链表有明确的终点而循环链表没有自然终止条件所有遍历、查找、删除操作都必须依赖回到起点这个判定。一个判断条件写错最常见的表现就是死循环或者漏处理某个结点。后面我会详细讲这些坑。另外说一下循环链表和双向循环链表的差别。双向循环链表是每个结点既有 next 又有 prev头结点的 prev 指向尾结点尾结点的 next 指向头结点两个方向都能转圈。单向版本只保留 next实现更省内存逻辑也更简练适合大多数只需要单向轮转的场景。本文讲的以单向循环链表为主双向版本在最后提一下扩展思路。核心关键词循环链表C在实操层面有两层含义第一层是用 C 的类封装和 RAII 思想把循环链表写成可复用的容器第二层是理解循环结构在各种算法题和工程场景中的应用。这篇我会把两层都覆盖到。2. 手写循环链表从结点定义到核心操作的完整实现2.1 结点设计与类的封装思路循环链表不是 C 标准库里的现成容器不像 vector、list 那样直接用就行。工程里要么自己封装要么在刷算法题时手写。自己封装时第一步是定义结点结构。template typename T struct Node { T data; NodeT* next; explicit Node(const T value) : data(value), next(nullptr) {} };这里用 struct 而不是 class 只是习惯问题因为结点本身就是数据和指针的聚合没有太多私有概念需要保护。构造函数初始化 data 和 next避免出现未初始化的野指针。特别注意C 里结构体成员默认是 public但构造函数还是要老老实实写新分配出来的结点如果不初始化 next后面判断循环终止条件时会读到随机地址那是极其隐蔽的内存错误。类封装的思路我建议把链表本身封装成一个类对外暴露 insert、remove、find、print 这类语义化接口内部维护 head 和 size 两个成员。head 是哨兵还是实际数据结点这是一个人为决策点。我习惯使用带头结点的循环链表头结点不存储有效数据只作为哨兵它的 next 指向第一个实际数据结点尾结点的 next 指回头结点。这么做的好处是插入和删除操作的代码对空表和非空表一视同仁不需要特殊处理头指针本身。刷题时很多解法是不带头结点的那种更适合利用指针的引用操作来抹平空表差异但封装成类时带头结点明显更省心。template typename T class CircularLinkedList { private: NodeT* head; size_t size_; public: CircularLinkedList() : head(new NodeT(T())), size_(0) { head-next head; // 空表状态下哨兵自指 } ~CircularLinkedList() { clear(); delete head; } bool empty() const { return size_ 0; } size_t size() const { return size_; } void clear() { while (!empty()) { remove_after(head); } } private: // 删除 p 的下一个结点返回被删结点的数据 T remove_after(NodeT* p) { if (p-next head) { throw std::out_of_range(cannot remove sentinel); } NodeT* target p-next; T value target-data; p-next target-next; delete target; --size_; return value; } };空表时 head-next head这个自指初始化是循环链表最关键的一行代码。它让空表和非空表在结构上没有本质差别都是从 head 出发绕一圈回来只不过空表绕一圈立刻回到自身。很多 bug 都是因为空表状态下 head-next 为 nullptr导致后续操作要么解引用空指针要么在循环遍历时条件判断混乱。2.2 尾插、头插与指定位置插入的细节插入操作是链表最频繁的操作循环链表里插入的核心思路是先找到目标位置的前驱结点然后新结点从中间挤进去。普通链表和循环链表在这一点上没有区别区别在于找前驱时怎么判断找到了尾部。尾插是最常用的往末尾追加一个结点。在带头结点的循环链表里尾结点其实就是 head 的前驱所以尾插可以理解为在 head 之前插入或者等价地在尾结点之后插入。void push_back(const T value) { insert_after(head, value); // 这一步其实是插入到 head 前面 }等等这里有个反直觉的点。带头结点的循环链表head 是哨兵它并不代表链表的第一个数据结点而是链表的入口标记。head 的前驱是尾结点head 的后继是第一个数据结点。所以尾插是插到 head 前面头插是插到 head 后面。这个表述刚接触时确实容易绕我给你一张表把四个关键位置讲清楚。操作语义在循环链表中的真实位置插入后的位置关系头插push_fronthead 的 next 之前新结点成为 head 的下一个即第一个数据结点尾插push_backhead 之前新结点成为 head 的前驱即最后一个数据结点中间插入insert指定前驱 p 之后新结点位于 p 和 p-next 之间删除第一个数据结点删除 head 的 next原第二个数据结点成为 head 的下一个具体实现一个通用的 insert_after 函数它接受前驱结点指针和新值处理所有插入场景NodeT* insert_after(NodeT* p, const T value) { NodeT* newNode new NodeT(value); newNode-next p-next; p-next newNode; size_; return newNode; }插入操作的顺序必须是先连新结点到后继再断旧链接。如果先把 p-next 改成 newNode那原来 p-next 指向的老后继结点就找不到了链表直接断成两截。这个顺序问题写错一次之后就不会再错了因为后果非常明显数据丢失和悬垂指针同时爆炸。头插和尾插都可以用 insert_after 一行搞定关键区别只在于传哪个结点作为前驱。void push_front(const T value) { insert_after(head, value); } void push_back(const T value) { NodeT* tail get_tail(); insert_after(tail, value); } NodeT* get_tail() const { if (empty()) return head; NodeT* p head; while (p-next ! head) { p p-next; } return p; }get_tail 每次尾插都要从头走一遍时间复杂度 O(n)。如果你频繁做尾插操作可以在类里维护一个 tail 指针指向真正的尾结点尾插就变成 O(1)。代价是删除操作可能会改 tail维护成本变高。我个人的建议是如果这个链表主要用来做轮询遍历和头尾插入维护 tail 指针值得如果只是偶尔尾插每次线性找一遍也完全可以接受代码反而更简单。工程上没有绝对最优只有适合当前场景的取舍。2.3 构造、析构与链表判空的边界处理构造函数我已经在类定义里写了初始化哨兵结点让 head 自指size_ 置 0。析构函数必须先 clear 掉所有数据结点再 delete 哨兵。顺序不能反如果一个一个 delete 数据结点时发现 head 已经被释放了循环条件就没了参照物。clear 函数我上面用了一个循环删除的思路只要链表非空就反复删除 head 的下一个结点。这里删除操作 remove_after(head) 会持续更新 head-next所以循环能正确收敛。还有一种写法是手动遍历并用临时变量保存下一个结点void clear() { NodeT* p head-next; while (p ! head) { NodeT* next p-next; delete p; p next; } head-next head; size_ 0; }这种写法更直白遍历每个真实数据结点先保存下一个结点的地址再删除当前结点防止删除后丢失后续链路的访问入口。两种写法都正确我建议理解第一种的循环删除背后逻辑也写得出第二种的显式遍历面试时被问到底层细节不至于卡壳。判空操作 empty() 可以直接判断 size_ 0也可以判断 head-next head。两种方式等价但在头结点中可能存储额外标记数据的扩展场景下size_ 更可靠因为 head 自指只表示没有数据结点如果有结点恰好是 head 自身但 size_ 非零这种非法状态用 size_ 判断能更快暴露问题。这一点我多说一句循环链表没有一个天然为 nullptr 的哨兵来标记终点所以 size_ 这个计数器不是可有可无的优化它是安全性的基础设施。你能快速判断链表是否为空、遍历是否已经完整走了一圈都非常依赖 size_ 的准确性。每次插入和删除都必须同步维护 size_漏掉一行后面任何依赖 size 的判断都会静默出错。3. 删除与查找循环结构下最容易出错的两个操作3.1 删除结点的完整步骤与断链风险删除操作比插入更麻烦因为插入时你只需要一个新结点的指针但删除时你需要同时掌握目标结点和它的前驱。单链表天生只有 next 指针无法从目标结点反推前驱所以删除的通用做法是找前驱删后继。我在类定义里给出的 remove_after 正是这个思路给定任意前驱 p删除 p-next 结点。这是删除操作的最小原语外层函数负责找到合适的前驱。删除的核心步骤是三步用 target 指针指向待删结点 p-next把 p-next 更新为 target-next这一步完成了断链与回连保存数据、delete target、--size_T pop_front() { if (empty()) { throw std::runtime_error(pop_front on empty list); } return remove_after(head); } T pop_back() { if (empty()) { throw std::runtime_error(pop_back on empty list); } NodeT* tail get_tail(); return remove_after(tail); } void erase(const T value) { if (empty()) return; NodeT* p head; while (p-next ! head) { if (p-next-data value) { remove_after(p); return; } p p-next; } }需要注意删除第一个数据结点时p 是 headp-next 是第一个数据结点remove_after(head) 会把 head-next 更新为原来第二个结点。如果链表只有一个数据结点head-next 会被更新为 head链表回到空表自指状态这是完全正确的。删除尾结点时有一个隐蔽的点。get_tail() 返回尾结点也就是 head 的前驱。remove_after(tail) 会删除 tail 的后继而 tail 的后继正是 head。我的 remove_after 里有一个保护判断if (p-next head) throw。这个保护是必须的否则在空表或 p 本身是尾结点时会误删哨兵结点 head导致整个链表结构崩溃。加这个判断是防御性编程的典型例子宁可多一个分支也不让核心结构被意外破坏。3.2 查找操作的循环终止条件查找操作在循环链表里最容易写错的就是循环条件。普通链表找元素时终止条件是 p nullptr循环链表没有 nullptr终止条件变成了 p head 或者 p-next head取决于你遍历的起点和语义。下面这段代码查找第一个匹配 value 的结点返回它的指针。注意循环条件用的是 p 从 head-next 出发绕回到 head 时停止NodeT* find(const T value) { if (empty()) return nullptr; NodeT* p head-next; while (p ! head) { if (p-data value) { return p; } p p-next; } return nullptr; }这段代码的终止逻辑是从第一个数据结点开始依次访问每个结点访问完尾结点后 p 会变成尾结点的 next也就是 head此时循环停止。整个过程中每个数据结点恰好被检查一次不会死循环。但如果把初始条件写成 Node * p head; while (p ! head)一上来就退出了一个结点都查不到。这种错误很经典看起来只是一行之差行为完全不同。还有一种常见的查找变体是从任意结点开始找这在循环链表里意义更特殊。因为链表是环你可以从任何结点出发绕一圈回到自己查找整个环中的所有结点。这种能力是普通链表没有的也是循环链表在轮询调度场景的核心价值所在。// 从 start 开始绕环一圈查找 NodeT* find_from(NodeT* start, const T value) { if (start nullptr || empty()) return nullptr; NodeT* p start; do { if (p-data value) return p; p p-next; } while (p ! start); return nullptr; }这里必须用 do-while 而不是 while道理很直白如果 start 本身就是目标结点while 循环会在检查 start 之前就判断 p ! start 为假直接退出错误地返回 nullptr。do-while 保证先检查当前结点再判断是否走完一圈这才符合从任意结点开始绕环查找的语义。4. 经典应用场景约瑟夫环问题的两种解法对比4.1 为什么约瑟夫环天然适合循环链表约瑟夫环问题Josephus problem是循环链表最经典的配套案例几乎每本数据结构教材里都会出现。问题描述是这样的n 个人围成一圈从某个位置开始报数报到 m 的人出圈然后从下一个人继续报数直到最后只剩一个人求这个人的原始编号。围成一圈、反复遍历、出圈后环自动收拢这三个特征和循环链表完美匹配。数组方案需要维护一个删除标记数组每次报数都要判断哪些位置已经出圈逻辑繁琐普通链表方案在尾部需要手动回头循环条件复杂。循环链表方案最符合直觉把 n 个结点接成环用指针沿 next 移动模拟报数每次走 m-1 步找到出圈结点的前驱用 remove_after 删除它继续重复。int josephus_circular_list(int n, int m) { CircularLinkedListint list; for (int i 1; i n; i) { list.push_back(i); } Nodeint* p list.head; // head 作为起始前驱 while (list.size() 1) { // 走 m-1 步找到出圈结点的前驱 for (int step 0; step m - 1; step) { p p-next; if (p list.head) p p-next; // 跳过头结点 } list.remove_after(p); } return list.head-next-data; }注意代码里的一个细节报数过程中如果指针走到了 head 这个哨兵需要额外跳一步到第一个真实数据结点。因为哨兵不参与报数但它在结构上又是环的一部分这是带头结点的循环链表处理模拟类问题时必须考虑的点。时间复杂度是 O(n*m)因为每次删除都要走 m 步一共删除 n-1 次。当 n 很大而 m 相对较小时这个方案完全够用如果 m 也很大单纯循环链表模拟会慢。4.2 数学递推优化当数据量变大时怎么办约瑟夫环还有一种完全不依赖任何链表的数学解法推导出递推公式后直接 O(n) 求出最终幸存者编号。递推公式是这样的f(1) 0 f(i) (f(i-1) m) % i其中 f(i) 表示 i 个人报数时幸存者的编号从 0 开始计数。最后的结果 f(n) 1 就是原始编号从 1 开始计数的话。int josephus_math(int n, int m) { int survivor 0; for (int i 2; i n; i) { survivor (survivor m) % i; } return survivor 1; }这个公式的原理不细讲核心是倒着推删掉一个人之后剩下的 n-1 个人重新形成环但他们编号整体偏移了 m 个位置。从最终幸存者在 n-1 人环中的位置反推它在 n 人环里的位置就是加上 m 再对 n 取模。这个递推是递归思想的动态规划版本。两种解法怎么选我给你一个明确的建议场景推荐方案理由n、m 都小比如 n 1000循环链表模拟直观、容易验证、方便扩展输出整个出圈序列n 很大比如 n 10^6数学递推O(n) 不可能超时内存 O(1)面试被问到底层原理两种都要会先讲递推公式再补充链表实现展示完整思路工程中需要完整出圈顺序循环链表模拟递推只能算最后一人无法输出中间过程老实说刷题时数学解法是主流因为它快但学习数据结构时循环链表模拟才是理解环形结构如何在移动中自维持的最好方式。两条路都走一遍你对循环链表的理解会上一个台阶。5. 实战中常踩的坑与排查方法5.1 死循环是怎么产生的如何快速定位死循环是循环链表最经典的问题几乎所有写过的人都遇过。举一个我实际遇到过的例子有一次我写一个轮询任务队列每个结点保存一个任务结构一个 worker 线程从队列里取任务循环执行。运行一段时间后程序卡死CPU 占用 100%。用调试器暂停线程发现代码停在了一个 while 循环里那个循环是遍历队列找下一个任务。根因是某个任务结点的 next 指针没有正确回连尾部结点的 next 指向了一个已经被释放的地址整理内存后这个地址恰好指向一个仍在内存中的结点导致遍历永远无法回到 head。排查方法有先后顺序。第一步用调试器暂停线程看当前线程栈停在哪一行如果是遍历循环几乎可以确定是循环终止条件没有满足。第二步检查链表结构从头结点开始手动走 10 步看看是否已经出现明显的重复访问走到了同一个结点或者访问到了非法地址。用 GDB 或者 Visual Studio 的调试器可以直接看链表指针的值。第二步有一个非常有效的辅助手段写一个验证函数 detect_cycle_len它遍历整个环一遍计算实际遍历步数和 size_ 对比。size_t count_nodes() const { size_t count 0; NodeT* p head-next; while (p ! head) { count; p p-next; } return count; }如果 count_nodes() 返回的数值和 size_ 不一致说明链表结构已经损坏可能形成了非预期的小环或者结点被非法删除。如果 count_nodes() 本身死循环不返回说明环中出现了不属于链表的结点或者指针错乱。这个验证函数是定位链表问题的第一个照妖镜。预防死循环的根本方法有三条。第一所有循环遍历的终止条件都基于回到 head而不是 p ! nullptr这听着简单但在大量代码里很容易被习惯性写成 nullptr 判断。第二插入和删除时保证 head-next 的单向一致性尤其是删除后要检查链表是否变成空表自指状态。第三每次修改链表结构后在开发阶段跑一遍 assert用 assert(count_nodes() size_) 强制校验。5.2 空表和单结点边界循环链表有非常多的边界情况取决于链表长度是 0、1、2 还是更多。一个常规长度的逻辑在长度为 1 时往往就崩溃了。比如 find 操作链表只有一个数据结点时的遍历路径是head - node1 - head。如果条件判断出问题可能永远访问 node1死循环。再比如 erase 删除唯一一个数据结点之后链表必须回到 head 自指状态如果代码里只是把 head-next 更新为 nullptr那后续所有操作都会把 nullptr 当结点解引用直接段错误。应对思路是边界意识每次写完一个操作函数先手动走一遍 size 0、size 1、size 2 三个最小规模。这不是 PPT 上的方法论是调试器的实际操作。对于循环链表来说空表和单结点是最容易写出隐蔽 bug 的地方因为它们在逻辑上引入了环的退化为点和环的消失两种特殊形态。我建议在类里显式维护一个 invariant 校验函数在每次插入、删除后调用开发期开启发布期关闭void check_invariant() const { if (size_ 0) { assert(head-next head); } else { assert(head-next ! head); size_t node_count 0; NodeT* p head-next; while (p ! head) { node_count; p p-next; assert(node_count size_); // 防止死循环 } assert(node_count size_); } }这个函数本质上用 assert 把循环链表的环完整性和 size_ 的一致性绑定住了。开发阶段开着它很多 bug 在出现症状前就会暴露发布时 NDEBUG 会把它自动去掉不影响性能。5.3 几个实用的调试技巧调试循环链表有个天然的不便之处普通链表遍历到 nullptr 就自然结束调试器显示链表内容时能明确看到终点循环链表在调试器里展开指针链时会无限展开下去或者干脆因为循环引用显示混乱。这里分享三个我实际用着顺手的技巧。第一个技巧是把自定义格式化器用起来。Visual Studio 的 natvis、GDB 的 pretty-printer、LLDB 的 data formatter 都可以为自定义类型写展示规则。比如给循环链表写一个 natvis让调试器只显示前若干个结点并在最后标记一个back to head这样调试窗口里就不再是混乱的指针循环了。Type NameCircularLinkedListlt;*gt; DisplayString{{ size {size_} }}/DisplayString Expand Item Name[size]size_/Item LinkedListItems Sizesize_/Size HeadPointerhead-next/HeadPointer NextPointernext/NextPointer /LinkedListItems /Expand /Typenatvis 里的 LinkedListItems 专门为链表结构设计它知道怎么处理循环链表只显示 size_ 个元素不会死循环。这是现代调试器给链表调试提供的贴心功能很多人没用起来实在可惜。第二个技巧是画指针状态图。在纸上或者在白板软件里画出 head、tail、每个结点的 next 指向然后一步步演算插入和删除过程。这个办法听起来原始但排查复杂指针问题时比盯着一堆十六进制地址高效得多。我自己在接手老项目里那些指针绕来绕去的代码时一定是先画图再动手。第三个技巧是用一个哨兵式的空结点来观察环的完整性。当你在调试器里看到一个指针的值想知道它是不是 head可以把它和 head 的地址比较。如果频繁需要这种比较可以在类里加一个调试用的成员方法bool is_head(const NodeT* p) const { return p head; }然后在这个函数上打一个条件断点每当 p 等于 head 时触发。这样就能在遍历过程中精确定位我们回到了起点的时刻观察当时的链表状态。这些技巧补充一句调试工具的能力上限其实很高很多人只停留在 F10 单步和加 watch 的水平。真正复杂的问题往往需要你综合用上类型格式化器、条件断点、自定义校验函数这些手段才能把隐藏的指针问题一举揪出来。6. 从单链表到双向循环链表一个自然的扩展单向循环链表已经能覆盖很多场景但如果你做的是一个需要在两个方向轮转的系统比如浏览器标签页的前后切换、播放列表的上下一首、双端轮询调度器那双向循环链表会更顺手。双向版本在原来的基础上增加了一个 prev 指针头结点的 prev 指向尾结点尾结点的 next 指向头结点形成一个双向闭合环。结点定义相应变成template typename T struct DoublyNode { T data; DoublyNodeT* prev; DoublyNodeT* next; explicit DoublyNode(const T value) : data(value), prev(nullptr), next(nullptr) {} };插入和删除的逻辑因为有了 prev变得更对称。插入时新结点同时连接前驱的 next 和后继的 prev需要四步赋值比单链表多两步但换来的是删除任意已知结点时不再需要找前驱直接通过 target-prev 就能拿到前驱指针。这在需要频繁删除任意结点的场景里是质的提升。真正体现双向循环链表优势的操作是反向遍历。播放列表里上一首的操作需要拿到当前结点的前驱如果只用单向循环链表你就得从头绕一圈才能找到上一个结点时间复杂度 O(n)双向循环链表直接走 prev 一步到位 O(1)。如果你的应用里两个方向切换的频率很高这个复杂度节省非常明显。从单向循环链表到双向循环链表不只是加一个指针那么简单。它意味着你必须时刻维护两组一致性结点的 next 构成了一个环结点的 prev 也必须构成同一个环的反向版本。任何一次插入和删除你都要同时修复 next 和 prev 两条链路漏掉任何一条链表就变成半环半断的畸形结构调试起来比单向版本更头疼。我的建议是先把单向循环链表搞透尤其是插入、删除、遍历的边界逻辑然后拿双向版本练手对比它们在不同操作上的时间复杂度差异。数据结构的核心能力从来不在背代码而在理解每一种结构都对应一种权衡——循环链表消除了尾部回头的分支代价是你必须手动管理终止条件双向版本消除了反向遍历的开销代价是每个结点额外占用一个指针的内存以及维护双链路的心智负担。想清楚你手头的场景到底需要哪种能力再下手实现这才是工程判断力。
