长度全解析：从链表快慢指针到图论与工程实战)
刷题的时候碰到“求环(回路)长度”这个标题，我第一反应是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 版本可以直接用节点对象做 key
class ListNode: def __init__(self, val=0, next=None): 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 判圈算法）的大致流程大家都知道：慢指针每次走一步，快指针每次走两步，如果链表有环，两个指针最终会在环内相遇。
但很多人没想过一个问题——为什么快指针步长得是 2？3 行不行？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 + 路径栈永远比单纯判断有没有环更有用，因为线上问题最终需要你给出“哪几个节点构成了环”，而不是一个干巴巴的布尔值。
