数据结构：循环链表（Circular Linked List）

目录

定义循环链表

分类：单向 vs 双向循环链表

 遍历输出（Display）一个单向循环链表

🔍 我们怎么知道“走完一圈”？

为什么必须用 do...while？

一步步构建完整 Display 函数

如何用递归方式遍历

普通链表的问题是什么？

普通单链表的结尾是 NULL：

A -> B -> C -> NULL

这个 NULL 结尾的本质是：

• 线性结构终止

• 不支持循环访问（例如“转一圈回来再处理”）

于是我们提出问题：如果不想让链表“终止”怎么办？

如何改进？引入循环结构

我们观察到一个物理现象：环形结构不会终止。

比如：

• 时钟的表盘：12小时后回到起点

• 操作系统的轮转调度：任务一个接一个重复执行

类比这个结构到链表：

如果把最后一个节点的 next 指针不指向 NULL，而是指回头结点，那么链表将变成一个首尾相连的结构。

这个结构就是：

A -> B -> C -+
^            |
|____________|

我们称之为：循环链表（Circular Linked List）

定义循环链表

循环链表是一种链表，其中链表的最后一个节点指向头结点或之前的某一结点，而不是 NULL。

从结构上看，它使得链表成为一个环形结构，即可以从任何一个节点开始，不断访问 next，最终一定会回到起点。

分类：单向 vs 双向循环链表

循环链表有两种基本形式，对应指针的数量：

1. 单向循环链表（Singly Circular Linked List）

• 每个节点只有一个 next 指针

• 最后一个节点的 next 指向头结点

• 没有前向指针

结构示意：

A -> B -> C -> A (head)

• 节点数 N，访问 N 次 next 一定回到起点

• 不支持反向访问

• 节点访问是 O(n)

2. 双向循环链表（Doubly Circular Linked List）

• 每个节点有 next 和 prev 两个指针

• 最后一个节点的 next 指向头结点

• 第一个节点的 prev 指向尾节点

结构示意：

<-> A <-> B <-> C <->
       ^         |
       |_________|

• 可以从任意节点出发双向访问

• 更适合双向遍历、删除操作

• 空间复杂度略高（双指针）

 遍历输出（Display）一个单向循环链表

从根源提问：什么叫 遍历输出？

在数据结构中， 遍历输出通常指的是：

沿着链表的结构，把每个节点的 data 值访问并输出，按顺序完成一次全遍历

这听起来和普通链表遍历没有区别 —— 但我们现在面对的，是循环链表。

⚠️ 循环链表有一个根本性的不同：它没有终点 NULL

所以如果你写：

while (temp != NULL) {
    ...
}

 它永远不会结束，因为 temp 最后会回到头，不会变成 NULL。

🔍 我们怎么知道“走完一圈”？

这是我们真正的问题本质：

循环链表不能通过 “走到 NULL” 判断终止，必须通过 “回到起点” 判断终止

也就是说：

• 我们从头结点 head 出发

• 每次走到下一个节点

• 当我们再次访问到 head 节点时，说明走了一圈

所以终止条件应该变成：

temp == head

但这里还有一个隐藏的陷阱

如果你直接写：

Node* temp = head;
while (temp != head) {
    printf("%d ", temp->data);
    temp = temp->next;
}

这段代码一行都不会执行！

为什么？

因为你在 while 条件中写的是 temp != head，但你一开始就让 temp = head，它一开始就跳出了循环。

所以——我们就引出了一个根本的程序设计原则：

为什么必须用 do...while？

让我们分析：

• 你一定要打印第一个节点

• 然后继续往后走

• 每打印一个，判断是否已经回到起点

C语言提供的这种结构是：

do {
    // 操作
} while (条件);

这就非常适合循环链表的 遍历输出操作：

1. 保证了至少访问一次

2. 每次访问之后判断是否回到起点

一步步构建完整 Display 函数

第一步：处理空链表情况

if (head == NULL) return;

 如果链表为空，没有节点，自然就没有东西可打印。

