★ FEATURED ARTICLE 1. 为什么会有循环链表从单链表的痛点说起1.1 单链表的尾部困境第一次接触单向循环链表的时候很多人都会冒出一个念头这东西不就是单链表最后一个节点指回头节点吗有什么好单独学的我第一次学的时候也是这个态度觉得它是老师们为了把表这一章讲得更厚而硬凑出来的考点。真正改变我想法的是一次做定时任务轮询调度的经历一堆任务要轮流执行最后一个执行完必须回到第一个用普通单链表写出来的代码到处都是if (p-next NULL) p head;这类补丁逻辑又丑又容易漏。后来换成单向循环链表整个调度逻辑变成了一条天然闭合的链接从头跑到尾再回到头这个需求直接被结构本身解决了。普通单链表的结构有一个隐含假设一切操作都是有终点的。从头节点出发走到next NULL就停下来。这在处理线性列表时没有问题但遇到绕一圈继续的场景就尴尬了。轮转调度、循环播放列表、多设备轮流分配请求这些场景的共同特征是首尾相接、周而复始。单链表非要用代码去模拟周而复始就得在每个循环的末尾做一次回溯到开头的判断而每次判断都伴随着别漏掉最后一个节点的阴影。单向循环链表把这个问题从根上解决了最后一个节点的next不再指向NULL而是指向头节点。遍历时只要你愿意可以沿着链表走任意圈数都不会断因为没有终点这个属性被结构天然地抹掉了。1.2 数组 取模为什么不够用可能有同学会说轮转场景我用数组加下标取模(index 1) % n不就搞定了确实能搞定而且对于固定大小、固定顺序的数据数组加取模是最简洁的方案没有之一。但数组有两个先天限制。第一容量固定扩容需要重新分配内存并搬运全部元素第二中间插入删除要移动大量元素。如果你的数据规模会动态变化或者操作集中在任意位置的插入删除数组就会非常别扭。比如一个游戏服务器维护一组正在排队的玩家随时有人加入、有人掉线用数组在中间删一个人可能要挪动几百个元素用链表只需要改两个指针。链表把顺序关系和容量彻底解耦节点散落在内存里靠next指针串联插入删除只涉及局部指针调整容量上限只受系统内存约束。这是链表区别于数组最大的优势也是循环链表继承下来的底子。1.3 单向循环链表与双向循环链表的取舍循环链表在教材里通常会分两个变体单向循环链表和双向循环链表。这里要学的是单向版本每个节点只有一个next指针最后一个节点指回头节点。双向循环链表多了一个prev指针好处是删除节点时可以直接拿到前驱在某些场景下能省掉一次遍历代价是每个节点多 8 字节内存64 位系统上一个指针的大小而且所有插入删除操作都要多维护一个指针代码量明显上涨。我的经验是如果删除操作频率极高、性能要求苛刻再考虑双向版本否则单向循环链表实现简单、内存紧凑绝大多数场景完全够用。2. 结构定义与初始化别小看这一步2.1 节点定义next 指向 NULL 还是指向自己先看最基础的节点定义typedef struct Node { int data; struct Node *next; } Node, *LinkedList;data先用int演示实际项目里通常换成void*指针或者泛型容器。这里有一个非常关键的习惯创建节点时把新节点的next初始化为指向自己而不是NULL。Node* createNode(int data) { Node* node (Node*)malloc(sizeof(Node)); if (node NULL) { fprintf(stderr, malloc failed\n); exit(1); } node-data data; node-next node; // 关键新节点先自指 return node; }为什么要自指因为只有一个元素的合法循环链表的形态就是唯一节点指向自身。如果你把新节点的next初始化为NULL后面一旦忘记补上闭环单节点链表就成了最后的节点指向空的畸形状态所有遍历逻辑都会出错。自指这个习惯能让空表、单节点、多节点三种状态都自然成立很多边界问题在最初一步就被消掉了。2.2 头指针还是尾指针一个影响复杂度的选择实现循环链表时最先遇到的问题就是保存head还是保存tail。这不是换汤不换药的细节它直接决定一批操作的复杂度。只保存 head从头遍历方便但要往尾部插入新节点得从头走一圈找到尾节点这是 O(n)。只保存 tail尾节点的next就是头节点于是尾部插入和头部插入都能做到 O(1)因为head tail-next这一步是 O(1) 的。代价是遍历时需要临时借一个变量记住起始节点因为没有一个直接的head指针。存储方式尾部插入头部插入遍历适用场景只有 headO(n)O(n)方便从 head 出发遍历为主、结构不常变化只有 tailO(1)O(1)需临时记录起点高频追加、模拟队列轮转注意第一行里的头部插入也是 O(n)虽然插入位置在 head 之后但因为循环链表的尾节点需要继续指向新的头节点你必须先找到尾节点才能完成闭环。这一点和普通单链表很不一样是循环链表新手最容易算错复杂度的地方。如果要把一批数据批量构造成循环链表保存tail指针可以把构建过程的复杂度从 O(n^2) 降到 O(n)区别非常明显。2.3 批量构造从数组到闭环Node* createCircularList(int arr[], int n) { if (n 0) return NULL; Node* head createNode(arr[0]); Node* tail head; for (int i 1; i n; i) { Node* node createNode(arr[i]); tail-next node; tail node; } tail-next head; // 关键闭环 return head; }这段代码里藏着一个我踩过的坑。createNode会把每个新节点的next初始化为自指所以如果你漏掉最后一行tail-next head;最后一个节点的next就会指向它自己。表面上看链表好像还是环形的但遍历时会在最后一个节点上无限打转因为它的next永远指向自己永远回不到head。这种 bug 非常难发现。排查的时候打印节点地址你会发现其他节点都正常唯独最后一个节点在原地绕圈。所以批量构建循环链表时闭环那行代码写完之后一定要立刻用一个遍历函数验证一遍。3. 遍历、插入、删除核心操作的完整实现3.1 遍历为什么 do-while 是标配遍历循环链表第一反应可能是这样写Node* cur head; while (cur ! head) { ... cur cur-next; }这个循环一次都不会执行因为一开始cur就等于head。这就是循环链表遍历和单链表遍历最大的差异结束条件从指针为 NULL变成了指针回到起点而起点本身也是要处理的节点。do-while 是这里最自然的选择void printList(Node* head) { if (head NULL) { printf(空链表\n); return; } Node* cur head; do { printf(%d - , cur-data); cur cur-next; } while (cur ! head); printf((回到头节点)\n); }do-while 保证循环体至少执行一次完美契合链表非空时至少有一个节点需要输出的语义。求长度同理int countLength(Node* head) { if (head NULL) return 0; int len 0; Node* cur head; do { len; cur cur-next; } while (cur ! head); return len; }我见过不少人在遍历上纠结非要写成 while 循环加一个先处理头节点再进入循环的特殊分支。能做但代码立刻丑一个档次。记住循环链表非空遍历直接用 do-while。3.2 插入三种写法与一个提速技巧先看最常用的头插和尾插void insertAtHead(Node** head, int data) { Node* node createNode(data); if (*head NULL) { *head node; return; } Node* tail *head; while (tail-next ! *head) { tail tail-next; } node-next *head; tail-next node; *head node; } void insertAtTail(Node** head, int data) { Node* node createNode(data); if (*head NULL) { *head node; return; } Node* tail *head; while (tail-next ! *head) { tail tail-next; } tail-next node; node-next *head; }两个操作都需要先找到尾节点复杂度都是 O(n)。如果持有tail指针这两个操作可以变成 O(1)。循环链表还有一种非常优雅的插入方式——在某节点之后插入它体现了指针操作的核心魅力void insertAfter(Node* prev, int data) { if (prev NULL) return; Node* node createNode(data); node-next prev-next; prev-next node; }这个函数只有三行却是整个循环链表里最值得反复琢磨的代码。在某节点后插入是链表的原子操作头插、尾插本质上都是它的特例头插 在尾节点后插入尾插 在原尾节点后插入。理解了insertAfter你对链表的理解就真正从背代码升级到了懂指针。再分享一个面试里可能见到的提速技巧如果只保存head又想 O(1) 完成逻辑上的头插可以这样——插入一个新节点到head之后然后把head的数据和新节点的数据互换void insertAtHeadO1(Node* head, int data) { // 前提head 不为空只关心逻辑顺序 Node* node createNode(head-data); node-next head-next; head-next node; head-data data; }这个技巧让新元素站在了逻辑第一位但物理上 head 节点没有换人所以完全不用去修改尾节点的next复杂度降到 O(1)。代价是节点的地址身份发生了变化对纯数据场景没问题如果外部还持有指向具体节点的指针就要谨慎使用。学有余力再看这个技巧基础阶段老老实实用insertAtTail就行。3.3 删除头节点这个特殊分支按值删除是循环链表实现里最容易出错的环节因为头节点一旦被删除闭环的入口就变了尾节点的next必须跟着改。完整实现如下int deleteByValue(Node** head, int target) { if (*head NULL) return -1; Node* cur *head; Node* prev NULL; do { if (cur-data target) { if (prev NULL) { // 目标是头节点需要先定位尾节点 Node* tail *head; while (tail-next ! *head) { tail tail-next; } if (tail *head) { // 链表只有一个节点 free(*head); *head NULL; } else { Node* old *head; *head old-next; tail-next *head; free(old); } } else { // 非头节点常规断开 prev-next cur-next; free(cur); } return 0; } prev cur; cur cur-next; } while (cur ! *head); return -1; }这里最值得说的是这个分支判断if (prev NULL)。在普通单链表里删除头节点就是把head往后挪一格一行代码搞定但在循环链表里删除头节点意味着要让原尾节点指向新的头节点而定位尾节点必须遍历一整圈所以复杂度是 O(n)。下面的分支tail *head处理的是单节点链表——整个链表只有一个节点头尾重合直接释放并置空。删除一个已知指针指向的节点在单向循环链表里也是 O(n)因为必须找到它的前驱。要想 O(1) 删除任意节点就得用双向循环链表或者额外的前驱信息。这是单向结构的固有代价不算缺陷选型时心里有数就行。还有一点要提醒删除操作之后任何指向被释放节点的指针都成了野指针。如果外部还有变量保存着删除前cur的地址别再用它。这也是我用了几次才彻底记住的教训。3.4 复杂度对比一张表说清楚学完插入删除有必要把复杂度做一个完整的对比。以下默认链表中节点数为 n操作普通单链表循环链表只有 head循环链表有 tail头部插入O(1)O(n)O(1)尾部插入O(n)O(n)O(1)删除头节点O(1)O(n)O(1)删除指定值节点O(n)O(n)O(n)遍历一圈O(n)O(n)O(n)这个表格解释了一个很容易被忽略的事实循环链表并没有让所有操作变快它改变的是表达能力。普通单链表在周而复始的场景下需要大量补丁代码循环链表把它变成了结构成本同时它放弃了普通单链表头插 O(1)的优势。数据结构选型从来没有银弹都是取舍。4. 空表、单节点、删头节点最容易出错的边界场景4.1 空链表所有操作的第一道门槛循环链表所有操作的第一步几乎都是判断head NULL。这一点和普通单链表一样但因为循环链表有自指的特性很多人会下意识以为反正节点都会自己连自己空表也不用管。这是错的。createNode的自指只对已经存在的节点生效空链表连头指针都是NULL任何head-next的访问都是野指针访问。我见过一个真实案例某个删除函数在空表时没有提前返回直接对NULL解引用程序段错误排查了半天才发现是调用方先删光了所有节点又调了一次删除。写循环链表的操作函数时先问自己三个问题空表能不能走单节点能不能走头节点被删了能不能走这三个问题在代码里各需要一个分支。4.2 单节点链表最特别的形态单节点链表的状态是node-next node它既是头也是尾。很多操作在这个状态下会表现出诡异但正确的行为遍历打印do-while 执行一次输出一个节点然后cur回到head循环结束。正确。删除这个节点tail *head成立走进单节点分支释放后置空。正确。在它后面插入insertAfter里node-next prev-next就是node-next node等于把新节点接到自己后面然后prev-next node形成两个节点的闭环。正确。单节点自指是循环链表最优雅也最危险的形态。优雅在于很多逻辑不用特判只有一个节点危险在于一旦某个操作忘了更新闭环node-next node会变成死循环的源头。比如前面说的批量构造漏掉tail-next head单节点场景下你根本看不出来因为自指已经让单节点看起来是闭环的。4.3 死循环的排查与验证循环链表最常见的 bug 就是死循环。症状很统一程序卡住CPU 100%遍历函数永远不返回。原因也基本统一某个节点的next没有正确回到该回的位置导致遍历条件cur ! head永远满足。排查死循环我强烈建议用一个带步数上限的验证函数int verifyCircular(Node* head) { if (head NULL) return 1; Node* cur head; int steps 0; do { cur cur-next; steps; if (steps 100000) { printf(疑似死循环指针跑了 %d 步还没回到 head\n, steps); return -1; } } while (cur ! NULL cur ! head); return (cur head) ? 1 : -1; }这个函数的好处是把死循环从无限崩溃变成了有限次提示。配合打印节点地址printf(%p\n, (void*)cur)你能看到循环究竟在哪里断裂。我用这个函数抓到过两次隐藏 bug一次是构造时漏了闭环另一次是删除头节点时忘了改尾节点指针。另一个非常实用的调试习惯是画图。链表相关的 bug十个里有八个靠盯着代码看不出来但把节点和指针画成箭头图一眼就能看出哪个箭头指错了。别嫌土真的管用。4.4 内存释放别把 next 指针跟着一起 free 了循环链表的内存管理有一个常见错误遍历释放节点时先free(cur)再去访问cur-next取下一个节点直接访问了野指针。正确的释放顺序是先保存下一个节点的地址再释放当前节点void destroyList(Node** head) { if (*head NULL) return; Node* start *head; Node* cur start; do { Node* nextNode cur-next; free(cur); cur nextNode; } while (cur ! start); *head NULL; }注意循环结束条件用的是cur ! start这里start保存的是最初的 head 地址。释放完最后一个节点后cur重新回到start循环退出。单节点情况下nextNode start释放后cur start循环条件直接不满足退出。这个写法对整个链表的释放是 O(n)比反复调用删除头节点那套逻辑省太多。5. 实战检验约瑟夫环的链表解法5.1 问题描述约瑟夫环是检验循环链表理解程度的经典题目n 个人围成一圈从第一个人开始报数报到 k 的人出列然后从下一个人重新报数直到只剩一个人为止。要求输出出列顺序和最后幸存者。这个问题用循环链表来解几乎是量身定做的人围成一圈对应循环链表的结构出列对应删除节点从下一个人重新报数对应继续向后遍历。整个过程不需要任何回到开头的补丁判断因为链表本身就是环。5.2 完整实现void josephus(int n, int k) { if (n 1 || k 1) return; // 构建 1..n 的循环链表 Node* head createNode(1); Node* tail head; for (int i 2; i n; i) { Node* node createNode(i); tail-next node; tail node; } tail-next head; Node* cur head; Node* prev tail; // prev 始终是 cur 的前驱 while (cur-next ! cur) { // 报数 k 次让 cur 停在要出列的人身上 for (int count 1; count k; count) { prev cur; cur cur-next; } printf(出列: %d\n, cur-data); prev-next cur-next; Node* tmp cur; cur cur-next; free(tmp); } printf(最后剩下的: %d\n, cur-data); free(cur); }这段代码里最精妙的一行是Node* prev tail;。在循环链表里每个节点都有前驱包括头节点——头节点的前驱就是尾节点。这个特性让整个约瑟夫环实现完全不需要删除头节点的特殊分支因为删除任何一个节点都是普通节点删除prev-next cur-next。而普通单链表要实现同样的逻辑删除头节点的瞬间就要处理头指针失效的问题代码复杂度立刻上去。这就是循环链表结构价值的直接体现它把环形场景下每个节点地位平等这个事实变成了代码里的自然表达。用 n5、k2 手动跑一遍出列顺序是 2、4、1、5最后剩 3。这个结果可以手算验证也是我写完后必做的自测用例。5.3 链表解法和数学解法的选择约瑟夫环还有一个数学公式解法著名的递推式f(1)0; f(i)(f(i-1)k)%i最后结果是f(n)1。那是不是说链表解法就没用了不是。数学公式只能算出最后一个幸存者给不出完整的出列顺序。如果问题要求打印整个出列序列公式就无能为力了而链表解法天然输出每一步的删除过程。其次数学公式推导需要理解取模递推的来龙去脉对初学者有门槛链表解法直接对应物理直觉理解成本低得多。我的建议是两种解法都掌握。链表解法帮你理解环形结构数学解法帮你在 n 非常大的时候快速出答案。实际面试里这两个解法都算经典答案能说出链表解法直观、数学解法高效的取舍本身就是加分项。6. 刷题和调试几个我很受用的习惯6.1 画图加辅助函数比盯着代码管用前面已经提过画图和verifyCircular这里再补充一个习惯每次写完链表操作立刻跑一遍覆盖三类状态的测试——空链表、单节点链表、三节点以上链表。我见过太多同学的测试只覆盖了三节点以上这个最常见状态导致删除头节点分支写错了都不知道。三行测试数据就能覆盖三个分支这点投入性价比极高。另外valgrind 或者编译器自带的 AddressSanitizer 一定要会用。链表是动态内存的重灾区字节级的内存泄漏和野指针访问用肉眼看几乎不可能发现但工具一跑就现原形。我的经验是凡是链表程序调试前先编译开 ASAN跑一次测试再看报告能省掉大半段错误排查时间。6.2 延伸思考单链表判环和循环链表的关联既然已经理解了最后一个节点指向 head 就是循环链表就可以顺带思考一个经典面试题如何判断一个普通单链表是否存在环这个问题和循环链表强相关——最常用的快慢指针解法本质就是两个指针在环形结构里必然相遇的原理。快慢指针的思路很简单一个指针每次走一步另一个每次走两步如果链表有环两个指针最终都会进入环内而且快指针一定会追上慢指针。这个结论背后的直觉是进入环之后快指针相对于慢指针的速度差是每次一步快走两步减慢走一步相对运动下必然套圈追上。学完循环链表再看这个题你会发现自己不需要记解法直接从环状结构的直觉推也能推出来。数据结构的大部分知识都是这样把底层结构理解透了面试题不过是同一个原理的不同包装。最后再啰嗦一句下次写代码时但凡遇到绕一圈的需求比如轮询、循环播放、进程调度条件反射地想一想能不能用单向循环链表。它不是什么高频炫技的结构但它把周而复始这件事变成了结构本身的一部分这种用结构代替逻辑判断的思路才是比记住代码更值钱的东西。我实际用下来最大的感受是写对循环链表之后我删掉的补丁代码比链表本身的代码还多。
阅读完成 · 觉得有帮助？
