1. 先说结论弗洛伊德判圈法到底是什么如果你刷过链表相关的算法题大概率遇到过这类问题判断一个单链表有没有环甚至要找出环的入口节点。稍加搜索你会发现十个人里有九个会提到“弗洛伊德判圈法”英文是Floyds Cycle Detection还有个更形象的名字叫“龟兔赛跑算法Tortoise and Hare”。弗洛伊德判圈法的思路简单到可以用一句话概括一个慢指针每次走一步一个快指针每次走两步如果链表中存在环那么这两个指针在进入环之后必然会相遇如果无环快指针会先一步到达链表末尾。这个算法最吸引人的地方不是它有多么精巧的数据结构而是它只需要常数额外空间时间复杂度为O(n)工程价值和面试考察价值都很高。但我在接触这个算法的初期心里一直有个疙瘩大家都会背代码知道快慢指针会相遇但几乎没有几个人能说清楚“为什么一定会相遇”“为什么相遇之后再把一个指针放回头结点两个指针同步走就能找到环的入口”。网上很多文章要么直接甩结论要么堆了一堆看不懂的数学符号。这篇东西就是把这两个“为什么”彻底掰开揉碎用最直观的追及问题比喻加严格的同余推导把证明讲透再附上完整的C实现和我在实际写代码时踩过的坑。适合谁看如果你正在准备算法面试或者刷LeetCode时遇到了环形链表系列题目又或者你只是单纯想知道这个经典算法背后的数学原理这篇文章都能给你一个满意的交代。不需要你有多深的数学底子只要你认识“取模”和“同余”这两个概念剩下的跟着推导一步步走就行。2. 为什么快慢指针必然相遇第一次数学推演2.1 把链表想象成环形操场要理解弗洛伊德判圈法第一步不是看代码而是建立一个物理画面。把链表里的直线部分想象成一条通往操场的走廊把环想象成环形跑道。慢指针和快指针从同一起点出发慢指针速度是1快指针速度是2。走廊部分没有任何悬念快指针始终在慢指针前面两人都往操场方向跑。只要链表有环快指针一定先进入操场。关键问题是快指针进入操场之后它并没有停在那里等慢指针而是一直以2倍速度在环形跑道上绕圈。等慢指针终于进入操场时快指针已经不知道在跑道上绕了多少圈了。这时候问题变成了两个物体都在同一个环形跑道上运动一个速度是1一个速度是2而且快物体就在慢物体前方某个位置。快物体能不能追上慢物体答案是必然能。因为在环形跑道上追及的本质是相对距离的减少。每单位时间里快物体相对慢物体前进1个单位距离而环形跑道的总长度是有限的所以经过有限时间两者必然相遇。这个直觉其实就是整个算法正确性的第一层证明。它告诉我们相遇一定发生在环内而不是直线部分相遇是必然事件不是概率事件。2.2 严格的数学证明相对距离按1递减直觉归直觉面试时如果只画个操场示意图面试官通常不会满意你要给出更严谨的说法。设环的长度为L。慢指针刚进入环的瞬间把它记作时刻t0。此时快指针已经在环内某个位置上。从环的入口节点开始顺时针数快指针距离入口的距离为dd是一个介于0到L-1之间的整数。从t0开始每个单位时间慢指针走1步快指针走2步。也就是说快指针相对于慢指针每个单位时间多走1步。在环上从慢指针的视角看快指针每单位时间靠近自己1个节点。两者初始的相对距离沿着运动方向快指针追上慢指针需要跨越的节点数不会超过L。因为每单位时间这个相对距离严格减少1所以在不超过L个单位时间之后快指针必然会与慢指针重合。这个证明比直觉层面的“操场追及”要强得多因为它把“必然相遇”量化了从慢指针入环那一刻算起最多再走L步两人必遇。这也就是为什么这个算法不会死循环不会出现快指针恰好总是跳过慢指针的诡异情况。后面我会专门讨论“快指针走3步行不行”的问题到时候你会发现走2步之所以能被选为默认方案恰恰是因为这个“相对距离按1递减”的性质发挥了决定性作用。2.3 为什么快指针每次走两步而不是三步这是个极具技术含量的追问也是很多面试者真正露馅的地方。既然每次多走一步能保证追上那把快指针速度从2改成3相对速度变成2不是追得更快么听上去有道理但结论会让你意外快指针每次走3步在某些环结构下永远不会与慢指针相遇。原因在于快指针一次移动3步本质上跳过了中间两个节点到达第三个节点。从“追上”的角度看快指针和慢指针都在离散的节点上移动快指针相对慢指针的位置变化速率是2。设相遇条件需要存在某一时刻t使得两者位置关于环长相一致。用数学表达就是快慢指针的相对距离在时刻t时为d 2t模L。要让它们相遇就需要d 2t ≡ 0 (mod L)也就是方程2t ≡ -d (mod L)有解。这个方程有解的充要条件是2与L的最大公约数能整除d。如果环长L是偶数而初始距离d是奇数那么2t ≡ -d (mod L)永远无解两个指针会在环上永远错开一个走奇数位一个走偶数位形成“鬼打墙”。这恰好体现了快指针每次走2步的得天独厚之处相对速度k-1等于11与任意环长L的最大公约数都是1方程t ≡ -d (mod L)必有解因此相遇是绝对必然的。这个性质不是偶然而是“速度差为1”带来的同余保证。理解了这一点你对弗洛伊德判圈法的信任就不再是背诵而是内化成了自己的判断力。从复杂度角度看快指针走2步也是最平衡的。走3步虽然单次追赶幅度大但破坏了必相遇性走1步则永远追不上走2步则同时兼顾匹配效率与确定性。所以在面试里如果有人问你“能不能走3步”你不仅要回答“可以但可能要额外讨论初始距离和环长不能保证必遇”还要能举出反例说明这才是真正吃透了算法。3. 环的入口哪里找等式的魔术3.1 从相遇点到入口的距离推导能判断有环只是阶段一找出环的入口才是完整闭环。面试题里最常见的就是“返回链表开始入环的第一个节点”LeetCode第142题。很多解法在这里给出了一个近乎“魔法”的操作第一次相遇后让一个指针从头节点出发另一个指针留在相遇点两个指针均以速度1继续走它们再次相遇的位置就是环的入口。但这个操作凭什么成立这才是整个算法中最精彩的部分。我们从数学上把它推一遍。约定几个符号a链表头节点到环入口节点的距离也就是直线部分的节点数。b慢指针进入环后从环入口走到与快指针相遇位置的步数。L环的长度。慢指针和快指针同时从链表头出发。由于两者运动时间相同而快指针速度是慢指针的2倍所以相遇时快指针走过的总路程是慢指针的2倍。慢指针总共走的距离是a b。快指针总共走的距离呢它同样先走了a然后进入环内绕圈。第一次相遇时它除了走过和慢指针相同的a b之外还额外多绕了若干圈。设多绕的圈数为n则快指针总路程为a b nL。由“快指针路程 2 × 慢指针路程”可得a b nL 2(a b)化简得到a b nL这就是整个推导的胜负手。它说明头节点到相遇点的距离恰好是环长的整数倍。这句话请圈起来后面所有结论都从这里长出。3.2 同余式与证明的精髓把a b nL稍作变形a nL - b (n - 1)L (L - b)这里L - b的意思是从相遇点出发沿着环继续走到达环入口还需要走的步数。为什么因为相遇点在环上的位置是b从环入口顺时针数过来第b个节点绕完一整圈需要L步已经走了b步剩下部分就是L - b步。这个等式的含义很深刻。头节点到入口的距离a与“从相遇点到入口的距离L - b”之间只差整数个环长。换句话说在模L的意义下a ≡ L - b (mod L)或者说a ≡ -b (mod L)。正是因为这个同余关系当你把一个指针放回头节点、另一个指针留在相遇点同时都开始以速度1前进时从头节点出发的指针走a步后抵达环入口而从相遇点出发的指针也走a步它走过的路程为(n - 1)L (L - b)等价于绕了n - 1圈之后又从相遇点走了L - b步来到环入口。两者在同一时刻出现在同一个节点——环入口。这个证明的精髓在于它把几何结构转化为算术结构。链表是线性的环是周期的周期性天然适合用模运算描述。一旦算出a nL - b前面那个“乖张”的同向同步走操作就变得顺理成章没有任何魔法成分。3.3 慢指针会不会在环里绕很多圈一个配套的小问题也经常被追问慢指针进入环之后会不会已经被快指针追了很多圈它是否可能绕了好几圈之后才被追上按照弗洛伊德判圈法的设定慢指针速度是1快指针速度是2两者相对速度是1。前面已经证明从慢指针进入环的瞬间起快指针最多再走L步就能追上慢指针。而L步正好是慢指针绕环一整圈的路程。也就是说慢指针在环内走过的路程不会超过一个完整的环长它在第一次相遇前最多绕环不到一圈。这个结论非常实用它保证了上一节推导中“b”这个变量有一个明确且紧凑的语义b是慢指针进入环后在第一次相遇前实际走过的步数并且0 ≤ b L。如果慢指针可能在环里绕了很多圈推导虽然依然成立但“L - b”作为“从相遇点到入口的距离”的直观解释就会被削弱。正是由于慢指针最多绕一圈整个等式的几何意义才格外清晰。知道这个还能顺带推出一个边界情形如果环很小比如只有2个节点快指针可能早就绕了很多圈在那里等慢指针但无论如何第一次相遇时慢指针的行程依然被约束在“入环后最多一圈”内。这为后面的代码实现提供了理论保障也让我在写边界测试用例时心里有底。4. C实现与关键代码注释4.1 判圈功能hasCycle的完整实现理论推完了接下来是落地。判断链表是否有环用弗洛伊德判圈法写起来非常短但越短的代码越要在意细节。直接看实现struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(nullptr) {} }; bool hasCycle(ListNode *head) { if (head nullptr || head-next nullptr) { return false; } ListNode *slow head; ListNode *fast head; // 快指针每次走两步必须先确认当前节点和下一节点都不为空 while (fast ! nullptr fast-next ! nullptr) { slow slow-next; // 慢指针走一步 fast fast-next-next; // 快指针走两步 if (slow fast) { return true; // 相遇必然是有环 } } return false; // 快指针到达末尾无环 }这段代码的核心逻辑只有一步快慢指针同步移动相遇即返回true。循环的终止条件要格外注意while (fast ! nullptr fast-next ! nullptr)保证了在访问fast-next-next之前fast-next一定存在。如果把条件写成while (fast-next ! nullptr)在无环链表的最后一个节点上就会对空指针解引用直接崩溃。这种错误在本地测试时很可能因为链表长度刚好够而侥幸通过一旦遇到边界用例就原形毕露。初始化时两个指针都从头节点出发而不是快指针从head-next出发。这是为了保持“同一起点、快慢恒定”的运动学模型也让后续找环入口的第二次遍历可以直接复用同一套位置关系避免斜门歪路的边界处理。如果你看到某些早期教程让快指针初始化为head-next那通常是早年为了避开“慢指针等于快指针初始相等”这种讨论而做的变体但标准做法就是都从头开始逻辑更干净。4.2 找环入口detectCycle的完整实现判环只是热身找入口才是完整解法。基于前面第三部分的数学推导实现起来就是第一次找相遇点第二次同步走ListNode *detectCycle(ListNode *head) { if (head nullptr || head-next nullptr) { return nullptr; } ListNode *slow head; ListNode *fast head; // 第一轮快慢指针相遇 while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) { break; } } // 如果循环是因为快指针走到了末尾说明无环 if (fast nullptr || fast-next nullptr) { return nullptr; } // 第二轮一个指针放回头节点另一个留在相遇点同步走 slow head; while (slow ! fast) { slow slow-next; fast fast-next; } return slow; // 再次相遇的位置就是环入口 }注意第二轮循环里有一个容易被忽略的边界如果环的入口恰好就是链表头节点那么slow head之后slow和fast已经指向了同一个节点直接跳过循环返回即可。这就是为什么在进入第二轮之前要把slow重新赋值为head而不是把它留在相遇点上再来回折腾。很多人在写第二步时犹豫“到底该把哪个指针放回头节点”答案是都可以代码里通常把slow放回头节点fast留在相遇点两者逻辑对称选一种固定下来就好。还有一点很关键第二轮循环不需要再判断空指针。因为第一轮已经确认了链表有环所以fast和slow在环内永远不会指向空节点循环一定会在某个节点终止。写这类代码时明确“哪些阶段依赖前面的结论”能帮你省掉很多无谓的空指针检查也让代码的层次感更清晰。4.3 边界条件与复杂度分析边界条件看似简单但每一行都有讲究我把它们单独拎出来说空链表head为nullptr直接返回false或nullptr不用进入任何循环。单节点链表无环且head-next为nullptr直接返回。全链表无环快指针会率先走到链表末尾循环条件判定为假后自然退出返回false。环长度为1也就是某个节点的next指向自己此时快慢指针都会陷入环内第一次循环就能相遇。头节点就是环入口第二轮循环开始前slow被重置为headfast也正好处于head因为相遇点就是入口直接返回入口节点。从时间复杂度角度看第一轮循环中慢指针入环后最多走L步就会被追上而入环前它最多走a步因此第一轮的时间上界为O(a L) O(n)。第二轮循环里从头节点出发的指针最多走a步到达入口因此这一轮也是O(n)。总体时间复杂度为O(n)空间复杂度为O(1)全程只用到了两个指针变量没有借助哈希表或额外数组。这里也顺带对比一下另一种常见解法——哈希表法。用一个集合记录访问过的节点每走一步检查一次当前节点是否已经在集合中。哈希表法的时间复杂度同样是O(n)但空间复杂度为O(n)。当链表规模达到百万级甚至更高时哈希表的额外内存开销就会成为不可忽视的负担。弗洛伊德判圈法之所以在工程和面试中地位很高正是因为它在同样线性时间内做到了常数空间。5. 常见问题与排查心得5.1 高发问题速查表在亲手写了无数遍这道题、也帮不少朋友 review 过代码之后我把最高发的问题整理成了一张速查表方便你写代码时对照症状原因修正办法无环链表上运行时出现空指针异常循环条件没检查fast-next写成while (fast fast-next)有环链表上运行超时快指针也被初始化成head-next导致两个指针永远错开某个相位将快慢指针统一初始化为head有环但判不出环循环条件写成了while (slow ! fast)初始状态slow fast直接跳过用do-while结构或先移动再判断detectCycle返回值是空指针判断无环条件的写法错误比如只判断fast nullptr同时判断fast nullptr和fast-next nullptr第二轮循环死循环忘记把某个指针重置回头节点在进入第二轮前执行slow head其中“初始状态slow fast直接跳过”这个坑比较隐蔽。如果你把循环写成while (slow ! fast)然后每次循环结束才更新指针那么初始化时两者都在head循环体一次都不会执行直接返回错误结果。正确的姿势是使用while (true)加内部判断或者先移动再比较再或者干脆用do-while循环。我在代码里采用的就是“循环内先移动再比较”的写法天然规避了这个问题。5.2 面试追问的三种打开方式面试官考察这道题通常不会止步于“默写代码”。下面几个追问我在不同场合都被问到过也推荐你在准备时主动演练第一问如果快指针走三步能保证相遇吗答案是不能保证。前面已经推导过方程d 2t ≡ 0 (mod L)是否有解取决于d与L的整除关系。举例来说环长为6初始距离为1那么d是不可被gcd(2,6)2整除的两个指针永远错开。能答到这里基本就能把面试官镇住。第二问第一次相遇时慢指针一共走了多少步精确值很难直接给出因为它依赖链表和环的具体结构但上界是可以确定的慢指针从head走到入环点需要a步入环后最多再走不到一圈L步。所以慢指针总步数不超过a L这也是算法复杂度O(n)的直接来源。第三问为什么第二次相遇点一定是环入口面试官想听的其实就是那个等式a nL - b。你要能顺势说出从头节点出发的指针走a步到入口而从相遇点出发的指针走同样步数等价于绕了n-1圈后又走了L-b步两者在同一时刻出现在同一位置。把数学表达清楚比什么都更有说服力。这三问如果全部答对大概率说明你不是背答案而是真正理解了这个算法背后的同余思想。这种理解深度恰恰是算法面试中区分“刷题机器”和“有真实功底”的分水岭。5.3 我在工程代码里踩过的坑说点实在的。理论一套套真正把弗洛伊德判圈法写进工程代码时依然有几个坑值得单独拿出来讲。第一个坑是内存安全检查的顺序。在实际项目里链表节点往往不是LeetCode那种干净的结构可能是共享内存对象可能是侵入式链表节点的生命周期管理非常脆弱。你不能假设fast-next-next这个访问一定安全要先在整型语义上判断fast fast-next再往后推进。这个顺序不能乱一乱就是空指针解引用轻则段错误重则崩溃影响线上服务。第二个坑是结构体指针比较的语义。在C里slow fast比较的是指针地址而不是节点内容。如果你在调试时打印两个节点看到的val值一样但指针不相等就说明你还不在同一个节点上。写测试用例时很多人习惯构造若干值相同的节点结果误判算法有问题其实是自己构造的环结构不对。第三个坑是修改链表结构的影响。弗洛伊德判圈法本身不修改链表但如果你在检测完之后做其他操作比如删除节点、改变next指向就必须重新评估指针的有效性。我在一个缓存淘汰模块里用过这个算法做环检测因为误以为“检测完链表还是原来的链表”结果某次清理操作把快慢指针指向的节点释放了后面再用就踩了悬空指针。记住算法不修改结构不代表你可以在检测过程中安全地修改结构特别是当你有并发写线程时这种裸指针遍历需要配合锁或版本号机制。第四个坑是非C语言里的引用问题。在Java里slow head只是重新赋值引用不会影响原链表在Python里同样如此。但在C里如果指针用的是智能指针赋值操作会涉及引用计数的增减虽然不影响逻辑正确性但会影响性能尤其是循环检测频繁触发时。所以我在C工程里通常优先用裸指针加明确的作用域把生命周期管理隔离在外面。最后再分享一个我自己测试时常用的“歪招”想验证算法在不同的环大小下都正确我写了一个随机生成链表的工具不断改变直线部分长度a和环部分长度L跑一次判圈和找入口然后用哈希表方法的结果做交叉验证。这种双实现互相校验的测试方式帮我抓出过好几个脑洞大开的边界bug。如果你也打算在生产代码里用这个算法强烈建议写一个类似的差分测试脚本成本很低但收益巨大。这个算法教会我的一个通用道理是很多看似奇妙的算法操作背后都藏着一个漂亮的数学结构。如果你只是背下代码遇到变体就会发怵如果你理解了它背后的同余关系那无论是判断链表有环、寻找环入口还是延伸到检测数组循环、判断重复数据你都能第一时间意识到“这里可以用弗洛伊德判圈法”。我后来在好几个完全不同的工程场景里复用同一种思路每次都能很快定位问题靠的并不是记忆力而是理解了它“等价于在周期性结构上寻找碰撞”的本质。
