循环链表

2026 大纲 二（二）线性表的实现 · 2 链式存储 · 本篇只写相对单 / 双链表的增量，共性内容见主篇《单链表》，prior 的语义与插删的 4 步 / 2 步见《双链表》。

把"到达 NULL"换成"回到起点"

循环链表的改动只有一处：尾结点的 next 不再存 NULL，而是指回表头。 结点定义一个字不改，指针修改的动作也和单 / 双链表逐字相同。

但这一处改动会连带改掉所有"走到头了没有"的判断——因为链上再也没有 NULL 可以到达：

对比项	普通链表	循环链表（带头结点）
尾结点的指针域	`next = NULL`	`next = L`（指回头结点）
判空条件	`L->next == NULL`	`L->next == L`
遍历终止	`p != NULL`	`p != L`
判 `p` 是否为尾结点	`p->next == NULL`	`p->next == L`

还有一件常被忽略的好事：循环化的空间代价为零。 它不新增任何指针域，只是把尾结点那个本来存 NULL 的域改成存表头地址，存储密度与非循环版完全相同。所以"要不要循环"几乎总是一个只看操作需求的选择，不用权衡空间。

先看一眼

加载可视化中...

顺着环走两圈，确认一件事：从任意一个结点出发都能到达其余全部结点。下面「尾指针表示法」那一节的全部好处，都是从这句话来的。

增量一：判尾条件的改写

结点结构与单链表完全相同——循环链表不改结点定义，只改指针的指向约定。变的是初始化、判空与遍历。

typedef struct LNode {            // 与单链表逐字相同
    int data;
    struct LNode *next;
} LNode, *LinkList;

bool InitList(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode));
    if (*L == NULL) return false;
    (*L)->next = *L;          // 指向自身而非 NULL —— 空表也必须是闭合的环
    return true;
}

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

void Traverse(LinkList L) {
    LNode *p = L->next;       // 从首元结点开始
    while (p != L) {          // 回到头结点即停止
        printf("%d ", p->data);
        p = p->next;
    }
}

🔴 这两条判据绝不能凭手感写。 循环链表上误用 p != NULL 的后果是死循环——环上根本没有 NULL 可到达，而不是"少访问一个结点"；反过来，普通链表上误用 p != L 会走过 NULL 再解引用。写之前先确认这张表是不是环。

不带头结点时，尾结点指回的是首元结点，判尾条件相应变成 p->next == first。两种口径的判据不同，写代码前必须先定死用哪一种。

循环单链表的按位插入 / 删除代码与四种边界的逐格自查（想弄清越界判据为什么和插入不一样就展开）

不带头结点的循环单链表：头指针 first 指向首元结点 a₁，尾结点 aₙ 的指针域指回 a₁，整条链闭合成环，链上不存在空指针

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 2.12，p66。图中是不带头结点的版本，尾结点指回 $a_{1}$ ；下文代码采用带头结点版本，尾结点指回 L。

指针修改的动作与单链表逐字相同（s->next = p->next; p->next = s;），唯一的改动在查找前驱时的循环条件。

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->next == L）就停，不再往前
        p = p->next;
        j++;
    }
    if (j < i - 1) return false;          // 没走够 i-1 步就撞到表尾，说明 i 越界
    LNode *s = (LNode *)malloc(sizeof(LNode));
    if (s == NULL) return false;
    s->data = e;
    s->next = p->next;                    // 与单链表完全一致
    p->next = s;
    return true;
}

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) return false;   // 前驱之后已是头结点，无结点可删
    LNode *q = p->next;
    *e = q->data;
    p->next = q->next;      // 与单链表完全一致
    free(q);                // 释放放在最后
    return true;
}

把四个边界逐格代进去验一遍，就能确认那两个循环条件写对了：

空表插 $i = 1$ ：p = L，p->next == L 使循环一次都不执行，j = 0 不小于 i-1 = 0，于是执行插入。结果 L->next = s、s->next = L，环仍然闭合 ✓
空表插 $i = 2$ ：循环仍不执行，但 j = 0 < 1 成立，返回 false ✓
表长 2 插 $i = 3$ （插到表尾）：循环走 2 步后 p 停在第 2 个结点、p->next == L 退出，j = 2 不小于 2，插入在表尾，s->next 拿到 L，环闭合 ✓
表长 2 插 $i = 4$ ：循环同样在 j = 2 时因 p->next == L 退出，但 j = 2 < 3，返回 false ✓

