说实话链表这个系列写到第4篇终于轮到循环链表了。单链表大家写起来还能靠NULL判断结尾可一旦把最后一个结点的next指回头结点代码就开始在环里面“转圈”各种死循环、漏打印、删错结点的问题全冒出来。这篇文章我想用一个完整的角度讲透单向循环链表结构怎么设计、初始化注意什么、插入删除怎么不翻车以及最经典的约瑟夫环怎么用代码落地。这个内容适合正在学数据结构的本科生、准备考研或者面试刷题的选手也适合工作中突然要手写链表但又忘得差不多的老哥。不管你用的是严蔚敏老师的 C 语言版教材还是王道考研系列循环链表这部分都是绕不开的知识点而且面试现场手写链表十次有四次会出到这里。1. 单向循环链表到底解决了什么问题1.1 和普通单链表相比差别只在一个指针普通单链表的最后一个结点指针域是NULL遍历到这就停下来。单向循环链表不一样它把最后一个结点的next重新指回头结点或者第一个结点整个链表从结构上变成了一个环。打个比方普通单链表是一条单行道走到终点你就得掉头循环链表是一条环形跑道你顺着路走只要不停下来就永远有下一个结点。这里有个细节要区分清楚循环链表有两种常见形态一种是带头结点一种是不带头结点。带头结点的做法是让尾结点指向头结点判空条件是head-next head不带头结点的做法是让尾结点指向首结点判空条件往往变成head NULL或者在遍历时判断p-next head。大学课堂上严蔚敏老师的教材和王道考研系列基本都采用带头结点的写法因为头结点的存在可以把空表和非空表的操作统一起来。比如删除第一个元素如果不带头结点你得先把head改掉有了头结点删除首元结点和删除中间结点的代码完全一样省心很多。1.2 尾指针循环链表里一个经常被忽略的设计很多人写循环链表只知道把尾结点指向头结点却不知道加一个尾指针会带来多大的收益。普通单链表想在末尾插入一个结点得从头开始找到尾时间复杂度是 O(n)。循环链表如果只保存head尾部操作同样要遍历一圈几乎没有优势。但如果你额外维护一个tail指针指向最后一个结点那么tail-next就是头结点或首结点在尾部插入一个结点就是 O(1) 的事。很多面试官喜欢问“如何实现在表尾 O(1) 插入”答案就是这个——用带尾指针的循环链表。所以实际工程里我一般建议用“头结点 尾指针”的组合既统一了空表和非空表的操作又把尾部操作的时间复杂度降了下来。尤其是在频繁在尾部追加数据的场景里这个设计非常实用。1.3 它和双向链表、静态链表怎么选有朋友会问既然循环链表这么好为什么不用双向循环链表双向循环链表确实操作更自由每个结点能 O(1) 找到前驱但代价是每个结点多存了一个指针内存占用更大插入删除时要维护的指针关系也更多写错概率成倍上升。我的建议是如果你只需要单向遍历、环形轮转、频繁尾部插入单向循环链表就够了如果业务里需要频繁进行“找前驱”的操作再考虑双向版本。数据结构选型本质上是在“空间、时间、实现复杂度”之间做权衡没有绝对的最优只有当前场景下最合适的选择。2. 结构设计与初始化把“环”搭起来2.1 结构体怎么定义我们用最经典的 C 语言写法数据域先用int方便测试真实业务里你可以换成任意数据类型。typedef struct LNode { int data; struct LNode *next; } LNode, *LinkList;LNode是结点类型LinkList是头指针类型。很多教材里把LinkList专门用来声明头指针而用LNode *声明普通的遍历指针这样在读代码的时候一眼就能看出每个变量的角色这个习惯建议保持。2.2 初始化空链表也是一个环带头结点的循环链表初始化的时候必须让头结点指向自己否则空链表无法判空。bool InitList(LinkList *L) { *L (LNode *)malloc(sizeof(LNode)); if (*L NULL) { return false; } (*L)-next *L; // 关键头结点的 next 指向自己 return true; }我第一次写循环链表的时候就犯了不把head-next指向head的错误结果判空的时候一直走head-next NULL的老逻辑后面所有操作全乱了。记住空循环链表的标志是L-next L不是L NULL更不是L-next NULL。2.3 创建 n 个元素的循环链表这里写一个用尾插法建表的函数顺便把尾指针这个设计用起来。LinkList CreateList(int n) { LinkList head NULL; InitList(head); LNode *tail head; for (int i 1; i n; i) { LNode *node (LNode *)malloc(sizeof(LNode)); node-data i; node-next head; // 新结点先指向头结点 tail-next node; // 尾结点指向新结点 tail node; // 新结点成为新的尾结点 } tail-next head; // 尾结点指回头结点形成环 return head; }整个过程可以这样理解头结点先自己跟自己构成一个空环然后每插入一个新结点就让当前尾结点指向它再更新尾结点为它自己最后把它的next指回头结点。只要保持“每次插入后尾结点都指向头结点”这个不变式链表就始终是闭合的。2.4 头结点和首元结点别把这两个概念搞混头结点是链表中第一个结点不存数据也可以叫哨兵结点首元结点是第一个存数据的结点也就是head-next指向的那个结点。遍历的时候很多人习惯从head-next开始这没问题。但判断循环链表空不空一定要用head-next head而不是head NULL。因为头结点在初始化时就已经存在了头指针本身一直非空。这道题在期末和考研选择题里经常出现本质上考的就是“带头结点循环链表如何表示空表”这个基础概念。3. 核心操作实现遍历、插入、删除3.1 遍历先证明“环”是闭合的遍历循环链表的写法和单链表唯一不同的地方在循环条件。void PrintList(LinkList L) { if (L-next L) { printf(empty list\n); return; } LNode *p L-next; while (p ! L) { printf(%d , p-data); p p-next; } printf(\n); }注意终止条件是p ! L也就是“回到头结点就停”。如果这里写成while (p ! NULL)程序会一直跑下去直到访问到野指针或触发段错误才停。我在带学生上机的时候最常见的现场翻车就是这里。一个排查思路是在while循环里加一个计数器比如最多打印 100 个元素然后手动跳出去看看是不是首元素出现了两次。如果打印序列开始重复就说明循环条件写错了或者环没有正确闭合。3.2 尾插法让尾指针帮你少跑一整圈在带尾指针的循环链表里尾部插入可以做到 O(1)这个操作在普通单链表里做不到因为普通单链表找尾部本身就是 O(n)。void InsertAtTail(LinkList L, int value) { LNode *tail L-next; // 如果维护了 tail 指针这里直接用 while (tail-next ! L) { tail tail-next; } LNode *node (LNode *)malloc(sizeof(LNode)); node-data value; node-next tail-next; tail-next node; }这段代码为了可读性每次插入都从头找尾。如果代码里全局维护了一个tail指针可以直接省掉while循环void InsertAtTailWithTail(LinkList L, LNode **tail, int value) { LNode *node (LNode *)malloc(sizeof(LNode)); node-data value; node-next L; (*tail)-next node; *tail node; }很多同学写到这里会有一个疑问node-next为什么不先置空因为在循环链表里尾结点的next永远指向头结点初始化为L或者说head才是符合环结构的不变式。要是置空了尾结点到最后一个结点之间的链就断了。3.3 删除指定元素最容易翻车的一步删除操作的核心是找到目标结点的前驱因为单链表没有前驱指针必须从头边走边找。bool DeleteByValue(LinkList L, int value) { LNode *prev L; LNode *cur L-next; while (cur ! L) { if (cur-data value) { prev-next cur-next; free(cur); return true; } prev cur; cur cur-next; } return false; }这个写法的一个好处是因为带头结点所以删除第一个元素时不需要单独处理“头指针移动”的问题。如果是不带头结点的循环链表删首元结点时就必须把head或者tail-next更新为被删结点的下一个结点逻辑会复杂不少。但有一个细节需要特别注意如果删的是尾结点并且你维护了tail指针那么tail必须同步更新否则后面再用tail就会指向一块已经释放的内存。具体做法是删除前判断tail cur是的话把tail改成prev。这个错误我在后文的“常见问题”章节还会再提因为它太典型了。3.4 查找、求长度、判空这三个操作几乎是循环链表的“标配”代码也相对简单。LNode *FindByValue(LinkList L, int value) { LNode *p L-next; while (p ! L) { if (p-data value) { return p; } p p-next; } return NULL; } int GetLength(LinkList L) { int count 0; LNode *p L-next; while (p ! L) { count; p p-next; } return count; } bool IsEmpty(LinkList L) { return L-next L; }这几个代码我建议直接背下来不要光看。考研笔试题里经常让你写出循环链表求长度的算法面试里也常让你实现IsEmpty别看简单很多人在while条件上栽过跟头。3.5 按位序插入按位序插入稍微有点绕因为你要找到第i-1个结点作为前驱然后在其后插入新结点。bool InsertAtPos(LinkList L, int i, int value) { if (i 1) { return false; } LNode *prev L; int step i - 1; while (step 0) { if (prev-next L) { return false; // 越界 } prev prev-next; step--; } LNode *node (LNode *)malloc(sizeof(LNode)); node-data value; node-next prev-next; prev-next node; return true; }越界判断建议放在循环内部因为循环链表里如果不加判断step再大也只会一直转圈你会“成功”地把结点插入到一个莫名其妙的位置。这里又是一个“循环结构虽然转圈快但边界要小心”的典型例子。4. 经典应用实战约瑟夫环的循环链表解法4.1 问题描述约瑟夫环问题Josephus Problem是数据结构课程里循环链表最经典的练习编号为 1 到 n 的 n 个人围成一圈从第 1 个人开始报数报到 m 的人出列然后下一个人重新从 1 开始报数直到所有人都出列要求输出出列顺序。这个问题的场景和循环链表简直是天作之合人围成一圈就是环出列就是删结点重新报数就是继续遍历。它把“循环”和“删除”两个核心操作结合起来很适合检验你对链表结构的理解。4.2 为什么不用数组模拟当然可以用数组模拟用一个visited数组记录谁已经出列但每报一个数都要判断当前人是否已经出列时间复杂度会偏高。如果连续多个人都已经离开圈子你还得不断跳着找下一个还活着的人代码写起来既不直观效率也一般。用循环链表模拟时出列的人被直接free掉剩下的人都“活着”遍历路径就是一条干净的环不需要额外的标记数组逻辑清晰很多。虽然链表在空间上多存了一个指针但这个问题里代码可读性和直观性比那一点点空间更值钱。4.3 代码实现尾指针就是“前驱指针”先看完整代码我再逐段拆解。#include stdio.h #include stdlib.h typedef struct Node { int data; struct Node *next; } Node; Node *CreateCyclicList(int n) { Node *head NULL; Node *tail NULL; for (int i 1; i n; i) { Node *node (Node *)malloc(sizeof(Node)); node-data i; node-next NULL; if (head NULL) { head node; } else { tail-next node; } tail node; } tail-next head; return tail; // 返回尾指针tail-next 就是首结点 } void Josephus(int n, int m) { Node *p CreateCyclicList(n); // p 始终指向待删结点的前驱 while (p-next ! p) { // 报数报到 m相当于让 p 向后移动 m-1 次 for (int i 1; i m; i) { p p-next; } Node *del p-next; printf(%d , del-data); p-next del-next; free(del); } printf(%d\n, p-data); free(p); } int main() { Josephus(5, 2); return 0; }运行结果2 4 1 5 3这里有个很关键的思考为什么要返回尾指针tail而不是头指针因为删除一个结点必须找到它的前驱。在单链表里想找前驱要么从头遍历要么一开始就保持一个指向“前驱”的指针。我们让p指向尾结点那么p-next就是首结点这正是“首结点的前驱”。之后每轮报数让p向后走m-1次停下来时p-next就是要删除的出列者。这样一来删除操作就不需要再循环去找前驱了一步到位。如果 m 是 1for循环一次都不执行p不动删除的正好是当前的p-next也就是第一个结点逻辑依然成立。这样的设计把边界情况统一掉了是我比较推荐的一种写法。最后一个结点退出循环的时候链表只剩一个元素它自己指向自己直接输出并释放即可。整个过程没有多余的哨兵结点干扰非常适合约瑟夫环这种纯粹的环上操作。4.4 扩展只求最后幸存者的数学解法如果题目只问“最后留下的是几号”其实可以不用链表用递推公式在 O(n) 时间内解决f(1) 0 f(i) (f(i-1) m) % i这里的下标从 0 开始最终答案加 1 即可。面试的时候如果能先给出这个数学解法再给出链表模拟的版本会是很明显的加分项。链表模拟的复杂度是 O(n*m)数学递推是 O(n)两者适用场景不同需要输出全部出列顺序时用链表只要求最后幸存者时用递推。5. 常见问题与调试技巧实录5.1 典型错误遍历条件写错导致死循环这个问题真的太多人踩了。写普通单链表写习惯了到了循环链表还是用while (p ! NULL)来控制循环结果最后一个结点的next指向头结点而不是NULL程序永远不会满足退出条件直接卡死。排查方法有两个第一在循环里加计数器比如限制最多打印 50 个元素看看有没有从头开始重复。如果打印的内容开始循环重复说明终止条件有问题。第二打印每个结点的地址看看最后一个结点打印完之后下一个地址是不是头结点的地址。配合地址打印基本一眼就能定位问题。5.2 典型错误删除尾结点后尾指针悬空如果你维护了tail指针删除操作这是最容易翻车的地方。看这段伪逻辑if (tail del) { // 这里一定要更新 tail tail prev; } prev-next del-next; free(del);不更新的后果是后续插入或者遍历时tail还在指向一块已经释放的内存程序崩溃或者出现诡异数据都是迟早的事。我个人的习惯是凡是涉及修改链表结构的操作代码里优先判断“被修改的结点是不是tail”是就提前更新。5.3 典型错误销毁链表时死循环销毁循环链表不等于一遍遍free到NULL因为没有NULL给你停。正确做法是每次记录下一个结点释放当前结点直到回到头结点为止。这里直接给出代码void DestroyList(LinkList L) { LNode *p L-next; while (p ! L) { LNode *tmp p-next; free(p); p tmp; } free(L); }注意先保存p-next再释放p顺序不能反否则释放完就找不到下一个结点了。如果链表为空p L循环体一次都不执行直接释放头结点也符合逻辑。5.4 调试技巧把地址打印出来看我调链表相关的代码最常用的方法不是瞪眼看而是打印。每个关键函数执行完打印一遍当前链表的所有结点的data和next指向的地址或者干脆打印next-data。比如你看到倒数第二个结点的next的data是首结点的值说明环闭合了如果看到next的值是野地址说明某个结点没有正确初始化。这个方法土归土但效率真的高。带项目的时候十个人里有八个 debug 半天找不到问题我过去加几行打印立刻就能定位到是漏了tail-next head还是遍历条件写错了。5.5 面试和考研中常见的考法这部分内容觉得值得提一下因为了解“会怎么考”可以帮助你更有针对性地复习。手写代码类约瑟夫环、按值删除、求链表长度、判断链表是否有环快慢指针、合并两个循环链表。这些代码量不大但很考验对循环结构和边界条件的把握。概念类带头结点和不带头结点的区别、空循环链表的判空条件、尾指针的作用、循环链表和普通单链表的适用场景差异。说句实在话这些题本身都不难难的是你平时有没有亲手写过、有没有踩过 bug。如果只是看书看懂了思路一到现场手写还是容易漏掉一两个关键指针赋值。最后分享一个小习惯我调链表时基本不会只靠看代码来找 bug而是把每个结点的地址和 data 打出来走一遍完整流程。别看这个方法土比瞪着屏幕猜快得多。数据结构里链表这关本质上就是和指针的next较劲画清楚图、打印清楚过程没有过不去的坎。