刷题的时候碰到“求环(回路)长度”这个标题我第一反应是LeetCode第142题那一类问题链表里有没有环环有多长。但真到了实际编码里你会发现这个概念被问得五花八门——有的是让返回环起点有的是让直接给环的节点数有的甚至从链表跳到了有向图、无向图。很多人在“判断有环”这一步很熟快慢指针一梭子写完结果“求环长”时卡住了相遇之后到底让哪个指针先停计数器从0开始还是从1开始单节点自环会不会死循环这篇文章就把“环回路长度”这个主题拆开讲透覆盖链表的环长求解、数学推导、图里的回路判长以及实际工程里的循环依赖和死锁检测场景。适合正在刷题准备面试的同学也适合因为构建依赖成环、数据库死锁这类线上问题反过来补算法的朋友。1. 先搞清楚题面你要求的到底是哪种“环”1.1 链表环 vs 图回路问题形态完全不同“求环(回路)长度”这个说法本身有歧义因为它在不同的数据结构里含义不太一样。在链表里环指的是尾节点的 next 指针没有指向 null而是指回了之前的某个节点。这种情况下“环长”通常指这个闭环里包含多少个节点。比如 1-2-3-4-2 这个链表环由 2、3、4 三个节点组成环长就是 3。这种题目非常经典输入就是一个链表头节点输出要么是有环时的环长要么是环的入口节点。在有向图里环回路指的是一条从某个节点出发沿着有向边走最终又能回到出发点的路径。环的长度一般用路径上经过的边的条数来度量。比如三个节点 A-B-C-A这就是一个长度为 3 的有向环。热搜词里有“有向图三元环计数”本质上就是在统计长度为 3 的回路数量。在无向图里则要小心一个坑无向图中 A-B-A 这种走法虽然能从 A 出发回到 A但一般不算环因为那只是沿着同一条边走了一个来回。标准定义下无向图的环至少需要三个节点、三条边。所以求无向图最小环的时候答案不会小于 3。理解了题面里“环”的准确含义再上手写代码才不容易出偏差。很多人在“判断链表是否有环”上没问题但是把环长输出成了“从相遇点再走回相遇点的步数减 1”之类的结果本质上就是没有想清楚单位是节点数还是边数。1.2 输出定义的坑环长是节点数还是边数我见过不少人栽在这个地方。链表里 3 个节点组成的环按节点数算是 3按边数算也是 3因为环内每条边连接两个节点节点数和边数相等。这误导了很多初学者以为环长怎么数都一样。其实只有在“自环”和其他特殊情况下你才会意识到区别。自环就是某个节点的 next 指向它自己。这个环内只有一个节点同时也只有一条边。如果你按节点数算环长是 1如果你按边数算环长也是 1。这时候两个定义一致。真正拉开差距的是有向图里的自环以及无向图里对边重复的限制。图论题里有时候会明确说“回路长度边数”有时候说“环包含的顶点数”这两个在普通简单环里相等但在带权图、多重边图里就可能不一致了。所以做题第一步永远是确认题目的输出定义。如果你刷题时判断“返回类型是 int”那基本是要求节点数或者边数如果你看到返回类型是 ListNode 或者数组那大概率要求的是环入口节点或者环上的节点列表这种情况“长度”只是中间产物。2. 哈希表法最直观也最容易把环长定义说清楚2.1 核心思路记录每个节点“第一次被看到”的位置求环长最简单、最不容易写错的解法是用哈希表。思路一句话遍历链表每走到一个节点就把这个节点本身作为 key 存进哈希表value 记录这是第几步访问到的。如果某个节点已经出现在哈希表里说明这个节点之前被访问过而你现在又走到了它——链表是单向的能再次访问同一个节点唯一的解释就是后面形成了一个环。这时候环长怎么算当前步数减去该节点第一次被访问时的步数。举个例子1 - 2 - 3 - 4 - 2从 head 出发第 0 步访问节点 1第 1 步访问节点 2第 2 步访问节点 3第 3 步访问节点 4。第 4 步的时候你访问到节点 2而这个节点在第 1 步已经出现过。当前步数 4 减去第一次出现的步数 1得到 3正好是 2-3-4 这个环节点个数。这个解法把“环长”的定义映射得非常清楚环长就是从第一次进入环口到再次回到环口之间经过的节点数。2.2 代码实现Python 版本可以直接用节点对象做 keyclass ListNode: def __init__(self, val0, nextNone): self.val val self.next next def get_cycle_length_with_map(head): seen {} cur head step 0 while cur: if cur in seen: # 当前步数与第一次访问该节点的步数之差就是环长 return step - seen[cur] seen[cur] step cur cur.next step 1 return 0这段代码里最关键的一行是seen[cur] step用了节点对象本身做 key而不是节点里的值。为什么要强调这个因为链表里可能存在两个不同节点值恰好相同。如果误用cur.val做 key遇到相同的值就会被误判成环算出来的长度完全是错的。用节点本身作为 key才能严格表达“同一个对象再次被访问”。还有一个细节在 Python 中默认的ListNode实例是可哈希的所以直接作为字典 key 没有问题。如果你在自己的代码里重写了__eq__方法比如让两个相同 val 的节点判定相等那么对象的__hash__也会受影响这种节点就不能直接当作 key 用了。遇到这种情况正确的做法是改用id(cur)作为 key。时间复杂度是 O(n)因为每个节点最多遍历一次空间复杂度是 O(n)哈希表里最多存 n 个节点。这也是哈希表法最大的软肋——面试官大概率会追问一句能不能用 O(1) 空间2.3 为什么哈希表法能“一步到位”给出环长和环入口哈希表法真正厉害的地方在于它不只是给你一个数字它把整个遍历路径都记录下来了。当if cur in seen触发的时候seen[cur]就是环入口节点对应的步数也就是环外链表的长度cur本身是环入口节点也就是再次回到的那个节点。也就是说环长、环入口、环外长度三个信息全部都能拿到。我之前帮朋友 review 代码的时候见过一个很有意思的写法他先判断有环再用另一个哈希表重新遍历一遍去统计环长。这其实绕远了。第一次遍历的时候如果就把步数存下来第二次再走到重复节点时直接做差就行完全不需要第三趟。哈希表法的缺点也很明显当链表特别长的时候内存占用会比较难看。工程上如果只是判断有没有环这个方案还可以接受但要是追求极致性能或者题目明确要求 O(1) 空间就得换快慢指针了。3. 快慢指针面试高频解法背后的数学原理3.1 判环阶段为什么快指针走两步就行快慢指针Floyd 判圈算法的大致流程大家都知道慢指针每次走一步快指针每次走两步如果链表有环两个指针最终会在环内相遇。但很多人没想过一个问题——为什么快指针步长得是 23 行不行4 行不行快指针步长 2 最大的好处是快指针相对于慢指针每个单位时间内只多走 1 步。也就是说快指针在一步一步地“追上”慢指针不会跳过它。如果快指针步长是 3那么它相对慢指针的速度是 2理论上可能会从慢指针头上“跳过去”而不相遇。虽然多绕几圈之后大概率还是会撞上但证明和分析就麻烦得多也不是所有环长下都能立刻相遇。所以写成fast fast.next.next是最稳的。判环的循环条件也要配套写好while fast and fast.next: slow slow.next fast fast.next.next if slow fast: # 有环 breakwhile fast and fast.next的含义是快指针当前节点不为空下一个节点也不为空才能一次走两步。如果链表无环且节点数是偶数快指针会在某一轮走到None循环条件直接拦住了fast.next.next的访问如果只写while fast.next快指针走到最后一个节点时不会报错但已经无法继续走两步判环逻辑就断了。3.2 求环长阶段相遇后原地绕圈计数器从 1 开始判断有环之后怎么求环的长度最简单可靠的做法是让一个指针停在相遇点另一个指针继续每次走一步绕环走一圈再次回到相遇点时走过的步数就是环长。def get_cycle_length_two_pointers(head): slow head fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: # 找到环开始数环长 cur slow.next length 1 while cur ! slow: cur cur.next length 1 return length return 0这里有个容易被新手写错的地方length从 1 开始cur从slow.next开始而不是让cur slow、length 0再在循环里length 1。两种写法都能得到正确答案但后者要多写一个 do-while 结构因为退出条件是“回到 slow”而不是“当前节点为空”。你如果用while cur ! slow的普通 while 循环却把cur初始化为slow、length初始化为 0循环体一次都不会执行直接返回 0。所以我的建议是固定一个指针不动另一个指针先走一步再进入循环这样length天然从 1 开始逻辑最顺。3.3 数学推导为什么这样绕一圈就一定是完整环长有人会有疑问相遇点不一定在环入口啊以相遇点为起点绕一圈会不会只绕了环的一部分答案是不会。关键点在于一旦两个指针相遇这个相遇点一定是环内的某个节点。你从环内任意一个节点出发沿着 next 一直走走完一整圈一定会回到这个节点在你走回这个节点之前会逐个经过环内所有其他节点。所以“从相遇点出发再次回到相遇点”这个过程中经过的节点数精确等于环内节点总数。这个过程完全不依赖快慢指针的相对速度也不依赖相遇点具体在环的哪个位置。如果还想再严谨一点可以用经典公式推导一下。设环外链表长度为 a环长为 b慢指针刚进入环后走 x 步与快指针相遇0 x b。慢指针总路程a x快指针总路程a x n*b其中 n 是快指针比慢指针多绕的圈数因为快指针速度是慢指针的两倍所以2 * (a x) a x n*b化简a x n*b也就是说相遇点的位置满足从链表头到相遇点的距离正好是环长的整数倍。这个式子虽然不能直接告诉我们 b 的具体数值但它告诉我们一件事相遇点确实在环上而且它和环入口之间有非常确定的关系。这个关系就是 3.4 节要讲的环入口推导。3.4 顺带解决环入口怎么找和环长的关系是什么LeetCode 142 题不仅要求判断有环还要求返回环的入口节点。有了刚才的式子环入口就很好求了从相遇点继续推导a x nb所以 a nb - x (n-1)*b (b-x)。这里的 b - x 是从相遇点继续往前走到环入口的距离。也就是说一个指针从链表头出发另一个指针从相遇点出发两者都每次走一步它们一定会在环入口相遇。这个结论和求环长有什么关系如果题目只要环长你完全可以先用 3.2 的绕圈法数出环长再根据环长去定位入口。但在实际刷题中我更推荐“先判环、再入口、再绕圈”的组合顺序第一趟快慢指针判断有环并拿到相遇点第二趟从链表头和相遇点同时出发找到环入口第三趟从环入口出发绕一圈统计环长这样每一步都清晰可控不会把变量搞混。如果你空间上允许哈希表法一次遍历就能同时拿到入口和环长很多工程场景里其实哈希表法更实用没必要为了炫技而强行 O(1) 空间。4. 边界情况与实战踩坑记录4.1 空链表、单节点自环、环长为 1 的边界刷题时最容易翻车的往往不是核心算法而是边界条件。对于“求环长”来说最典型的边界有三个。第一个是空链表。head为 None循环条件while fast and fast.next会直接把fast判为假整个循环不执行函数返回 0没问题。第二个是只有一个节点且指向 None 的无环链表。同样由循环条件兜住返回 0。第三个是单节点自环也就是head.next head。这种情况下初始化slow head、fast head进入循环之后slow slow.next和fast fast.next.next都走到了 head 自己两个指针立刻相遇。进入绕圈环节cur slow.next也就是 head而cur slow条件为真循环不执行返回 length 1。这个结果是完全正确的但前提是你没有在初始化时把快指针写成fast head.next。如果初始化写成fast head.next单节点自环时fast和slow都是同一个节点依然能正确判环但空链表时head.next会直接抛 AttributeError。所以我在所有代码里都统一写成slow fast head省得在不同初始化方式之间切换时出错。4.2 fast 判空顺序最容易写错的三个版本快慢指针的循环条件有几种写法我按照“从错到对”排个序while fast:只判了 fast 不为空没有判 fast.next。链表长度为偶数且无环时fast 走到最后一个节点后下一次循环体内访问fast.next.next会返回 None然后循环继续fast None下一轮while fast退出看起来没问题但你会多走一次无意义的循环而且slow也被多移动了一次。while fast.next:如果 fast 已经是 None调用fast.next直接抛异常。如果 fast 是最后一个节点fast.next为 None循环退出但此时 fast 没能走到最后一步链表末尾的节点没有被检查。while fast and fast.next:正确。先判断当前节点存在再判断下一个节点存在最后才敢访问fast.next.next。这段顺序我在本地测过很多次也用不同长度的无环链表验证过第三种写法是唯一在所有情况下都能安全退出的版本。不要觉得这是小事很多人提交后报错就出在 AttributeError 上。4.3 递归判环的陷阱为什么实际工程里不建议用递归还有一种求环长的思路是用递归加访问集合伪代码如下def dfs(node, visited, path): if node in visited: return ... visited.add(node) return dfs(node.next, visited, path)这种写法在链表很短的时候没问题但链表一长Python 默认递归深度限制是 1000超过就 RecursionError。我在本地构造了一条 1500 个节点的无环链表递归版本直接崩迭代版本秒出。更麻烦的是递归版本身很容易在“判断重复节点”和“计算长度”之间夹杂太多状态review 的时候可读性也差。所以求环长这种很简单的场景不要使用递归。相比之下哈希表迭代或者快慢指针迭代都更好。如果你真的需要处理超长链表可以在开头加sys.setrecursionlimit()但这属于治标不治本工程上的循环依赖图动辄上万个节点递归栈根本扛不住。5. 从链表到图环回路长度的扩展战场5.1 有向图判环与“有向图三元环计数”链表只是最简单的环模型放在有向图里“求环回路长度”就变成一个更复杂的话题。先说要判断有向图里有没有环、环由哪些节点组成。常用方案有两种。第一种是拓扑排序。对图做拓扑排序如果最后处理完的节点数量小于总节点数说明有节点没有被排序进去这些节点一定处在某个环中。但拓扑排序的一个问题是它告诉你“有环”但不直接告诉环有几个节点、在哪。想拿环长你需要另做处理。第二种是 DFS 路径栈。维护一个递归栈或显式栈记录当前正在遍历的路径。访问到一个节点时如果它已经在当前路径栈中就说明发现了一个环环长就是栈中从该节点位置到栈顶的元素个数。这个方法非常直观也是我在工程里检查循环依赖时最喜欢用的方式。至于热搜词里的“有向图三元环计数”它统计的是长度为 3 的有向环。朴素做法是三层循环枚举所有三元组复杂度 O(n^3)图一大人就没了。常见优化是给每个节点按度数排序把所有无向边转成从度数小的点指向度数大的点的有向边然后枚举边 (a,b)再枚举 b 的出边 (b,c)判断 c 到 a 是否有边。这样复杂度能做到 O(m√m)m 是边数。虽然思路稍绕但本质上就是在数特定的环长。5.2 无向图的最小环长度无向图里如果要求“最小环长度”问题又变了。刚才说过无向图里 A-B-A 不算环至少 3 个节点才算。求最小环有两种常见思路。第一种是 BFS。枚举每个起点 s把 s 的邻边“断开”从 s 的各个邻居出发做 BFS如果 BFS 过程中遇到一个已经被访问过的节点说明存在一条回到 s 的非原路路径当前深度加上回边长度就是一个候选环。这个方案的理解成本稍微高一点但实现上可以复用最短路模板。第二种是 Floyd 动态规划求最小环。初始化dis[i][j]为 i 到 j 的最短距离matrix[i][j]为原图边的权值。枚举中间点 k在把 k 作为中转节点加入之前先尝试用dis[i][j] matrix[j][k] matrix[k][i]更新最小环长度。这个做法的核心思想是枚举环上编号最大的点 k那么环的其他部分只包含编号小于 k 的节点这正好符合 Floyd 算法按节点编号递推的顺序。这两种方法我实际都实现过BFS 适合边权为 1 的图Floyd 适合带权图但适合小规模节点。为什么因为 Floyd 本身是 O(n^3)几百个节点还可以上万个节点就基本没法用了。工程里遇到大规模图一般会先用拓扑排序把不成环的部分剪掉再在剩余的强连通分量里寻找目标环。5.3 生产环境中的求环场景循环依赖、死锁检测和报文长度校验讲完算法说几个真实世界里的应用。我最早接触“求环”不是刷题是在做构建系统的时候。项目里几十个模块互相 import某个模块循环依赖导致启动时栈溢出。我当时用的就是 DFS 路径栈的思路把那几个互相引用的模块名按顺序打印出来一眼就定位到问题。环的长度就是模块循环的个数。另一个经典场景是数据库死锁检测。资源分配图里有向环往往意味着死锁环上的节点就是互相占用资源的会话。这时候不只是判断“有没有环”更要把环里的节点列表捞出来才能知道谁在等谁释放锁。很多数据库内核内部维护的等待关系图就是靠类似 DFS 的方式检测环并回滚事务的。还有一个和“长度”有关但更容易被忽略的工程场景是网络数据包的长度字段校验。热搜词里有一句“在网络数据包负载中指定的长度与读取的字节数不匹配;该连接已关闭。请与客户端库”这看起来不像是环的问题但它本质上是一种“长度校验失败”的报错。处理这类问题的时候我习惯在每次读取循环前先核对长度字段然后用一个严格等于长度字段的循环边界去读数据。如果发现实际读到的字节数和声明的不一致立刻抛出异常而不是盲目继续读——这和算法里“先定义清楚长度再围绕长度做校验”是一个道理。写在最后的一点实操体会“求环(回路)长度”这个题目表面上只是链表的快慢指针实际拆开之后能辐射到哈希表、数学推导、图论、工程死锁检测等一大片领域。我自己的经验是拿到这类题不要急着写快慢指针先确认三件事——环的定义是节点数还是边数、输出单位是什么、是否需要额外返回环入口或环节点列表。确认完再选择算法。链表场景下哈希表法最直观、容错率最高空间受限或想秀优化再用快慢指针绕圈计数。无论用哪种写法单节点自环、空链表、fast 判空顺序这三个 case 一定要在本地先跑一遍尤其是单节点自环最容易暴露计数器初始化的问题。如果你是在工程里排查循环依赖DFS 路径栈永远比单纯判断有没有环更有用因为线上问题最终需要你给出“哪几个节点构成了环”而不是一个干巴巴的布尔值。