删除同理：空表删 $i = 1$ 时循环不执行、p->next == L 成立，返回 false；表长 2 删 $i = 1$ 时循环不执行（j < 0 不成立），p = L、q 为首元结点，删除正确；表长 2 删 $i = 3$ 时循环走到 p 为第 2 个结点、p->next == L 退出，返回 false。

上面那两段代码有一处不对称，值得单独看清楚：插入判越界用的是 j < i-1，删除用的却是 p->next == L。 原因在于插入允许 $i = n + 1$ （插在表尾之后），此时 p 恰好停在尾结点、p->next == L 成立却完全合法，所以插入只能去查"有没有走够 $i - 1$ 步"；而删除没有"删第 $n + 1$ 个"这回事， $i = n + 1$ （走够了步数但前驱就是尾结点）与 $i > n + 1$ （没走够就撞上表尾）两种越界在退出时都满足 p->next == L，用这一条就够了。

顺带一个能省掉的判断：开头已经拦掉 $i < 1$ ，循环又只在 j < i-1 成立时才自增，于是恒有 $0 \leq j \leq i - 1$ ——再补一句 j > i-1 是永远为假的死代码。教材的按位取值算法里确实写了这一句，那是因为它没有单独拦 $i \leq 0$ ，靠它来兜住；这里前面拦过了，就不必重复。

增量二：尾指针表示法，以及它会失效的那一刻

普通单链表只留尾指针就再也回不到表头；是"环"使得从任一结点都能到达任一结点，尾指针才有资格独自标识整张表。用尾指针 rear 表示时，三个关键位置全是 $O (1)$ ：尾结点就是 rear、头结点是 rear->next、首元结点是 rear->next->next。

由此得到循环链表最有分量的一处收益——两个循环单链表可以 $O (1)$ 合并：

// 将 Lb 合并到 La 的尾部（两者均为尾指针，假设两表均非空）
LinkList Connect(LinkList La, LinkList Lb) {
    LNode *headA = La->next;    // 先存 La 的头结点，下一句就要覆盖 La->next
    La->next = Lb->next->next;  // La 的尾结点接上 Lb 的首元结点
    free(Lb->next);             // 释放 Lb 的头结点（已无人引用）
    Lb->next = headA;           // Lb 的尾结点接回 La 的头结点，环重新闭合
    return Lb;                  // Lb 即合并后表的尾指针
}

为什么是 $O (1)$ ：三步全是常数次指针赋值，没有一步需要遍历；若用头指针表示，光是第 1 步"找 $A$ 的尾结点"就要 $O (n)$ 。这条性质直接决定了链队列的实现：入队在表尾、出队在表头，用带尾指针的循环单链表两端都是 $O (1)$ 。

🔴 尾指针不是白拿的：一旦删掉的结点恰好是尾结点，rear 就悬空了。 最典型的局面是"删除第一个元素"——表里只有一个数据结点时，首元结点同时也是尾结点，把它摘掉之后 rear 指着一块已经释放的内存。所以带尾指针的循环链表，删除代码里必须补一句检查：

// 带尾指针 rear 的循环单链表（带头结点 h），删除第一个元素
q = h->next;              // q 指向首元结点
h->next = q->next;        // 头结点越过它
if (rear == q) rear = h;  // ← 被删的正是尾结点，尾指针回退到头结点
free(q);                  // 释放放在最后

注意判据写的是 rear == q（被删的是不是尾结点），不是 rear != q。判反的后果是：正常情况下把好好的尾指针改坏，而真正悬空的那次反而不修。

合并的逐步指针推演、教材的等价写法与空表前提（想手工验一遍指针怎么走就展开）

逐步验算（ $A = (1, 2, 3)$ 、 $B = (4, 5)$ ，均带头结点 $h_{A}$ 、 $h_{B}$ ）：

步骤	环的状态
初始	$h_{A} \to 1 \to 2 \to 3 \to h_{A}$ ，`La` = 结点 3； $h_{B} \to 4 \to 5 \to h_{B}$ ，`Lb` = 结点 5
`headA = La->next`	`headA` = $h_{A}$
`La->next = Lb->next->next`	结点 3 的 `next` 改为结点 4
`free(Lb->next)`	释放 $h_{B}$
`Lb->next = headA`	结点 5 的 `next` 改为 $h_{A}$
结果	$h_{A} \to 1 \to 2 \to 3 \to 4 \to 5 \to h_{A}$ ，`Lb` = 结点 5 即新尾指针 ✓

教材给出的语句段更短，因为它把"释放第二个表的头结点"留在正文里没写进代码（A、B 均为尾指针）：

