循环链表

数据结构：循环链表 (Circular Linked List)

Abstract: 核心概念 循环链表是链表的一种变体。它的核心特点是：链表中最后一个节点的 next 指针不再指向 NULL，而是指向链表的头节点（Head），从而形成一个闭环。

1. 结构图解

与普通单链表相比，循环链表没有明显的“尽头”。从链表中的任何一个节点出发，都可以遍历到整个链表的所有节点。

graph LR
     循环回指的指针
    N3 -.->|next 指针绕回| H
    
    linkStyle 3 stroke:#ff1744,stroke-width:2px,stroke-dasharray: 5 5;

---

2. 核心代码实现 (C语言)

数据结构定义

循环链表的节点定义与普通单链表完全相同：

#include <stdio.h>
#include <stdlib.h>

// 定义节点结构体
typedef struct Node {
    int data;           // 数据域
    struct Node *next;  // 指针域
} Node;

初始化

关键在于：当链表为空（仅有头节点）时，头节点的 next 必须指向它自己，而不是 NULL。

Node* initCircularList() {
    Node* head = (Node*)malloc(sizeof(Node));
    if (head <mark> NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    head->next = head; // 重点：指向自身形成环
    return head;
}

遍历操作

在普通单链表中，判断遍历结束的条件是 curr != NULL。但在循环链表中，遍历结束的条件是 当前指针又回到了头节点。

void printList(Node* head) {
    if (head </mark> NULL || head->next <mark> head) {
        printf("链表为空\n");
        return;
    }
    
    Node* curr = head->next; // 跳过头节点，从第一个实际数据节点开始
    
    // 重点：结束条件是 curr 回到了 head
    while (curr != head) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf(" (回到 Head)\n");
}

---

3. 循环链表 vs 普通单链表

对比维度	普通单链表	单向循环链表
尾节点指针	指向 NULL	指向头节点 head
遍历结束条件	curr </mark> NULL 或 curr->next <mark> NULL	curr </mark> head 或 curr->next == head
遍历起始限制	只能从头节点开始遍历	可以从 任意节点 出发遍历整个链表
查找前驱节点	时间复杂度为 O(n) ，且极度不便	时间复杂度仍为 O(n) ，但顺着环总能找到

Tip: 尾指针的妙用

在实际工程中，有时我们只保存指向尾节点（Tail）的指针，而不保存头节点。

为什么？因为有了尾指针，查找尾节点的时间复杂度是 O(1) ；而通过 tail->next 找到头节点的时间复杂度也是 O(1) 。这在需要在链表头部和尾部频繁插入/删除的场景下效率极高。

---

4. 经典应用场景

循环链表非常适合处理**“具有周期性、环形结构”**的业务逻辑：

1. 约瑟夫环问题 (Josephus Problem)：经典的算法题，一群人围成一圈报数，报到某个数的人出列，求最后剩下的人。

2. 操作系统的调度算法：例如 时间片轮转调度 (Round-Robin)，CPU 按顺序给每个进程分配时间片，执行到末尾后又回到第一个进程。

3. 多人回合制游戏：玩家排成一个圈，轮流操作（如大富翁、UNO）。

---

🏷️ Tags: #数据结构 #链表 #C语言 #算法