你还在用头指针遍历整个链表来尾部插入吗？加上一个尾指针，时间复杂度从 O(n) 直接降到 O(1)！
今天我们来聊一个链表中的“小优化大智慧”——单向循环链表配合尾指针。别看只是多存了一个指针，它能让尾部插入、头部删除、链表拼接等操作变得异常高效。
一、什么是单向循环链表？
单向循环链表：在普通单向链表的基础上，将最后一个节点的next指针指向头节点（而不是None），形成一个闭环。
尾指针：除了传统的head指针外，再维护一个tail指针，始终指向链表的最后一个节点。
为什么加尾指针？
- 没有尾指针时，要在尾部插入新节点，需要从头遍历到尾部，O(n)。
- 有了尾指针，直接
tail.next = new_node，然后更新tail，O(1)。
二、结构图示
普通单向链表（带头指针）
head → [A] → [B] → [C] → None尾部插入需要遍历到C才能操作。
单向循环链表（带尾指针）
head → [A] → [B] → [C] ──┐ ↑ │ └────────────┘ tail ────────────────────┘tail.next指向head，形成环。- 插入、删除时，同时维护
head和tail。
三、插入操作详解（带尾指针）
1. 头部插入（在第一个节点之前）
步骤：
- 创建新节点
new_node。 new_node.next = head（新节点指向原头节点）。tail.next = new_node（尾节点的 next 指向新头）。head = new_node（更新头指针）。
时间复杂度：O(1)
图示：
原链表：head → [A] → [B] → [C] ─┐ tail ────────────────────┘ 插入 new 到头部后： head → [new] → [A] → [B] → [C] ─┐ tail ────────────────────┘2. 尾部插入（在最后一个节点之后）
步骤：
- 创建新节点
new_node。 new_node.next = head（新节点指向头，保持循环）。tail.next = new_node（原尾节点指向新节点）。tail = new_node（更新尾指针）。
时间复杂度：O(1) —— 因为直接通过tail定位。
图示：
原链表：head → [A] → [B] → [C] ─┐ tail ────────────────────┘ 插入 new 到尾部： head → [A] → [B] → [C] → [new] ─┐ tail ────────────────────┘3. 中间插入（已知某节点之后）
与普通单向链表一样，需要先找到插入位置的前驱节点（O(n)），然后修改指针，并注意如果插入位置是尾部，需要更新tail。
四、删除操作详解（带尾指针）
1. 删除头节点
步骤：
- 如果链表只有一个节点：
head == tail，则删除后链表为空，设置head = tail = None。 - 否则：
head = head.next（移动头指针）。tail.next = head（保持循环）。
时间复杂度：O(1)
图示：
删除前：head → [A] → [B] → [C] ─┐ tail ────────────────────┘ 删除后：head → [B] → [C] ─┐ tail ─────────────┘2. 删除尾节点
关键：删除尾节点需要找到它的前驱节点（倒数第二个节点），因为单链表无法直接获取前驱。所以即使有tail指针，删除尾节点仍需要遍历到倒数第二个节点，时间复杂度 O(n)。
步骤：
- 从
head开始遍历，找到节点prev使得prev.next == tail。 prev.next = head（跳过尾节点，指向头）。tail = prev（更新尾指针）。- 如果链表只有一个节点，则删除后置空。
时间复杂度：O(n)
特殊优化：如果经常需要删除尾节点，可以考虑使用双向循环链表，那样可以 O(1) 删除尾部。
3. 删除中间节点
需要先找到前驱节点（O(n)），然后prev.next = curr.next。注意如果删除的是最后一个节点（即curr == tail），需要更新tail为prev。
五、时间复杂度总结表
| 操作 | 单向循环链表（带尾指针） | 普通单向链表（仅头指针） |
|---|---|---|
| 头部插入 | O(1) | O(1) |
| 尾部插入 | O(1) | O(n) |
| 中间插入（已知前驱） | O(1) | O(1) |
| 头部删除 | O(1) | O(1) |
| 尾部删除 | O(n) | O(n)（需遍历到倒数第二） |
| 中间删除（已知前驱） | O(1) | O(1) |
| 查找元素 | O(n) | O(n) |
结论：尾指针主要优化了尾部插入操作，从 O(n) 降为 O(1)。
六、Python 实现（带详细注释）
classNode:def__init__(self,val):self.val=val self.next=NoneclassCircularLinkedList:def__init__(self):self.head=None# 头指针self.tail=None# 尾指针defis_empty(self):returnself.headisNone# 头部插入definsert_at_head(self,val):new_node=Node(val)ifself.is_empty():self.head=new_node self.tail=new_node new_node.next=new_node# 指向自己，形成循环else:new_node.next=self.head self.tail.next=new_node self.head=new_node# 尾部插入（O(1)）definsert_at_tail(self,val):new_node=Node(val)ifself.is_empty():self.head=new_node self.tail=new_node new_node.next=new_nodeelse:new_node.next=self.head self.tail.next=new_node self.tail=new_node# 删除头节点defdelete_head(self):ifself.is_empty():returnNoneremoved_val=self.head.valifself.head==self.tail:# 只有一个节点self.head=Noneself.tail=Noneelse:self.head=self.head.nextself.tail.next=self.headreturnremoved_val# 删除尾节点（需要遍历，O(n)）defdelete_tail(self):ifself.is_empty():returnNoneremoved_val=self.tail.valifself.head==self.tail:# 只有一个节点self.head=Noneself.tail=Nonereturnremoved_val# 找到倒数第二个节点curr=self.headwhilecurr.next!=self.tail:curr=curr.next# curr 现在是倒数第二个节点curr.next=self.head self.tail=currreturnremoved_val# 删除第一个值为 val 的节点defdelete_by_value(self,val):ifself.is_empty():returnFalse# 如果头节点就是要删除的ifself.head.val==val:self.delete_head()returnTrue# 遍历查找prev=self.head curr=self.head.nextwhilecurr!=self.head:ifcurr.val==val:prev.next=curr.nextifcurr==self.tail:# 删除的是尾节点self.tail=prevreturnTrueprev=curr curr=curr.nextreturnFalse# 遍历打印（从 head 开始，绕一圈）defdisplay(self):ifself.is_empty():print("空链表")returnresult=[]curr=self.headwhileTrue:result.append(str(curr.val))curr=curr.nextifcurr==self.head:breakprint(" -> ".join(result)+" -> (回到头)")# 测试if__name__=="__main__":cll=CircularLinkedList()cll.insert_at_tail(10)cll.insert_at_tail(20)cll.insert_at_head(5)cll.display()# 5 -> 10 -> 20 -> (回到头)cll.delete_head()cll.display()# 10 -> 20 -> (回到头)cll.insert_at_tail(30)cll.display()# 10 -> 20 -> 30 -> (回到头)cll.delete_tail()cll.display()# 10 -> 20 -> (回到头)cll.delete_by_value(20)cll.display()# 10 -> (回到头)七、图解辅助理解（ASCII 艺术）
插入尾部（带尾指针）
初始状态（只有一个节点 5）： head ──→ [5] ←── tail ↑ │ └─┘ 插入 10 到尾部： head ──→ [5] → [10] ←── tail ↑ │ └───────────┘尾指针直接让5.next = 10，10.next = head，tail = 10，一步到位。
删除尾部
删除前： head ──→ [5] → [10] → [20] ←── tail ↑ │ └─────────────────┘ 删除尾节点 20： 需要找到前驱节点 10： head ──→ [5] → [10] ←── tail ↑ │ └────────┘10.next = head，tail = 10。
八、实际应用场景
- 约瑟夫环问题：循环链表天然适合模拟围成一圈的人。
- 操作系统进程调度：时间片轮转调度算法中，就绪队列常用循环链表。
- 缓冲池/对象池：需要循环利用固定数量资源时。
- 游戏开发中的回合制战斗：角色按顺序行动，循环链表可轻松实现。
九、总结
- 单向循环链表 + 尾指针的核心优势是尾部插入 O(1)。
- 头部插入/删除、尾部插入都是 O(1)，但尾部删除仍然是 O(n)。
- 空间上只多了一个指针，换来了尾部操作的高效。
- 适合需要频繁在尾部添加元素的场景（如消息队列、日志收集）。
思考题：如果既要尾部插入 O(1)，又要尾部删除 O(1)，应该使用什么数据结构？
（提示：双向循环链表，或者用 Python 的collections.deque）
如果觉得有用，欢迎点赞、收藏、转发～
下期我们讲“双向循环链表的实现与应用”，敬请期待！