p = B->next->next;    // p 指向 B 的首元结点
B->next = A->next;    // B 的尾结点接回 A 的头结点
A->next = p;          // A 的尾结点接上 B 的首元结点
                      // 正文另有一句：然后释放第二个表的头结点

两段代码语义相同，只是赋值次序不同——都遵守同一条约束：凡是要用到 A->next 或 B->next 原值的语句，必须排在覆盖它的语句之前。

⚠️ 两段代码都隐含"两表均非空"这个前提。 若 $B$ 为空表（Lb->next == Lb），尾指针 Lb 就是它自己的头结点，free(Lb->next) 会把 Lb 本身释放掉，后续 Lb->next = headA 就是写已释放内存。自己实现时应先特判空表。

增量三：循环双链表免掉了哪些特判

非循环双链表里，结构恒等式在首尾两端不成立（头结点无前驱、尾结点无后继），所以每段代码都要补 if (p->next != NULL) 这类判断。循环双链表里每个结点必有前驱和后继，恒等式处处成立，那些判断整段消失——插入四句、删除两句都可以直接连写。

循环双链表的结构是：头结点的 prior 指向尾结点、尾结点的 next 指向头结点，正反两条链都闭合；空表时头结点的两个指针都指向它自己，即 L->prior = L->next = L。

⚠️ 免掉的是判空特判，不是判头结点。删除时仍必须拦 p->next == L——头结点不是数据结点，删掉它整张表就散了。"循环链表不用特判"这句话要精确到"不用判 NULL"，而不是"不用判任何东西"。

循环双链表的初始化与插删代码、与循环单链表的操作集对照（想看清省掉的是哪几个 if 就展开）

操作	循环单链表	循环双链表
在已知结点之后插入	$O (1)$	$O (1)$
在已知结点之前插入	$O (n)$ （要找前驱）	$O (1)$
删除已知结点自身	$O (n)$ （要找前驱）	$O (1)$
反向遍历	做不到	$O (n)$
判 `p` 是否为尾结点	`p->next == L`	`p->next == L`

带附加头结点的双向循环链表：头结点的 prior 指向尾结点、尾结点的 next 指向头结点，正反两条链都闭合；空表时头结点的两个指针都指向它自己

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 2.16 带附加头结点的双向循环链表，p69。注意 (b) 空表：头结点仍在，只是它的 prior 与 next 都指向自身——这正是初始化要写 L->prior = L->next = L 的原因。

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

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

// 在结点 p 之后插入结点 s
bool InsertNextDNode(DNode *p, DNode *s) {
    if (p == NULL || s == NULL) return false;
    s->next = p->next;
    p->next->prior = s;   // ← 非循环版本这里要判 p->next != NULL，循环版本不必
    s->prior = p;
    p->next = s;
    return true;
}

// 删除结点 p 的后继结点
bool DeleteNextDNode(DLinklist L, DNode *p) {
    if (p == NULL || p->next == L) return false;  // 后继是头结点，说明 p 已是尾结点
    DNode *q = p->next;
    p->next = q->next;
    q->next->prior = p;   // ← 非循环版本这里要判 q->next != NULL，循环版本不必
    free(q);
    return true;
}

增量四：约瑟夫问题

$n$ 个人围成一圈（编号 $1 \sim n$ ），从第 1 个人开始报数，报到 $m$ 的人出列，再从下一个人重新报 1，如此循环直到所有人出列，求出列顺序。

为什么用不带头结点的循环单链表：①"围成一圈"没有逻辑上的表头，第 $n$ 个人的下一个就是第 1 个人，正是循环链表的结构语义；② 每个结点都是一个"人"，头结点没有意义、反而会在报数时被当成人数进去；③ 出列就是摘结点，圈空了算法自然结束。

约瑟夫问题的完整实现、三处设计要点与逐轮推演（想默写代码或手工验出列序列就展开）

约瑟夫问题 n=8、m=3 的逐轮出列过程：从 1 开始报数，出列顺序依次是 3、6、1、5、2、8、4，最后圈内只剩 7；每一格里的箭头标出该轮报到 m 的那个人

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图 2.15 $n = 8$ 、 $m = 3$ 的约瑟夫问题示例，p68。

// 约瑟夫问题：输出 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）： $1, 2, 3$ → 3 出列；从 4 起报， $4, 5, 1$ → 1 出列；从 2 起报， $2, 4, 5$ → 5 出列；从 2 起报， $2, 4, 2$ → 2 出列；圈内只剩 4。

这段代码有三处值得说清的设计：

