循环链表（Circular Linked List） 一、什么是循环链表 循环链表是一种特殊的单链表，其尾节点的 Next 指针不指向 nil，而是回指到头节点，从而形成一个闭合的环。 普通单链表的遍历走到尾节点就结束了（node.Next == nil），而循环链表没有天然的"终点"——如果你不停下来，可以无限遍历下去。 普通单链表: A -> B -> C -> D -> nil 循环链表: A -> B -> C -> D -> A (D 的 Next 指回 A) ^ | |______________________| 1.1 循环链表 vs 单链表 对比维度 单链表 循环链表 尾节点指向 nil 头节点 遍历终止条件 cur == nil cur.Next == head 从任意节点可达性 只能向后走，无法回到起点 可以绕一圈回到起点 环形结构 无 有 适用场景 线性序列 轮询调度、约瑟夫环、资源循环分配 1.2 循环链表的变种 单循环链表：只有 Next 指针，尾指回头 双循环链表：有 Prev 和 Next 两个指针，尾的 Next 指头，头的 Prev 指尾 双循环链表在 Go 的 container/ring 标准库中就有实现。 二、Go 实现：单循环链表 2.1 节点定义与基本结构 package main import "fmt" // Node 循环链表节点 type Node struct { Data int Next *Node } // CircularList 循环链表 type CircularList struct { Head *Node Size int } 2.2 尾部插入 往循环链表尾部添加节点，核心步骤： 新建节点 如果链表为空，新节点自己指向自己，并设为 Head 如果链表非空，找到尾节点（tail.Next == head 的那个），让尾节点指向新节点，新节点指向头节点 // Append 在尾部插入节点 func (cl *CircularList) Append(data int) { newNode := &Node{Data: data} if cl.Head == nil { cl.Head = newNode newNode.Next = newNode // 自己指向自己，形成环 } else { // 找到尾节点（Next 指向 Head 的就是尾） tail := cl.Head for tail.Next != cl tail.Next = newNode newNode.Next = cl.Head } cl.Size++ } 2.3 头部插入 头部插入需要将新节点插在 Head 之前，然后把 Head 指向新节点。但有个容易遗漏的点：尾节点的 Next 也需要更新指向新的 Head。 // Prepend 在头部插入节点 func (cl *CircularList) Prepend(data int) { newNode := &Node{Data: data} if cl.Head == nil { cl.Head = newNode newNode.Next = newNode } else { // 找尾节点 tail := cl.Head for tail.Next != cl // 新节点插在 head 前面 newNode.Next = cl.Head tail.Next = newNode cl.Head = newNode } cl.Size++ } 2.4 删除节点 删除指定值的节点，需要维护环的闭合性。关键在于： 如果删除的是 Head，需要把 Head 移到下一个节点，同时尾节点也要更新指向新 Head 如果删除的是中间节点，只需前驱节点跳过它 // Remove 删除第一个匹配的节点 func (cl *CircularList) Remove(data int) bool { if cl.Head == nil { return false } // 只有一个节点的情况 if cl.Head.Next == cl return false } // 查找目标节点及其前驱 prev := cl.Head cur := cl.Head.Next for cur != cl prev = cur cur = cur.Next } // 检查 Head 是否是目标 if cl.Head.Data == data { // 找到尾节点，让尾指向 Head.Next tail := cl.Head for tail.Next != cl tail.Next = cl.Head.Next cl.Head = cl.Head.Next cl.Size-- return true } return false } 2.5 遍历 循环链表的遍历不能像单链表那样 for cur != nil，否则会死循环。正确的做法是：从 Head 出发，走一圈回到 Head 就停。 // Traverse 遍历打印所有节点 func (cl *CircularList) Traverse() { if cl.Head == nil { fmt.Println("空链表") return } cur := cl.Head for { fmt.Printf("%d", cur.Data) cur = cur.Next if cur == cl fmt.Print(" -> ") } fmt.Println(" (回到头部)") } 2.6 完整测试 func main() { cl := &CircularList{} // 尾部插入 cl.Append(10) cl.Append(20) cl.Append(30) fmt.Print("Append 10,20,30: ") cl.Traverse() // 10 -> 20 -> 30 (回到头部) // 头部插入 cl.Prepend(5) fmt.Print("Prepend 5: ") cl.Traverse() // 5 -> 10 -> 20 -> 30 (回到头部) // 删除中间节点 cl.Remove(20) fmt.Print("Remove 20: ") cl.Traverse() // 5 -> 10 -> 30 (回到头部) // 删除头节点 cl.Remove(5) fmt.Print("Remove 5 (head): ") cl.Traverse() // 10 -> 30 (回到头部) // 验证环形结构 fmt.Printf("Size: %d\n", cl.Size) // 2 // 验证尾节点指向头 tail := cl.Head for tail.Next != cl fmt.Printf("Head=%d, Tail=%d, Tail.Next=%d (应等于Head)\n", cl.Head.Data, tail.Data, tail.Next.Data) } 运行结果： Append 10,20,30: 10 -> 20 -> 30 (回到头部) Prepend 5: 5 -> 10 -> 20 -> 30 (回到头部) Remove 20: 5 -> 10 -> 30 (回到头部) Remove 5 (head): 10 -> 30 (回到头部) Size: 2 Head=10, Tail=30, Tail.Next=10 (应等于Head) 三、Go 标准库 container/ring Go 标准库提供了 container/ring，这是一个双循环链表的实现。它的所有节点值都是 interface{} 类型。 package main import ( "container/ring" "fmt" ) func main() { // 创建一个长度为 5 的环 r := ring.New(5) // 填充数据 i := 0 r.Do(func(v interface{}) { r.Value = i * 10 i++ r = r.Next() }) // 遍历（手动） r.Do(func(v interface{}) { fmt.Printf("%d ", v) }) fmt.Println() // 输出: 0 10 20 30 40 // 移动指针 r = r.Move(2) // 向前移动2步 fmt.Printf("移动2步后当前值: %d\n", r.Value) // 20 // 链接（跳过中间节点） r.Link(ring.New(1)) } container/ring 的核心方法： New(n) — 创建 n 个节点的环 Next() / Prev() — 前进/后退一步 Move(n) — 移动 n 步（可为负数） Link(s) — 将另一个环链接进来 Unlink(n) — 移除 n 个节点 Do(f) — 对环中每个节点执行函数 f Len() — 返回环长度 四、循环链表的应用场景 轮询调度（Round Robin）：操作系统进程调度中，所有就绪进程排成环，调度器循环分配 CPU 时间片 约瑟夫环问题：经典的数学问题，N 人围坐报数出列 资源池管理：数据库连接池、线程池中的资源循环分配 音乐播放器：单曲循环、列表循环播放模式 游戏中的回合制：玩家轮流操作，一圈接一圈 心跳检测：分布式系统中节点间的周期性健康检查 五、复杂度分析 操作 时间复杂度 说明 头部插入 O(1) 但需要更新尾节点指向，找尾 O(n) 尾部插入 O(n) 需要遍历找到尾节点（除非维护尾指针） 头部删除 O(n) 同样需要找尾节点更新 查找 O(n) 最坏遍历整个环 遍历 O(n) 一圈正好 n 个节点 优化技巧：如果维护一个 tail 指针，尾部插入可以做到 O(1)。container/ring 的 Next()/Prev() 都是 O(1) 的，因为它本质是双循环链表。 六、小结 循环链表的核心思想是将线性结构首尾相连变成环形结构，从而消除了"终点"的概念。它在需要循环处理、轮转调度的场景中非常自然。Go 标准库的 container/ring 提供了开箱即用的双循环链表实现，实际开发中应优先使用标准库而非自己造轮子——但理解底层原理对于面试和算法学习仍然重要。 与单链表相比，循环链表最大的陷阱在于遍历终止条件：绝不能用 cur != nil，否则会死循环；正确的条件是 cur.Next == head（回到起点即停）。