循环链表

循环链表（Circular Linked List）是链表的一种特殊形式，其最后一个节点的指针不再指向空值（`NULL`），而是指向链表的头节点（或第一个节点），从而形成一个闭环。这种结构在需要周期性操作或环形遍历的场景中非常有用。

基本概念

循环链表分为两种主要类型： 1. 单向循环链表：每个节点包含数据域和指向下一个节点的指针，尾节点指向头节点。 2. 双向循环链表：每个节点包含数据域、前驱指针和后继指针，尾节点的后继指针指向头节点，头节点的前驱指针指向尾节点。

与普通链表的区别

• 普通链表的尾节点指向`NULL`，而循环链表的尾节点指向头节点。
• 遍历时需要额外注意终止条件，避免无限循环。

实现示例

以下是使用Python实现的单向循环链表：

  
class Node:  
    def __init__(self, data):  
        self.data = data  
        self.next = None  

class CircularLinkedList:  
    def __init__(self):  
        self.head = None  

    def append(self, data):  
        new_node = Node(data)  
        if not self.head:  
            self.head = new_node  
            new_node.next = self.head  
        else:  
            temp = self.head  
            while temp.next != self.head:  
                temp = temp.next  
            temp.next = new_node  
            new_node.next = self.head  

    def display(self):  
        if not self.head:  
            print("List is empty")  
            return  
        temp = self.head  
        while True:  
            print(temp.data, end=" -> ")  
            temp = temp.next  
            if temp == self.head:  
                break  
        print("HEAD")  

# 示例用法  
clist = CircularLinkedList()  
clist.append(1)  
clist.append(2)  
clist.append(3)  
clist.display()

输出：

  
1 -> 2 -> 3 -> HEAD  

实际应用场景

循环链表的典型应用包括： 1. 操作系统调度：时间片轮转调度算法中，任务队列常使用循环链表实现。 2. 游戏开发：循环遍历角色或道具列表（如“大富翁”中的玩家轮流机制）。 3. 数据缓冲区：音频/视频流处理中环形缓冲区的实现。

复杂度分析

时间复杂度对比

操作	普通链表	循环链表
插入/删除（头部）	O(1)	O(1)
插入/删除（尾部）	O(n)	O(n)
遍历	O(n)	O(n)

进阶操作

约瑟夫问题（Josephus Problem）

循环链表可高效解决经典约瑟夫问题：

  
def josephus(n, k):  
    clist = CircularLinkedList()  
    for i in range(1, n+1):  
        clist.append(i)  
    current = clist.head  
    while current.next != current:  
        for _ in range(k-2):  # 移动k-1步  
            current = current.next  
        print(f"Eliminated: {current.next.data}")  
        current.next = current.next.next  
        current = current.next  
    print(f"Survivor: {current.data}")  

josephus(5, 2)  # 示例：5个人，每第2个淘汰

输出：

  
Eliminated: 2  
Eliminated: 4  
Eliminated: 1  
Eliminated: 5  
Survivor: 3  

可视化结构

graph LR A[Head] --> B[Node 1] B --> C[Node 2] C --> D[Node 3] D --> A

数学表达

循环链表的长度计算与普通链表相同，但遍历条件需满足： $\mathrm{\exists }n\in \mathbb{\mathbb{N}}\text{使得}{\text{node}}_{n+1}={\text{node}}_1$

注意事项

• 避免内存泄漏：删除节点时需正确更新指针。
• 终止条件：遍历时需检查是否回到起始点（如`while temp != self.head`）。

总结

循环链表通过闭合环路简化了环形数据的处理，适合需要循环访问的场景。掌握其实现与边界条件处理是算法设计中的重要技能。