CodeBrick 博客

Appearance

循环链表 ​

相比普通链表的改进 ​

循环链表将尾结点的指针指回头部，形成一个环。用尾指针就能 O(1) 同时访问表头和表尾，从任意结点出发都能遍历全部结点。典型应用场景包括：

  • 操作系统中的轮转调度（Round-Robin）
  • 经典的约瑟夫问题（Josephus Problem）
  • 需要反复循环处理的数据缓冲区

核心思想 ​

循环链表的核心特点：

  • 循环单链表：尾结点的 next 指针不为 NULL，而是指向头结点（带头结点时）或第一个数据结点（不带头结点时）
  • 循环双链表：在循环单链表的基础上，头结点的 prior 指向尾结点，尾结点的 next 指向头结点，形成双向闭合环
  • 判空条件不同：普通链表判 p->next == NULL；循环链表判 p->next == L（是否回到头结点）

循环单链表结构示意：

┌───┬───┐   ┌───┬───┐   ┌───┬───┐
│ L │ ──┼──→│ a₁│ ──┼──→│ a₂│ ──┼──┐
└───┴───┘   └───┴───┘   └───┴───┘  │
  ↑                                 │
  └─────────────────────────────────┘

循环双链表结构示意：

       ┌──────────────────────────────────┐
       ↓                                  │
  ┌───┬───┐   ┌───┬───┐   ┌───┬───┐     │
  │ L │   │←──│ a₁│   │←──│ a₂│   │     │
  │   │ ──┼──→│   │ ──┼──→│   │ ──┼─────┘
  └───┴───┘   └───┴───┘   └───┴───┘

循环链表 vs 普通链表：终止条件对比 ​

对比项普通链表循环链表
尾结点指针next = NULLnext = L（指向头结点）
判空条件L->next == NULLL->next == L
遍历终止p != NULLp != L

易错：循环链表的判空条件与普通链表不同：普通链表判 head->next == NULL，循环链表判 head->next == head（带头结点时）。408 选择题常考这个区别。

交互可视化 ​

通过下方的交互动画，你可以逐步观察循环链表的执行过程：

加载可视化中...

操作详解 ​

循环单链表 ​

结点定义 ​

c
typedef struct LNode {
    int data;
    struct LNode *next;
} LNode, *LinkList;

初始化（带头结点） ​

初始化时，头结点的 next 指向自身，形成空的循环链表。

c
bool InitList(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode));
    if (*L == NULL) return false;
    (*L)->next = *L;  // 指向自身，而非 NULL
    return true;
}

判空 ​

c
bool Empty(LinkList L) {
    return L->next == L;  // 注意：不是 L->next == NULL
}

遍历 ​

与普通单链表的关键区别在于终止条件：不再判 p != NULL，而是判 p != L（是否回到头结点）。

c
void Traverse(LinkList L) {
    LNode *p = L->next;   // 第一个数据结点
    while (p != L) {       // 回到头结点时停止
        printf("%d ", p->data);
        p = p->next;
    }
}

在第 i 个位置插入 ​

关键步骤与普通单链表相同，找到第 i-1 个结点后执行插入。唯一区别是查找过程中终止条件从 p != NULL 变为 p != L。

c
bool ListInsert(LinkList L, int i, int e) {
    if (i < 1) return false;
    LNode *p = L;
    int j = 0;
    while (p->next != L && j < i - 1) {  // 终止条件不同
        p = p->next;
        j++;
    }
    if (j < i - 1) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

删除第 i 个结点 ​

c
bool ListDelete(LinkList L, int i, int *e) {
    if (i < 1) return false;
    LNode *p = L;
    int j = 0;
    while (p->next != L && j < i - 1) {
        p = p->next;
        j++;
    }
    if (p->next == L || j > i - 1) return false;
    LNode *q = p->next;
    *e = q->data;
    p->next = q->next;
    free(q);
    return true;
}

尾指针的妙用 ​

如果设置一个尾指针 rear 指向尾结点（而非头指针），则：

  • 访问尾结点：rear，时间 O(1)
  • 访问头结点：rear->next，时间 O(1)
  • 访问第一个数据结点：rear->next->next，时间 O(1)

这在两个循环单链表的合并中特别有用，可以在 O(1) 时间内完成：

c
// 将 Lb 合并到 La 的尾部（均用尾指针表示，假设两表均非空）
LinkList Connect(LinkList La, LinkList Lb) {
    LNode *headA = La->next;  // 保存 La 的头结点
    La->next = Lb->next->next; // La 尾接 Lb 第一个数据结点
    free(Lb->next);            // 释放 Lb 的头结点
    Lb->next = headA;          // Lb 尾接 La 头结点
    return Lb;                 // 返回新的尾指针
}

注意：以上是教材标准写法，隐含前提是两表均非空。若 Lb 为空表（Lb->next == Lb），尾指针 Lb 就是它自己的头结点，free(Lb->next) 会把 Lb 本身释放掉，后续访问就是错误的。考试默认两表非空即可；自己实现时应先特判空表。

循环双链表 ​

结点定义 ​

c
typedef struct DNode {
    int data;
    struct DNode *prior, *next;
} DNode, *DLinklist;

初始化（带头结点） ​

头结点的 prior 和 next 都指向自身。

c
bool InitDLinkList(DLinklist *L) {
    *L = (DNode *)malloc(sizeof(DNode));
    if (*L == NULL) return false;
    (*L)->prior = *L;  // 前驱指向自身
    (*L)->next = *L;   // 后继指向自身
    return true;
}

判空 ​

c
bool Empty(DLinklist L) {
    return L->next == L;
}

遍历 ​

c
void Traverse(DLinklist L) {
    DNode *p = L->next;
    while (p != L) {       // 回到头结点时停止
        printf("%d ", p->data);
        p = p->next;
    }
}

在结点 p 之后插入结点 s ​

与普通双链表的操作基本一致，但因为是循环结构，不需要特判 p 是否为尾结点——p->next 永远不会是 NULL。

c
bool InsertNextDNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return false;
    s->next = p->next;
    p->next->prior = s;  // 无需判空，循环链表中 p->next 必有效
    s->prior = p;
    p->next = s;
    return true;
}

