1. 循环链表删除操作与单链表的第一层差异1.1 循环链表的本质没有一个节点是终点前几天有个朋友问我循环链表删除节点到底怎么写才不踩坑。他说自己照着单链表的删除逻辑改了两行结果一跑就死循环。我听完就笑了这几乎是每个写过循环链表的人都撞过的墙。先明确一个基本概念。循环链表Circular Linked List和单链表最大的区别在于单链表的尾节点指向NULL遍历时靠p ! NULL来终止而循环链表的尾节点指向头节点或者指向自身如果只有一个节点整个链表形成一个闭环。这意味着循环链表里没有任何一个节点是终点遍历时如果处理不好终止条件程序就会永远转下去。这个结构特性直接影响了删除操作的设计。在单链表里删除一个节点只需要让前驱节点的next指向后继节点然后把当前节点释放掉逻辑非常直白。但到了循环链表里问题就变成如果删除的是头节点链表新的头节点是谁如果删除的是唯一的节点链表是不是就空了如果遍历过程中不小心越过了一圈怎么知道自己已经转回来了别小看这几个问题它们恰恰是删除循环链表节点这个主题里最容易翻车的地方。struct Node { int val; Node* next; Node(int x) : val(x), next(nullptr) {} };在初始化一个循环链表时通常的做法是让最后一个节点的next指向第一个节点如果只有一个节点就让它的next指向自己。抓住这个无 NULL 结尾的特征后面的删除逻辑才有讨论的基础。1.2 直接套单链表模板为什么会出问题很多人第一次写循环链表删除会有这样的念头把单链表删除的代码拿过来把终止条件从p ! NULL改成p ! head不就行了听起来合理但实际写出来的代码经常在两个地方出问题。第一处是遍历遍历的终止条件。写成while (cur ! head)只会在cur回到头节点时停下来可如果删除的目标刚好是头节点cur在删除头节点后就指向了新的头节点这时候循环根本不会走到cur head于是死循环。第二处是前驱指针的维护。单链表里删除尾节点后新的尾节点next置为NULL就行循环链表里删完尾节点还得让新尾节点指向头节点这个细节漏掉链表的结构就被破坏了。所以我的建议是不要试图把单链表代码改几行变成循环链表版本而是从循环链表的结构出发重新设计删除逻辑。1.3 删除操作的四种场景划分在实际项目中循环链表删除节点通常会遇到四种情况场景问题描述核心难度按值删除删除链表中所有值等于 target 的节点头节点删除、连续重复节点按位置删除删除第 k 个节点如约瑟夫环场景位置计数与指针移动的配合已知指针删除给定某个节点的指针要求 O(1) 删除尾节点无法 O(1) 处理清空链表删除所有节点释放全部内存先断开环再逐个释放后面几个小节我会逐一展开这四种场景的完整实现和注意事项。\2. 按值删除多个节点的实现与边界处理2.1 终止条件do-while 比 while 更适合按值删除意思是给定一个target把循环链表里所有值为target的节点全部删掉。这种需求在实践里很常见比如在任务调度循环链表里移除所有失败任务。遍历时有两种写法。一种是先记录头节点再用while另一种是用do-while。我强烈推荐do-while。bool removeByValue(Node* head, int target) { if (head nullptr) return false; Node* cur head; Node* prev nullptr; bool found false; // 先找到 prev即尾节点头节点的前驱 prev head; while (prev-next ! head) { prev prev-next; } // 用 do-while 遍历一圈 do { if (cur-val target) { if (cur head) { // 删除头节点需要特殊处理 if (head-next head) { // 只有一个节点的循环链表 delete head; head nullptr; cur nullptr; found true; break; } else { Node* temp cur; prev-next cur-next; head cur-next; // 头节点后移 cur cur-next; delete temp; found true; // 注意这里不移动 prev continue; } } else { // 删除普通节点 Node* temp cur; prev-next cur-next; cur cur-next; delete temp; found true; // 同样不移动 prev continue; } } prev cur; cur cur-next; } while (cur ! head); return found; }这里do-while的优势很多因为循环链表至少有一个节点do-while保证至少执行一次循环体处理完头节点后cur指向新的头节点此时cur ! head判断依然能够正确终止。如果用while (cur ! head)做前置判断一开始cur head循环体一次都不会执行整段代码就废了。2.2 头节点删除后头指针必须更新上面的代码里删除头节点时做了一个关键操作head cur-next。这行代码的作用是更新链表的头节点。很多人写循环链表删除时会忽略这一步。他们觉得反正链表是循环的从哪个节点出发都能访问到所有节点头节点是否更新无所谓。这个想法在只需要遍历的场景下没错但在实际工程里有问题第一很多调用方持有head指针如果head指向一个已经被删除的节点下一次访问就是野指针直接崩溃。第二链表判空逻辑通常依赖head nullptr如果删除唯一节点后不及时将head置空链表状态就会出现严重的不一致。所以无论用什么语言写循环链表的删除头指针的更新是必须要做好的事情。C 里必须用引用或二级指针传递head否则函数内部修改的head在函数外不生效。2.3 连续重复节点的跳过陷阱按值删除时还有一个经常遇到的情况链表里有连续多个值为target的节点。比如链表是1 - 2 - 2 - 2 - 3要把所有值为 2 的节点删掉。很多新手在删除一个值为target的节点后会把prev和cur同时往前移动一位。这样做的问题在于如果下一个节点仍然是目标值prev已经指向了待删除节点的前驱此时就无法再通过prev-next cur-next完成删除了。正确的做法是删除当前节点后cur更新为cur-next但prev保持不变让下一轮循环继续检查新的cur。这也正是我在前面代码里写continue而不移动prev的原因。这个细节也许看起来不起眼但在实际项目里有真实案例。比如在一个定时任务循环链表里需要清理所有已经超时的任务节点如果处理不好连续超时节点就会导致某些超时任务漏删后续执行时造成重复调度。不要嫌这些边界情况烦链表题的坑几乎全部集中在边界上。2.4 清空头节点后链表为空的状态维护在按值删除的过程中如果整个链表的所有节点都被删除了需要把head置为nullptr同时确保没有残留的野指针。前面代码里的特判就处理了这种情况当head-next head时说明这是唯一节点删除后head直接置空。这个判断非常关键因为唯一节点既是头节点又是尾节点它的next指向自己如果不特判删除后链表会留下一个自我引用的无效状态。写成代码很容易但我想提醒的是这条判断是循环链表特有的。单链表里唯一节点的next本来就是NULL删除后直接让head NULL就行没有歧义。循环链表则必须先判断然后再决定是否断开自引用。如果在 C 语言中维护还要注意释放后的指针置空问题。尽量不要在释放后仍然保留原指针的副本否则后面的free或delete操作会触发二次释放。\3. 已知节点指针的 O(1) 删除技巧与风险3.1 单链表做不到的循环链表可以做到大半现在来看另一种常见需求已知链表里某个节点的指针要求把这个节点删除。在单链表里如果不遍历去找前驱节点几乎不可能 O(1) 删除——因为你只有当前节点的指针没有前驱信息无法把前驱的next接过来。循环链表却可以做到大部分情况下的 O(1) 删除。思路很巧妙不删除当前节点本身而是把当前节点的值替换成后继节点的值然后删除后继节点。外观看上去你删除的就是当前节点但实际操作的是它的后继。这个方法在数据结构和算法领域很出名很多面试题都以此为考点。void deleteNode(Node* node) { if (node-next node) { // 唯一节点无法用常规方法处理由调用方决定 return; } Node* next node-next; node-val next-val; node-next next-next; delete next; }代码很简洁对吧但这里有个非常隐蔽的问题如果node是链表的尾节点node-next指向的是头节点那这段代码就会把头节点的值复制到尾节点上然后删除头节点。这可不是你想要的结果。3.2 借尸还魂 删除法的原理和限制我把这个技巧叫作借尸还魂因为本质上是让新节点顶替旧节点的位置而不是真的删除旧节点。它的完全版实现应该是这样的void deleteNode(Node* node) { if (node nullptr) return; // 情况一node 是尾节点即 node-next head 的情况 // 需要从头遍历找到它的前驱 if (node-next head) { // 唯一节点 if (node-next node) { delete node; head nullptr; return; } // 找前驱 Node* curr head; while (curr-next ! node) { curr curr-next; } curr-next head; delete node; return; } // 情况二普通节点用后继覆盖 Node* next node-next; node-val next-val; node-next next-next; delete next; }看到没有尾节点是个例外。因为尾节点的next不是普通后继而是头节点直接覆盖尾节点的值会导致头节点的值被错误修改进而影响整个链表的逻辑。所以面对尾节点只能老老实实从头遍历找前驱时间是 O(n)。这也就意味着循环链表的 O(1) 删除是有条件的只有删除非尾节点时才能做到 O(1)删除尾节点时需要 O(n) 的额外代价。3.3 工程上到底该不该用这个技巧很多算法教程讲到这里就结束了但我必须多说几句工程上的考量。这个借尸还魂技巧虽然能省时间但它有一个隐含的前提节点本身不带有需要特殊处理的外部资源。如果节点里管理着堆内存、文件句柄、锁资源等直接覆盖值再删除后继节点会导致资源管理错乱。比如原来节点持有某个对象的唯一所有权你把后继节点的值复制过来原来那个对象的引用计数就乱了。另外在有外部引用的场景下使用这个技巧也需要谨慎。如果链表的其他部分或者调用方持有指向被删除节点的指针经过借尸还魂后这个节点的值已经被替换成后继节点的值外部引用方读到的是错误的旧数据。在一个小规模链表里这种问题可能难以察觉但放到大型系统里这类数据幽灵问题排查起来非常痛苦。所以我的建议是算法题里可以用这个技巧拿复杂度工程项目里尽量用常规的双指针法找前驱。如果一定要用必须保证节点不持有独立资源并且没有任何外部指针长期引用该节点。\4. 约瑟夫环场景中删除第 k 个节点4.1 约瑟夫环问题循环链表删除的经典舞台如果说删除循环链表节点有一条最经典的实战路径那一定是约瑟夫环Josephus Problem。问题描述是这样的有 n 个人围成一圈从第 1 个人开始报数数到第 k 个人出列然后从下一个人重新开始报数问最后剩下的人是几号。这个问题的本质就是在一个循环链表上反复执行按位置删除操作。每次删除一个节点后链表会自动闭合下一次报数从被删除节点的后继节点开始。几乎所有支持链表的数据结构教材都会用约瑟夫环作为循环链表的综合练习。用代码来实现之前先想清楚过程构建一个 n 个节点的循环链表节点值分别是 1 到 n。用指针cur指向当前报数的人用prev指向它的前驱。从cur开始移动 k-1 步到达第 k 个节点。删除这个节点同时把prev-next接到被删节点的后继上。让cur指向后继节点继续下一轮报数。直到链表中只剩下一个节点。4.2 先删除第 k 个节点还是先移动指针这一步是约瑟夫环循环链表实现里最常见的分歧点是先让指针移动 k-1 步再删除还是先删除再移动事实上正确答案是先移动再删除而且移动的步数是 k-1 而不是 k。理由是报数时当前节点本身就是第 1 个数所以从当前节点到第 k 个节点只需要往前走 k-1 步。如果从cur开始走 k 步实际上会走到第 k1 个节点把报数逻辑弄错。int josephus(int n, int k) { // 构建循环链表 Node* head new Node(1); Node* cur head; for (int i 2; i n; i) { cur-next new Node(i); cur cur-next; } cur-next head; // 形成环 Node* prev cur; // prev 指向尾节点头节点的前驱 cur head; while (cur-next ! cur) { // 当链表中还剩至少两个节点 // 移动 k-1 步找到第 k 个节点 for (int i 1; i k; i) { prev cur; cur cur-next; } // 删除 cur prev-next cur-next; Node* temp cur; cur cur-next; delete temp; } int result cur-val; delete cur; return result; }这份代码里有个细节很容易被忽略初始化时prev被设置成了尾节点。为什么因为循环链表的删除操作需要前驱节点的指针而头节点的前驱正是尾节点。如果初始化后不把prev指向尾节点当第一次需要删除头节点时prev会是一个野指针程序直接崩溃。4.3 复杂度分析与大 k 值的性能问题上面这份实现的时间复杂度是 O(nk)每删除一个节点需要移动 k-1 步一共要删除 n-1 个节点。对于 n 和 k 都是几百几千的规模O(nk) 完全够用但如果说 n 是 10 万、k 是 10 万那 O(nk) 就是 100 亿级别的操作直接超时。优化方法有很多。比如每次移动的步数可以对当前链表长度取模k-1可以压缩成(k-1) % 剩余节点数因为走完整圈回来后其实又到了原点。这个优化不改变算法整体方向但能把大 k 值场景下的无效移动大幅削减。while (cur-next ! cur) { int steps (k - 1) % countNodes; // countNodes 是当前链表长度 for (int i 0; i steps; i) { prev cur; cur cur-next; } // 删除逻辑同上 }countNodes可以每轮维护一个计数器也可以用循环链表求长度。对于大规模应用使用取模优化是很有必要的。如果 k 远大于 n这个优化能把时间复杂度从 O(nk) 降到接近 O(n^2)再加上每一轮剩余节点数都在减少整体效果非常明显。4.4 用手工模拟验证测试用例写完代码后手工模拟几组数据是最好的验证方式。以 n5、k2 为例初始1 - 2 - 3 - 4 - 5 - 1从 1 开始报数1 是数到 12 是数到 2删除 2。链表变为1 - 3 - 4 - 5 - 1从 3 开始报数3 数 14 数 2删除 4。链表变为1 - 3 - 5 - 1从 5 开始报数5 数 11 数 2删除 1。链表变为3 - 5 - 3从 3 开始报数3 数 15 数 2删除 5。最后剩 3。把这段模拟过程跑完再对拍代码输出如果结果一致基本可以确定实现逻辑没有大问题。我建议你在写任何链表删除算法时都先手动跑一个小的用例不要直接跳到大数据量验证否则出了问题很难定位。\5. 实测中容易踩的坑死循环、野指针和首尾衔接5.1 死循环的成因与排查手段我在这个主题下见过最多的 bug 就是死循环。死循环在循环链表删除里通常有三个来源第一个来源是终止条件设计错误。比如写while (cur ! head) { ... cur cur-next; }如果头节点被提前删除cur永远不会等于head循环就停不下来了。解决办法是使用do-while结构并且在删除头节点后同步更新head。第二个来源是删除节点后没有及时让prev-next正确指向后继。假如删除cur后忘记更新prev-next那么链表的环就会断开或者形成自环遍历时就会沿着错误的引用链一直绕圈。比如prev-next仍然指向已被删除的cur而cur-next又可能是某个还在链表中的节点遍历路径就会混乱。第三个来源是递归删除整表时没有先断开环。有一种常见的写法是递归删除节点deleteNode(head-next); delete head;如果head-next最终回到head递归会无限加深最终栈溢出。正确做法是先断开环让head-next nullptr再进入递归。排查死循环时我的经验是不要光靠眼神直接打印遍历路径。在循环体内加一行输出cout cur-val endl;看它重复打印哪些值就能快速定位是哪条边出了问题。我一个同事排查过这种问题最后发现是删除节点后cur没有更新永远指向同一个节点日志里同一个数字刷刷刷打满屏幕。5.2 C 中 delete 的时机与 C 语言中 free 的时机C 和 C 语言操作循环链表删除时内存管理是一个必须认真对待的点。常见错误是删除节点后继续使用这个节点里的数据。看似无害一旦该内存被系统回收或复写就会出现诡异的数据错乱。正确做法是先摘链再释放。把prev-next更新完毕确认没有任何指针指向待删除节点后再调用delete或free。释放之后如果函数还要继续访问链表一定要通过新指针变量接手。Node* temp cur; prev-next cur-next; cur cur-next; delete temp; // 此时 temp 所指内存已释放还有个容易被忽略的点*释放后将指针置空确实是个好习惯但 C 语言的free和 C 的delete都不会帮你去掉其他副本指针的值。比如你有一个全局变量存了head指针当head指向的节点被删除后这个全局变量就成了野指针。所以在删除头节点后必须同步更新所有持有头指针的变量。这也是我在前面强调head用引用传递的原因。5.3 唯一节点的删除最容易忽略的判断当循环链表只有一个节点时它的next指向自己。删除这个节点时不能简单地执行prev-next cur-next因为这会把节点自己接回自己等于没删干净。标准做法是if (head-next head) { delete head; head nullptr; return; }这个判断在按值删除和清空链表中都必不可少。比如你要按值删除target5而整个链表只有一个值为 5 的节点这时候走到删除分支时如果不特判执行完prev-next cur-next之后链表会变成一个没有实际节点却能自我引用的空壳后续任何遍历和长度计算都会出错。5.4 清空整表的正确打开方式清空循环链表和单链表的思路也不一样。单链表可以直接从头开始挨个释放因为最终会遇到NULL。循环链表如果不做任何处理就直接从头开始删删到最后一个节点时需要判断且只能靠回到起点这个条件容易出错。我用一种比较清晰的写法先断开环把head-next置为nullptr这样循环链表就退化成了单链表然后用常规的单链表删除方式逐个释放节点。void clearList(Node* head) { if (head nullptr) return; // 断开环 Node* tail head; while (tail-next ! head) { tail tail-next; } tail-next nullptr; // 逐个释放 while (head ! nullptr) { Node* temp head; head head-next; delete temp; } }这个写法的好处是逻辑清晰断开环这个操作既完成了从环退化为线性的转换又使得后续的 while 循环不会死循环。我在实际项目里清理定时任务队列时都用这个写法稳定且好理解。5.5 一个通用的调试工具函数调试循环链表时我强烈建议写一个打印函数。很多 bug 靠肉眼是看不出来的把链表内容完整打一遍立刻能看到结构是否损坏。void printList(Node* head) { if (head nullptr) { cout empty endl; return; } Node* cur head; do { cout cur-val ; cur cur-next; } while (cur ! head); cout - (back to head-val ) endl; }打印的结果会以完整体现循环回到起点的方式呈现。如果在每次删除操作前后都调用这个函数对比前后状态基本不需要花太多时间就能找到问题出在哪。我在工程上还见过一种更省事的方式记录打印次数超过一定次数就强制停止避免死循环打爆日志。这个技巧在排查线上问题时很有用。\6. 循环链表删除的多种实现写法与对比6.1 迭代删除、递归删除、哨兵节点法按值删除、清空表这些操作不同的人有不同的实现偏好。最常见的三种分别是迭代法、递归法和带哨兵节点dummy node的方法。迭代法就是前面几节里反复展示的优势是直接、好理解、没有调用栈溢出风险。递归法在处理逆序操作或者树形结构延伸出的链表时比较优雅但在循环链表里递归必须在删除前先断开环否则递归永远无法返回。哨兵节点法则是给链表额外加一个哑节点让它的next指向真正的头节点这样删除头节点时也能统一走删除普通节点的逻辑不用特判头节点。这个技巧在很多链表算法题里非常好用特别是在删除头节点频繁的场景下。为了直观对比我写一个带哨兵节点的循环链表删除按值版本bool removeByValueWithDummy(Node* head, int target) { if (head nullptr) return false; // 创建哨兵节点使其 next 指向 head Node dummy(0); dummy.next head; Node* prev dummy; Node* cur head; Node* tail head; while (tail-next ! head) tail tail-next; tail-next dummy; // 临时让尾节点指向 dummy形成环路 bool found false; while (cur ! dummy) { if (cur-val target) { prev-next cur-next; Node* temp cur; cur cur-next; delete temp; found true; } else { prev cur; cur cur-next; } } // 恢复原结构找到新的头节点尾节点重新指向它 head dummy.next; tail head; while (tail-next ! dummy) tail tail-next; tail-next head; return found; }注意这个实现里临时把tail-next指向了dummy遍历终止条件是cur ! dummy这样所有节点包括原头节点都变成了普通节点无需特判。删除完成后再把tail-next指回新的头节点。整个过程比较绕但代码逻辑统一。6.2 各写法的适用场景建议从我的实际经验来看面试或者刷题推荐用哨兵节点法代码清晰不容易在头节点上翻车。工程项目推荐用迭代法直接明确后续同事 review 代码时不用猜测。链式操作复杂、需要回溯的场景可以少量使用递归但务必先断开环。内存极其受限的嵌入式环境不要递归用迭代法。三种写法没有哪个是绝对最好重要的是你对当前场景的判断。链表规模小、操作频率低怎么写都无所谓链表规模大、删除频繁就要特别注意时间复杂度和内存释放时机。\7. 扩展思考与实战心得7.1 多级循环链表与带头尾指针的循环链表循环链表在工业界并不罕见但很多时候不是教科书里那么简单地只有一个头指针。比如在某些缓存淘汰策略类似环形缓冲区中链表会额外维护tail指针方便从尾部直接定位。此时删除节点的逻辑要同时维护head和tail两个指针复杂度进一步上升。头尾指针同时存在的循环链表删除头节点后需要更新head如果被删的就是尾节点还得更新tail。这就比单头指针的循环链表多了一层判断。我在一个实时数据流处理模块里就维护过这样的环形队列每次删除节点都要反复确认head和tail是否被同时影响代码写得异常小心。7.2 并发环境下删除链表节点需要注意什么如果你的循环链表会被多个线程同时访问删除节点就不再是简单的指针操作了。经典的 ABA 问题在多线程环境下会特别致命某个线程 A 看到节点 X 准备删除线程 B 却先把它删了并把 X 的内存重新分配给一个新节点线程 A 再操作 X 时可能误删了一个全新的节点。这种情况下光有链表本身的逻辑正确还远远不够。一般有几种方案用锁保护整个删除操作代价是并发度大幅下降。用无锁链表的 CASCompare And Swap手法配合 hazard pointer 或 epoch-based reclamation 防止内存被提前回收。如果删除操作不频繁直接用一种标记删除的逻辑只把节点标记为删除不实际摘链后续某一轮统一清理。我的经验是不要一上来就搞无锁编程那是所有并发方案里调试成本最高的。普通业务场景下加一把互斥锁保护删除操作的临界区完全够用。只有在性能要求极其苛刻的地方才值得投入精力去设计无锁方案。7.3 最后再分享一个小技巧所有链表删除问题无论是单链表、双链表还是循环链表核心都是三件事找到目标、接好前后、释放内存。只不过循环链表多了一个圈的概念让这三件事里的每一件都需要多一点思考。我在给团队新人讲这个问题时都会让他们先画图把节点和next引用都画出来然后标出删除前后哪些指针需要改动。画完图再写代码错误率会直线下降。这个建议听起来朴素但它确实是我见过的大量删除循环链表节点实现里最有效的防错方式。别只盯着代码想一张图往往比十分钟白板推演管用得多。