第二步：从头节点开始遍历

Node* temp = head;

我们定义一个指针变量 temp，初始指向头结点。

第三步：do...while 循环开始

do {
    printf("%d ", temp->data);
    temp = temp->next;
} while (temp != head);

这几行的含义逐条解释：

printf("%d ", temp->data);

• 访问当前节点的数据

• 输出到终端（或控制台）

temp = temp->next;

• 向后移动一个节点

while (temp != head);

• 如果移动后还没回到头结点，继续循环

• 否则说明遍历结束，退出

特殊情况验证

情况1：空链表

• head == NULL，直接 return，不执行任何操作 

情况2：只有一个节点

• head->next == head

• 第一次 printf 输出 data

• temp = temp->next 还是 head

• while(temp != head) 不成立，循环退出 

情况3：多个节点

• 每个节点依次访问，直到再次访问到 head，退出 

完整代码

void display(Node* head) {
    if (head == NULL) {
        // 链表为空，不需要输出
        return;
    }

    Node* temp = head;

    do {
        // 访问并打印当前节点数据
        printf("%d ", temp->data);
        // 移动到下一个节点
        temp = temp->next;
    } while (temp != head);

    // 最后换行，保持输出整洁
    printf("\n");
}

如何用递归方式遍历

问题核心：递归能不能替代 do...while 实现遍历？

我们已经知道，循环链表 traversal（遍历）不能靠 while (temp != NULL)，因为它没有 NULL。

但现在问题来了：

如果我们想用 递归 来遍历，如何判断“已经回到起点”？如何防止无限递归？

递归的本质是：

一个函数调用自己，每次解决更小的子问题，直到满足终止条件为止

用更数学的语言：

• 递归 = 拆解问题 + 基本情况终止 + 递归调用

所以我们要做的，其实就是：

1. 定义一个递归函数 void display_recursive(Node* current)

2. 每次访问当前节点，然后递归访问 current->next

3. 找到合理的终止条件，避免死循环

循环链表中的致命问题：没有 NULL！

在普通链表中我们可以这么写递归：

void display(Node* current) {
    if (current == NULL) return;
    printf("%d ", current->data);
    display(current->next);
}

但循环链表没有 NULL 作为终点 —— 所以你会：

• 从 A 打印到 B，再到 C，然后又回到 A，然后无限递归……💥栈溢出

💡第一性解法：引入“哨兵节点”参数，记住起点

核心思想：

我们不能在递归中只传 current，还要传 head（或者初始起点），用来判断是否“回到了起点”。

于是我们重构递归函数的参数结构：

void display_recursive(Node* current, Node* head);

现在我们的策略是：

• 第一次调用：display_recursive(head, head);

• 每次访问并打印 current->data

• 递归调用：display_recursive(current->next, head);

• 当 current->next == head，说明下一次将要回到起点，于是：

  • 先打印 current

  • 然后不再递归（否则会无限循环）

第一性验证边界情况

情况1：空链表

• head == NULL，不会进入递归 

情况2：只有一个节点

• head->next == head

• 直接满足 current->next == head，打印一次后终止 

我们现在拆分写出逻辑：

第一步：终止条件

if (current->next == head) {
    // 当前是最后一个节点（下一个是起点）
    printf("%d ", current->data);
    return;
}

第二步：正常情况递归

printf("%d ", current->data);
display_recursive(current->next, head);

第三步：完整组合

void display_recursive(Node* current, Node* head) {
    if (current == NULL) return; // 空链表处理

    if (current->next == head) {
        printf("%d ", current->data); // 最后一个节点
        return;
    }

    printf("%d ", current->data);
    display_recursive(current->next, head);
}

 完整示意结构图

假设链表是：10 -> 20 -> 30 -> (回到10)

递归调用过程如下：

display(10, 10)
|
|-- printf(10)
|-- display(20, 10)
    |
    |-- printf(20)
    |-- display(30, 10)
        |
        |-- current->next == head
        |-- printf(30)
        |-- return