删除结点 p 的后继结点 ​

同样无需特判尾结点。但要注意不能删除头结点（即 p->next == L 时不可删除）。

c
bool DeleteNextDNode(DLinklist L, DNode *p) {
    if (p == NULL || p->next == L) return false;  // 后继是头结点则无法删除
    DNode *q = p->next;
    p->next = q->next;
    q->next->prior = p;
    free(q);
    return true;
}

循环双链表的优势 ​

相比循环单链表，循环双链表可以在 O(1) 时间内找到任意结点的前驱，因此：

  • 在某结点之前插入：O(1)
  • 删除当前结点自身：O(1)（不需要找前驱）

这使得循环双链表成为实际工程中最常用的链表形式之一。

应用：约瑟夫问题 ​

**约瑟夫问题（Josephus Problem）**是循环单链表的经典应用：n 个人围成一圈（编号 1~n），从第 1 个人开始报数，报到 m 的人出列，然后从下一个人重新报 1，如此循环直到所有人出列。求出列顺序。

这个场景里每个结点都是"人"，没有逻辑上的表头，所以用不带头结点的循环单链表最自然——出列就是摘结点，圈空了算法结束。

c
// 约瑟夫问题：输出 n 个人按报数 m 的出列序列
void Josephus(int n, int m) {
    // 1. 建表：不带头结点的循环单链表，结点依次存编号 1~n
    LNode *head = (LNode *)malloc(sizeof(LNode));
    head->data = 1;
    LNode *tail = head;
    for (int i = 2; i <= n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = i;
        tail->next = s;
        tail = s;
    }
    tail->next = head;                 // 尾指回首，成环

    // 2. 报数出列：pre 始终是 p 的前驱，方便摘除 p
    LNode *pre = tail, *p = head;
    while (p->next != p) {             // 圈内剩下超过 1 人
        for (int k = 1; k < m; k++) {  // p 从"报 1"走到"报 m"的人
            pre = p;
            p = p->next;
        }
        printf("%d ", p->data);        // 报到 m，出列
        pre->next = p->next;           // 从圈中摘除 p
        free(p);
        p = pre->next;                 // 下一轮从出列者的下一人重新报 1
    }
    printf("%d\n", p->data);           // 圈内最后一人
}

以 n = 5、m = 3 验证：出列顺序为 3, 1, 5, 2, 4。时间复杂度 O(n·m)——每出列一人要走 m-1 步，共出列 n 人。

易错：①出列后下一轮从出列者的下一个人报 1，不是从原起点重新数；②循环条件是 p->next != p（圈内剩 1 人时它的 next 指向自己），别写成 p != NULL——循环链表里没有 NULL。

复杂度分析 ​

循环单链表 ​

操作时间复杂度说明
头插 / 头删O(1)在头结点之后操作
尾插（头指针）O(n)需遍历找到尾结点
尾插（尾指针）O(1)尾指针直接定位
按位查找O(n)需从头遍历
按值查找O(n)最坏遍历整个表
两表合并（尾指针）O(1)仅修改指针

循环双链表 ​

操作时间复杂度说明
在已知结点后插入O(1)修改四个指针
在已知结点前插入O(1)利用 prior 直接定位
删除已知结点O(1)利用 prior 无需遍历
按位查找O(n)需从头遍历
按值查找O(n)最坏遍历整个表

空间复杂度：所有操作均为 O(1)，只需常数级辅助空间。

考研高频考点 ​

  • 循环链表的判空条件：L->next == L（对比普通链表的 L->next == NULL）
  • 循环链表遍历终止条件：p != L（对比普通链表的 p != NULL）
  • 尾指针表示循环单链表的优势：O(1) 时间访问头尾结点、O(1) 时间合并两个循环链表
  • 约瑟夫问题（Josephus Problem）：n 个人围成一圈，从第 k 个人开始报数，报到第 m 个人出列，循环进行直到所有人出列。这是循环链表的经典应用，考研中常以算法设计题出现（完整实现见上文"应用：约瑟夫问题"一节）
  • 循环双链表插入、删除操作的指针修改顺序（选择题/代码填空题高频）
  • 循环链表 vs 普通链表的适用场景对比
  • 循环双链表中无需特判尾结点的原因分析

相关知识 ​

  • 循环链表是单链表的变体，将尾结点的 next 指回头结点形成环
  • 循环队列的设计思想与循环链表类似——都是通过"首尾相连"解决空间浪费或遍历受限的问题
  • 队列的链式存储也可以使用循环链表实现，尾指针表示时入队出队均为 O(1)
  • 循环双链表结合了双链表和循环结构的优势，插入删除时无需特判边界

相关文章

交互体验

前往完整可视化页面 →

真题练习 ​