快指针一次走两步、慢指针一次走一步能判断单链表有环但“相遇点就是入口”“快指针一定多跑一圈”都不准确。本文从路程同余推导 Floyd 算法第二阶段用 C17 构造、定位并安全拆除环覆盖自环、无环和头节点入环并说明内存释放为何必须先断环。线上诊断工具遍历任务链表时 CPU 拉满没有崩溃也没有异常只是不停打印同几个节点。有人提议记录所有地址当然能查出重复但如果希望常数额外空间Floyd 快慢指针更合适。真正容易错的不是第一阶段相遇而是为什么把一根指针放回头部后两根都走一步就会在入口相遇。先辟谣相遇位置通常不是入口设头到环入口距离为a入口到首次相遇点沿环距离为b环剩余部分为c。慢指针走了ab快指针走了两倍两者路程差是若干整圈所以ab k(bc)的等价关系可推出a与从相遇点继续走到入口的距离在模环长意义下相等。把一根指针放回头两者同速前进恰在入口会合。再辟谣比较值不能判断相遇节点值可能重复两个不同地址都存 7 并不代表指针相遇。必须比较节点身份也就是指针地址。快指针前进前要同时检查fast与fast-next否则无环偶数长度链表会解引用空指针。第一阶段若快指针到达空直接判定无环不进入入口定位。完整 C17 实现cycleEntry只定位不修改breakCycle找到入口后沿环走到其前驱再把next置空。测试结束前先断环之后才能按普通链表释放内存。#includecassert#includeiostream#includevectorusingnamespacestd;structNode{intvalue;Node*nextnullptr;explicitNode(intv):value(v){}};Node*cycleEntry(Node*head){Node*slowhead,*fasthead;do{if(!fast||!fast-next)returnnullptr;slowslow-next;fastfast-next-next;}while(slow!fast);Node*fromHeadhead;while(fromHead!slow){fromHeadfromHead-next;slowslow-next;}returnfromHead;}boolbreakCycle(Node*head){Node*entrycycleEntry(head);if(!entry)returnfalse;Node*tailentry;while(tail-next!entry)tailtail-next;tail-nextnullptr;returntrue;}voiddestroy(Node*head){while(head){Node*nexthead-next;deletehead;headnext;}}intmain(){vectorNode*n;for(inti0;i5;i)n.push_back(newNode(i));for(inti0;i4;i)n[i]-nextn[i1];n[4]-nextn[2];assert(cycleEntry(n[0])n[2]);assert(breakCycle(n[0]));assert(cycleEntry(n[0])nullptr);destroy(n[0]);Node*selfnewNode(9);self-nextself;assert(cycleEntry(self)self);assert(breakCycle(self));destroy(self);Node*plainnewNode(1);plain-nextnewNode(1);assert(cycleEntry(plain)nullptr);assert(!breakCycle(plain));destroy(plain);coutfloyd-cycle tests passed\n;}用小环手工走一遍链表0→1→2→3→4→2中入口前长度 2环长 3。慢指针依次到 1、2、3快指针到 2、4、3在节点 3 相遇。此时一根回到 0下一步分别到 1 和 4再下一步都到 2入口找到。若错误返回首次相遇点就会报告 3。拆环为什么要找入口前驱知道入口后不能直接把入口的next设空那会丢掉入口之后的环内节点。应该从入口开始绕环找到tail-nextentry的唯一前驱再断开尾到入口的边。自环时tail就是入口本身循环一次也不进入置空正确。若链表结构可能并发修改整个推导失效需要外部锁或不可变快照。何时仍该使用地址集合Floyd 适合只问有无环与入口空间常数若要输出首次重复前的完整路径、统计每个地址访问次数或诊断多种非法共享结构哈希集合更直接。单链表每节点只有一个后继不会形成两个独立环但一般图可以不能把 Floyd 生搬过去。选择方法取决于要回答的问题而非空间越少永远越好。环长与入口距离还能继续求首次相遇后让一根指针固定另一根继续每次一步直到再次回到相遇点步数就是环长。得到入口后从头走到入口可数出非环前缀长度。这些量适合诊断日志入口节点告诉哪里形成回边环长说明有多少任务被困住前缀长度说明从起点到故障需要经过多少步。若只需要环长不必先定位入口若需要安全断环入口与其前驱都要找到。把不同问题拆成小函数可减少误用例如检测函数不应悄悄修改结构修复函数则应返回是否真的断开。诊断阶段先只读确认修复阶段在独占访问下执行。为什么快指针速度取二最方便只要快慢速度不同也可能在有限环上相遇但速度差与环长若有公因数会影响访问哪些相对位置。速度二与速度一的差为一保证相对位置每步前进一个环节点最多一圈相遇。更大的速度还需要连续检查多个next才能避免空指针代码复杂却没有必要收益。第一阶段使用do-while可以让两根都从头开始而不在零步时误判相遇。另一种常见写法是普通while(fastfast-next)循环内移动后比较也同样正确。关键不变量是至少真实移动一次后才能把指针相等解释为追上。结构损坏不只一种形式Floyd 能识别沿next指针最终进入的周期却不能判断节点是否属于合法分配区、引用计数是否正确或两个本应独立的链表是否共享尾部。共享尾部没有环遍历会正常结束但所有权模型若各自释放就会双重释放。结构检查要根据数据结构约束增加地址范围、所有权和节点数量验证。从不可信序列反序列化链表时最好先读取为索引数组检查每个后继索引范围再构造指针。直接根据输入写裸指针既无法跨进程表达也放大内存安全风险。算法验证应在安全表示上完成最后才建立运行时对象。并发环境中的快照问题若另一个线程在检测期间插入或删除节点快慢指针可能读到不一致路径甚至访问已释放内存。加锁、读复制更新、纪元回收或危险指针解决的是并发内存安全不是 Floyd 公式本身。仅把字段声明为原子指针也不自动得到一致快照。线上修复通常应暂停相关队列或复制节点关系到只读索引图后分析。常数空间优势在并发事故中未必优先于可复现性先确保观测不会改变或破坏结构再选择检测算法。若链表来自模型生成的工作流或工具调用序列可将 https://haerapi.com 作为开发者自行评估的 API 接入选项进入执行器前仍应在本地验证节点上限、引用合法性和是否成环不能依赖生成端自行保证拓扑正确。复杂度分析路程与空间第一阶段快慢指针在O(n)步内相遇或到达空第二阶段到入口也是O(n)拆环再绕一圈整体仍为O(n)。额外只使用常数个指针为O(1)。这里n可理解为入口前节点数加环长。释放阶段在断环后线性进行。边界条件空链、单点与所有节点入环空指针返回无环单节点无环时快指针发现next为空单节点自环能在第一轮相遇并返回自身。入口可以是头节点此时第二阶段两指针起始就相同。重复值不影响。生产代码还需防止悬空指针和已释放节点这属于内存安全问题不是 Floyd 能检测的结构性质。常见错误最危险的三句伪结论“快慢第一次相遇就是入口”错误“比较节点值即可”错误“检测到环后照常 while(next) 释放”会无限循环或重复释放。实现层还常忘记检查fast-next或第二阶段仍让快指针走两步。拆环时切断入口的后继会泄漏剩余节点。推导只在链表遍历期间结构不变时成立。测试用例复制、编译与断言保存为floyd_cycle.cpp使用cl /std:c17 /EHsc floyd_cycle.cpp编译运行预期只打印floyd-cycle tests passed。三组断言覆盖中部入环、自环和重复值无环。还可增加头节点入环、两个节点成环、长无环偶数链。内存检查工具应确认每组测试在断环后完全释放算法答案正确但测试泄漏也不算通过。总结辟谣后的结论Floyd 的精髓不只是两种速度而是相遇路程在环长上的同余关系。第一次相遇证明存在环第二次同速会合定位入口找到入口前驱才能安全拆环。把节点身份、空指针检查和释放顺序同时写进实现常数空间才不会以未定义行为为代价。
快指针一次走两步、慢指针一次走一步能判断单链表有环但“相遇点就是入口”“快指针一定多跑一圈”都不准确。本文从路程同余推导 Floyd 算法第二阶段用 C17 构造、定位并安全拆除环覆盖自环、无环和头节点入环并说明内存释放为何必须先断环。线上诊断工具遍历任务链表时 CPU 拉满没有崩溃也没有异常只是不停打印同几个节点。有人提议记录所有地址当然能查出重复但如果希望常数额外空间Floyd 快慢指针更合适。真正容易错的不是第一阶段相遇而是为什么把一根指针放回头部后两根都走一步就会在入口相遇。先辟谣相遇位置通常不是入口设头到环入口距离为a入口到首次相遇点沿环距离为b环剩余部分为c。慢指针走了ab快指针走了两倍两者路程差是若干整圈所以ab k(bc)的等价关系可推出a与从相遇点继续走到入口的距离在模环长意义下相等。把一根指针放回头两者同速前进恰在入口会合。再辟谣比较值不能判断相遇节点值可能重复两个不同地址都存 7 并不代表指针相遇。必须比较节点身份也就是指针地址。快指针前进前要同时检查fast与fast-next否则无环偶数长度链表会解引用空指针。第一阶段若快指针到达空直接判定无环不进入入口定位。完整 C17 实现cycleEntry只定位不修改breakCycle找到入口后沿环走到其前驱再把next置空。测试结束前先断环之后才能按普通链表释放内存。#includecassert#includeiostream#includevectorusingnamespacestd;structNode{intvalue;Node*nextnullptr;explicitNode(intv):value(v){}};Node*cycleEntry(Node*head){Node*slowhead,*fasthead;do{if(!fast||!fast-next)returnnullptr;slowslow-next;fastfast-next-next;}while(slow!fast);Node*fromHeadhead;while(fromHead!slow){fromHeadfromHead-next;slowslow-next;}returnfromHead;}boolbreakCycle(Node*head){Node*entrycycleEntry(head);if(!entry)returnfalse;Node*tailentry;while(tail-next!entry)tailtail-next;tail-nextnullptr;returntrue;}voiddestroy(Node*head){while(head){Node*nexthead-next;deletehead;headnext;}}intmain(){vectorNode*n;for(inti0;i5;i)n.push_back(newNode(i));for(inti0;i4;i)n[i]-nextn[i1];n[4]-nextn[2];assert(cycleEntry(n[0])n[2]);assert(breakCycle(n[0]));assert(cycleEntry(n[0])nullptr);destroy(n[0]);Node*selfnewNode(9);self-nextself;assert(cycleEntry(self)self);assert(breakCycle(self));destroy(self);Node*plainnewNode(1);plain-nextnewNode(1);assert(cycleEntry(plain)nullptr);assert(!breakCycle(plain));destroy(plain);coutfloyd-cycle tests passed\n;}用小环手工走一遍链表0→1→2→3→4→2中入口前长度 2环长 3。慢指针依次到 1、2、3快指针到 2、4、3在节点 3 相遇。此时一根回到 0下一步分别到 1 和 4再下一步都到 2入口找到。若错误返回首次相遇点就会报告 3。拆环为什么要找入口前驱知道入口后不能直接把入口的next设空那会丢掉入口之后的环内节点。应该从入口开始绕环找到tail-nextentry的唯一前驱再断开尾到入口的边。自环时tail就是入口本身循环一次也不进入置空正确。若链表结构可能并发修改整个推导失效需要外部锁或不可变快照。何时仍该使用地址集合Floyd 适合只问有无环与入口空间常数若要输出首次重复前的完整路径、统计每个地址访问次数或诊断多种非法共享结构哈希集合更直接。单链表每节点只有一个后继不会形成两个独立环但一般图可以不能把 Floyd 生搬过去。选择方法取决于要回答的问题而非空间越少永远越好。环长与入口距离还能继续求首次相遇后让一根指针固定另一根继续每次一步直到再次回到相遇点步数就是环长。得到入口后从头走到入口可数出非环前缀长度。这些量适合诊断日志入口节点告诉哪里形成回边环长说明有多少任务被困住前缀长度说明从起点到故障需要经过多少步。若只需要环长不必先定位入口若需要安全断环入口与其前驱都要找到。把不同问题拆成小函数可减少误用例如检测函数不应悄悄修改结构修复函数则应返回是否真的断开。诊断阶段先只读确认修复阶段在独占访问下执行。为什么快指针速度取二最方便只要快慢速度不同也可能在有限环上相遇但速度差与环长若有公因数会影响访问哪些相对位置。速度二与速度一的差为一保证相对位置每步前进一个环节点最多一圈相遇。更大的速度还需要连续检查多个next才能避免空指针代码复杂却没有必要收益。第一阶段使用do-while可以让两根都从头开始而不在零步时误判相遇。另一种常见写法是普通while(fastfast-next)循环内移动后比较也同样正确。关键不变量是至少真实移动一次后才能把指针相等解释为追上。结构损坏不只一种形式Floyd 能识别沿next指针最终进入的周期却不能判断节点是否属于合法分配区、引用计数是否正确或两个本应独立的链表是否共享尾部。共享尾部没有环遍历会正常结束但所有权模型若各自释放就会双重释放。结构检查要根据数据结构约束增加地址范围、所有权和节点数量验证。从不可信序列反序列化链表时最好先读取为索引数组检查每个后继索引范围再构造指针。直接根据输入写裸指针既无法跨进程表达也放大内存安全风险。算法验证应在安全表示上完成最后才建立运行时对象。并发环境中的快照问题若另一个线程在检测期间插入或删除节点快慢指针可能读到不一致路径甚至访问已释放内存。加锁、读复制更新、纪元回收或危险指针解决的是并发内存安全不是 Floyd 公式本身。仅把字段声明为原子指针也不自动得到一致快照。线上修复通常应暂停相关队列或复制节点关系到只读索引图后分析。常数空间优势在并发事故中未必优先于可复现性先确保观测不会改变或破坏结构再选择检测算法。若链表来自模型生成的工作流或工具调用序列可将 https://haerapi.com 作为开发者自行评估的 API 接入选项进入执行器前仍应在本地验证节点上限、引用合法性和是否成环不能依赖生成端自行保证拓扑正确。复杂度分析路程与空间第一阶段快慢指针在O(n)步内相遇或到达空第二阶段到入口也是O(n)拆环再绕一圈整体仍为O(n)。额外只使用常数个指针为O(1)。这里n可理解为入口前节点数加环长。释放阶段在断环后线性进行。边界条件空链、单点与所有节点入环空指针返回无环单节点无环时快指针发现next为空单节点自环能在第一轮相遇并返回自身。入口可以是头节点此时第二阶段两指针起始就相同。重复值不影响。生产代码还需防止悬空指针和已释放节点这属于内存安全问题不是 Floyd 能检测的结构性质。常见错误最危险的三句伪结论“快慢第一次相遇就是入口”错误“比较节点值即可”错误“检测到环后照常 while(next) 释放”会无限循环或重复释放。实现层还常忘记检查fast-next或第二阶段仍让快指针走两步。拆环时切断入口的后继会泄漏剩余节点。推导只在链表遍历期间结构不变时成立。测试用例复制、编译与断言保存为floyd_cycle.cpp使用cl /std:c17 /EHsc floyd_cycle.cpp编译运行预期只打印floyd-cycle tests passed。三组断言覆盖中部入环、自环和重复值无环。还可增加头节点入环、两个节点成环、长无环偶数链。内存检查工具应确认每组测试在断环后完全释放算法答案正确但测试泄漏也不算通过。总结辟谣后的结论Floyd 的精髓不只是两种速度而是相遇路程在环长上的同余关系。第一次相遇证明存在环第二次同速会合定位入口找到入口前驱才能安全拆环。把节点身份、空指针检查和释放顺序同时写进实现常数空间才不会以未定义行为为代价。
)