为什么要维护 pre：单链表摘结点必须有前驱。若不维护 pre，每次出列都要绕环一整圈去找前驱，时间从 $O (n m)$ 涨到 $O (n^{2} + n m)$ 。
循环条件为什么是 p->next != p：圈内只剩 1 人时，这个人的 next 指向他自己。绝不能写成 p != NULL——循环链表里根本没有 NULL，那样写就是死循环。
走 $m - 1$ 步而不是 $m$ 步：从当前这个人（他报 1）走到报 $m$ 的那个人，中间只隔 $m - 1$ 步，所以循环写成 for (k = 1; k < m; k++)；写成 k <= m 会让整个出列序列偏移一个人。

时间复杂度 $O (n m)$ ：每出列一人要走 $m - 1$ 步，共出列 $n$ 人，总步数约 $n (m - 1)$ 。空间 $O (n)$ —— $n$ 个结点是问题本身的规模，算法只额外用了 pre、p、k 三个变量，辅助空间 $O (1)$ 。

⚠️ 两处容易搞反的细节：① 出列后下一轮从出列者的下一个人重新报 1，不是从原起点重新数；② $m = 1$ 时每个人报一次就出列，出列顺序就是 $1, 2, \dots, n$ ，代码里 for 循环一次都不执行，正好覆盖这个边界。

考点速记

三条会被反复调用的结论：

全部代码改动集中在一处：判尾的依据从"到达 NULL"变成"回到起点"，指针修改的动作本身与单 / 双链表逐字相同。
尾指针能独自标识整张表，是"环"给的；由它导出的两表 $O (1)$ 合并是最实的收益。
循环化的空间代价为零，所以要不要循环，只看操作需求。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：都是给四组指针语句，选出正确的那一组。要盯的是两处：

双向循环链表删除结点 p：正确写法是 p->next->prev = p->prev; p->prev->next = p->next; free(p);——两个方向各改一句，让 p 的前驱和后继直接互指。错误选项的手法是把某一句的右值写成 p->next 或 p->prev 中错误的那个，结果指针指回了被删结点自己。逐句代入结构恒等式验算即可。
带尾指针的循环单链表删除第一个元素：除了常规的摘结点三句，还必须补 if (rear == q) rear = h;——被删的若正是尾结点，尾指针要回退到头结点。判据写反（写成 rear != q）会把正常情况下好好的尾指针改坏。

易错：遍历条件写成 p != NULL。 环上没有 NULL，后果是死循环而不是漏访问一个结点。循环链表一律用 p != L（不带头结点时用 p != first）。

易错：删除时忘了尾指针可能同时失效。 只有一个数据结点时，首元结点就是尾结点，删完 rear 悬空。

易错：把"循环链表不用特判"理解成"什么都不用判"。 免掉的只是判 NULL；头结点不能删，p->next == L 这条拦截仍然必须写。

教材出处

循环链表的定义（"表中最后一个结点的指针域指向头结点，整个链表形成一个环。由此，从表中任一结点出发均可找到表中其他结点"）、以及判尾条件的改写（"在单链表中，判别条件为 p != NULL 或 p->next != NULL，而循环单链表的判别条件为 p != L 或 p->next != L"）：严蔚敏《数据结构（C 语言版）》（第 2 版），p38，2.5.3 节。
只设尾指针不设头指针可使一些操作简化，以及两个循环单链表合并的三行语句段与"上述操作的时间复杂度为 $O (1)$ "：同书 p39。该页正文另有一句 "然后释放第二个表的头结点"，这一步在语句段里没有写出。
双向链表也可以有循环表（图 2.19(c)）、空的双向循环链表只有一个表头结点：同书 p39–p40。

真题练习

2021Q12分 2019Q4210分 2016Q22分

循环链表

把"到达 NULL"换成"回到起点"

先看一眼

增量一：判尾条件的改写

增量二：尾指针表示法，以及它会失效的那一刻

增量三：循环双链表免掉了哪些特判

增量四：约瑟夫问题

考点速记

相关知识

相关文章

交互体验

真题练习

相关真题（3题）

循环链表 ​

把"到达 NULL"换成"回到起点" ​

先看一眼 ​

增量一：判尾条件的改写 ​

增量二：尾指针表示法，以及它会失效的那一刻 ​

增量三：循环双链表免掉了哪些特判 ​

增量四：约瑟夫问题 ​

考点速记 ​

相关知识 ​

相关文章

交互体验

真题练习 ​

相关真题（3题）

循环链表

把"到达 NULL"换成"回到起点"

先看一眼

增量一：判尾条件的改写

增量二：尾指针表示法，以及它会失效的那一刻

增量三：循环双链表免掉了哪些特判

增量四：约瑟夫问题

考点速记

相关知识

真题练习