看到“弗洛伊德判圈法”这个名字很多人第一反应是这又是一个要背下来的算法模板。但它背后那个证明简单得可以用一次跑步来概括。判圈法也叫龟兔赛跑算法核心就一句话在一条链式结构上用两个速度不同的指针同时往前跑如果存在环快指针迟早会追上慢指针。它能干三件实事判断链表有没有环、找到环的入口、算出环长。本文不打算给你堆一堆让人犯困的符号推导而是用“慢指针入环那一刻”的视角把这个算法为什么成立、怎么证明、怎么写代码、有哪些坑一次讲透。我第一次见到这个算法是在准备一场算法面试的时候当时被要求手写判定单链表是否有环的代码。哈希表的做法很容易想到一路走一路记见重复就说明有环。但面试官追了一句“能不能只用O(1)的空间”我当场就卡住了。后来翻开《算法导论》看到弗洛伊德判圈法这个名字感觉像是某个玄学定理。直到有一天我把一个具体链表的手算过程完整推了一遍才恍然大悟原来它并不玄甚至可以用一道小学数学题来解释。1. 判圈算法到底在干什么弗洛伊德判圈法Floyd’s Cycle Detection也叫龟兔赛跑算法本质是用两个速度不同的指针在线性结构上遍历。“慢指针”每次走一步“快指针”每次走两步。如果有环两者必然在环内的某个点相遇如果没有环快指针会先撞到链表末尾的空指针。它解决的问题通常被拆成三个层次问题输入输出典型场景是否有环判断链表/状态序列是否成环检测单链表环、死锁检测、循环依赖判断环的入口在哪返回入环的第一个节点LeetCode 142、系统依赖解析环长是多少输出环内节点数量状态机周期测量、缓存优化分析这里特别要强调“O(1)空间”意味着什么。哈希表法需要把走过的每个节点都存下来空间复杂度是O(n)链表越长占的内存越多。而判圈法只保留快慢两个指针无论链长到多少额外空间都是常数。这在嵌入式设备、流式数据、超大链表遍历这类场景里几乎是唯一可接受的做法。为什么同向跑圈一定会追上想象两辆摩托车在环形赛道上同向行驶慢车在前、快车在后只要赛道是环形的快车总会套圈追上慢车。难点在于链表的“赛道”不是一开始就进入环形而是先走一段直线非环部分再进入环形。要证明的其实就是“无论这段直线多长快车都能在进入环形之后追上慢车”并且“追上的一刻能反推出环形入口的位置”。2. 简单证明为什么快慢指针一定会相遇先约定三个记号。设链表的非环部分长度为L从链表头到环入口的节点数环的长度为C。慢指针入环时快指针已经在环内跑了片刻假设此时快指针领先慢指针a步这里“领先”指沿着前进方向从慢指针所在位置到快指针所在位置的距离。a的取值是0到C-1之间的整数。看一眼这个场景慢指针走到环入口用掉了L步。同样这L步内快指针走了2L步其中L步用来走到入口剩下的L步已经进入环内。所以快指针在环内跑了L步它对慢指针的领先距离就是a L mod C这里要小心一个边界情况如果L恰好是C的整数倍那么a等于0。这意味着慢指针到达入口的同一步快指针也绕完整数圈回到入口两个指针当场就相遇了。这个情况下x慢指针从入环到相遇走的步数就是0不需要再追。如果a不等于0那慢指针入环后快指针还在它前方a步。接下来就是一个简单的追及问题慢指针每走一步快指针走两步两者之间的距离每单位时间减少1步。要把这a步的差距抹平需要x C - a步。为什么是C减a而不是a因为这是个环形赛道快指针在前方a步处从慢指针的视角看追上它等于要绕过大半个环。比如环长10、快指针领先3步那么慢指针要走7步才能追上快指针快指针用这些时间多走了14步正好比慢指针多跑一圈多4步。把a代入就得到x C - (L mod C)这里如果出现负数按模C取正值即可。换句话说慢指针从进入环到第一次被追上一共走了x步而L加上x正好是C的整数倍。为什么这个性质重要因为稍后找环入口时靠的就是它。用一个具体链表验证一下。假设非环部分L3环长C5。慢指针走3步到达环入口。此时快指针已经多走了3步在环内领先慢指针3步a3。慢指针继续走追上需要C-a2步所以x2。两者第一次相遇的位置距离环入口2步。算一下Lx5确实是C的整数倍说明这个相遇点恰好满足“离入口x步”的规律。从复杂度角度再看这个证明的意义。慢指针走到入口最多L步入环之后最多再走C步就会被追上所以总步数不超过LC时间复杂度是O(LC)也就是O(n)。这从理论上保证了算法不会在环里无限绕圈快慢指针必然会在有限步内相遇。3. 第二次相遇为什么能找到环的入口判断有环不难难的是找到入口。判圈法第二阶段的口诀是第一次相遇后把快指针拉回链表头速度降成每次一步慢指针留在相遇点继续每次一步两者并肩前进下一次相遇的地方就是环入口。这个口诀我当年背得很熟但一直没想通为什么。直到把数字代进去手算了一遍。第一次相遇时慢指针走过的总步数是Lx快指针的总步数是它的两倍也就是2(Lx)。两者走过的路程差是Lx这个差必须是C的整数倍因为从入环到相遇快指针比慢指针多绕了若干整圈即L x kC现在第二阶段开始。快指针从链表头重新出发它走到环入口需要L步。慢指针从相遇点继续走L步。相遇点是在入口前方x步的位置慢指针再走L步后所在位置是“入口前方xL步”。因为xL是C的整数倍所以这个位置经过模C之后就是入口本身。同一时刻快指针也恰好走到入口。两个指针就在入口处重合。还需要回答一个更细的问题会不会在到达入口之前它们在中途就先遇上了这个可能性可以排除。第二阶段开始时快指针还停在链表头慢指针在环内两者不在同一条“赛道”上——快指针至少要走L步才能进入环。在快指针还没入环的那L-1步里它根本不可能跟慢指针相遇。而第L步它们就同时到达入口所以第一次重逢必然发生在入口。再看刚才的例子。L3、C5、x2。第一阶段相遇点在入口前2步处。第二阶段快指针从头部出发3步后到入口慢指针从相遇点出发走3步后位置是235模5后等于0恰好是入口。两者同时到达。更重要的是从这次相遇之后两个指针在环内相对静止速度一致、方向一致会一直同步走下去。这个“连体婴儿”的现象恰好是入口位置的直观证明。我在手推这个过程时最大的感触是找入口的算法本身很简单但它依赖的“xL是C的倍数”这个性质不是靠观察代码能看出来的必须从第一阶段的相遇条件反推。如果你只是背代码永远只能知其然把这一步推导写一遍才能彻彻底底理解。4. 算出环长别小看这个附带功能面试里最常见的是判环和找入口环长偶尔会作为追问出现。其实环长的计算比前两步都要简单证明甚至不需要动笔。方法一标记法。在第一次相遇点停下让其中一个指针不动另一个指针每次走一步计数器加1直到走回相遇点。因为相遇点在环内沿着单一方向前进走一圈回到原处时计数器的值就是环长C。方法二双指同速法。两个指针都在相遇点保持每次一步一起往前走。因为两个指针速度相同它们会一直保持相对静止直到走过一整圈后再次重合。这期间慢指针绕了整整一个环所以它走过的步数就是环长。至于为什么走一圈就能回到原处这是环形结构的定义属性单向环形链表上的任意节点沿着next指针不断前进经过C步后必定回到自身。这里不存在“走不止一圈”的疑问因为第一次回到自身时一定刚走完最小的正整数周期这个周期就是环的节点数。不过实际写代码时要注意区分两种需求。如果只需要判断是否有环那么只需要第一阶段如果需要找入口和环长则代码结构会有差异。还要留意找完入口之后原本的slow指针已经在入口处如果还要继续用这个链表做别的事通常需要额外记录一个临时指针。我在第一次手写这段逻辑时就吃过亏判断完环入口后直接返回了结果环长的计算没法复用之前的指针。5. 代码复现与复杂度分析先给一份完整的Python实现把判环、找入口、算环长三个功能放在一起。这个版本的思路是以可读性优先不追求极致的压缩写法。class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def has_cycle(head: ListNode) - bool: slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: return True return False def detect_cycle_start(head: ListNode) - ListNode: slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: # 第二阶段快指针拉回头部步长改为1 fast head while slow is not fast: slow slow.next fast fast.next return slow return None def cycle_length(head: ListNode) - int: slow, fast head, head while fast and fast.next: slow slow.next fast fast.next.next if slow is fast: # 停在相遇点让slow继续走计数直到回到原地 start slow count 0 while True: slow slow.next count 1 if slow is start: return count return 0这里有个容易忽略的细节while条件必须写成while fast and fast.next不能只判断fast。因为循环体内要访问fast.next.next如果fast.next本身是空直接取再下一个节点会抛出AttributeError。链表为空、只有一个节点、链尾接空这三种边界情况都会被这个条件挡掉。再看一个Go版本逻辑完全一致差别只在指针语法。Go在遍历中也要注意fast.Next是否为空判断条件跟Python的写法是同一个道理。日常工程里遇到链表的频率虽然不高但判圈法经常被用在状态图、缓存队列、事件循环这类结构上Go版本还是有参考价值的。type ListNode struct { Val int Next *ListNode } func hasCycle(head *ListNode) bool { slow, fast : head, head for fast ! nil fast.Next ! nil { slow slow.Next fast fast.Next.Next if slow fast { return true } } return false } func detectCycle(head *ListNode) *ListNode { slow, fast : head, head for fast ! nil fast.Next ! nil { slow slow.Next fast fast.Next.Next if slow fast { fast head for slow ! fast { slow slow.Next fast fast.Next } return slow } } return nil }复杂度这里单独说。空间复杂度是明摆着的O(1)全程只有两个指针变量。时间复杂度的推导在前面证明里已经覆盖慢指针走完非环部分需要L步入环后最多C步必然被追上所以第一阶段时间O(LC)。第二阶段快指针从头走到入口需要L步慢指针从相遇点走到入口也恰好L步这段距离等于非环部分长度时间同样是O(LC)。整个算法是线性的不会出现某些直觉以为的“在环里无限绕圈”的情况。6. 踩坑实录与经验总结第一个坑是空指针前面已经强调过。我在LeetCode上见过不少提交判环部分写的是while fast.next and fast.next.next看起来没问题但如果链表一开始就是个空链表fast本身就是None取fast.next直接报错。必须先从fast本身判空。第二个坑是“快指针每次走两步”这个设定。有人试过走三步、走四步理论上有环时最终也会追上但前提是速度差和环长的关系要合适否则可能出现快指针“跳过”慢指针之后两者永远错开的情况。两步走法的妙处在于速度差恰好是1可以让“追上”变成一个严格的每步逼近过程证明最干净也不会因为跳步产生非预期行为。我见过有人实际改过三步版本环长是奇数时会出现让人摸不着头脑的异常这种改动没有收益别折腾。第三个坑是边界案例链表无环时快指针会先到达nil两个指针永远不相遇环入口就在链表头时L0第一阶段第一次相遇就可能发生在入口第二阶段直接返回。我在写detect_cycle_start时用slow is not fast作为循环条件如果两个指针一开始就在同一个节点比如L0且环在头部循环体根本不会执行直接返回这棵树。如果不习惯用引用相等判断用值相等在同一链表里也可以工作但更稳妥的做法就是比较节点引用毕竟每个节点对象在内存里是唯一的。第四个坑是证明层面的混淆很多人把“快指针走2L步领先L步”这一句直接等同于“快指针走了L圈”这是错的。领先L步不等于领先L圈只有对C取模之后才知道快指针的相对位置。我第一次手算时就把L mod C写漏了结果怎么推都对不上“xL是C倍数”的结论。建议在纸上画一个小链表标上L3、C5把每个时刻指针位置写出来比看十遍公式都管用。最后说说我个人在实操中的体会。当初背这个算法始终觉得它是“别人证明过正确的结论”自己完全使不上力。直到有一天我用纸笔把慢指针入环时刻的位置算清楚才突然意识到判圈法本质上就是把一个在二维链表上的追踪问题化解成了一次时间轴上的追及问题。所谓“简单证明”关键就是先盯住慢指针入环的瞬间把快指针在环内的位置固定下来剩下的几步就是小学应用题。面试时遇到它与其对着范例默写代码不如边说边画把两个阶段的追及过程讲清楚说服力会强很多。这道题打磨透之后我还顺手把它用在了日志循环检测和任务依赖环的判断上确实是个放在工具包里很趁手的通用武器。