C / C++ / 系统课时

循环链表怎样判断遍历结束

循环链表怎样判断遍历结束

普通链表可以靠遇到 NULL 结束遍历,但循环链表的尾节点会重新指向头节点,因此永远不会自然走到空指针。本节用一个可运行的 C 示例说明如何识别“回到起点”,并避开死循环和漏访问尾节点这两个常见错误。

学习目标

  • 理解循环链表为什么不能用 NULL 作为正常遍历的结束条件
  • 掌握从头节点出发并以“再次回到头节点”为结束条件的写法
  • 能处理空链表、单节点循环链表以及多节点循环链表

循环结构改变了结束标志

普通单链表的最后一个节点通常满足 tail->next == NULL,所以指针不断后移后,最终会变成 NULL。循环链表则把尾节点的 next 指回头节点,形成一个闭环。

普通链表与循环链表的遍历结束条件对比

因此,如果仍然写 while (p != NULL),只要链表结构没有损坏,p 就会在这些节点之间不断循环,程序无法正常退出。循环链表需要把“访问了一整圈”作为结束依据,而不是等待空指针出现。

用回到头节点判断一整圈结束

最直接的策略是保存头指针 head。第一次访问 head 后不断执行 p = p->next,当 p 再次等于 head 时,说明所有节点已经访问一遍。

由于第一次检查条件时 p 本来就等于 head,这里很适合使用 do...while:先处理当前节点,再判断移动后的指针是否回到起点。

下面程序构造一个包含三个节点的循环链表,并完整遍历一圈:

c
#include <stdio.h>

typedef struct Node {
    int value;
    struct Node *next;
} Node;

void print_cycle(Node *head) {
    if (head == NULL) {
        return;
    }

    Node *p = head;
    do {
        printf("%d ", p->value);
        p = p->next;  // 每次访问后再向前移动
    } while (p != head);  // 再次回到起点时结束

    printf("\n");
}

int main(void) {
    Node n1 = {10, NULL};
    Node n2 = {20, NULL};
    Node n3 = {30, NULL};

    n1.next = &n2;
    n2.next = &n3;
    n3.next = &n1;

    print_cycle(&n1);
    return 0;
}

预期输出

text
10 20 30 

这里的节点使用局部变量构造,因此示例不涉及动态内存释放,重点只放在循环遍历条件上。

空链表和单节点链表也要成立

do...while 不能直接对空指针解引用,所以遍历前必须先判断 head == NULL。如果链表为空,函数直接返回即可。

单节点循环链表则满足 head->next == head。第一次处理这个节点后,p = p->next 会立刻回到 head,循环恰好执行一次,因此同一套逻辑无需特殊分支。

两种容易出错的结束条件

把条件写成 p != NULL 会导致正常的循环链表永远无法结束,因为它本来就不存在作为终点的空指针。

另一种常见写法是从 head 开始,却用 p->next != head 控制循环。如果代码在条件成立后才处理 p,当 p 到达尾节点时条件已经为假,尾节点便可能被漏掉。相比之下,“先访问当前节点,再移动,移动后判断是否回到 head”的语义更直接,也更容易验证。

如果遍历不是从头节点开始,同样可以保存实际起点,例如 start = p,并在再次回到 start 时结束。核心原则始终相同:循环链表没有天然的 NULL 终点,遍历一圈必须依靠一个明确保存的起始节点来识别完成状态。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

循环链表怎样判断遍历结束

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通