空间定位链表环起点的机制、证明与落地)
Floyd判圈算法O(1)空间定位链表环起点的机制、证明与落地【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址: https://gitcode.com/GitHub_Trending/cp/cp-algorithms链表里存在环而你被要求用 O(1) 空间找到环的起点。Floyd判圈算法龟兔赛跑只用快、慢两个指针就能做到不依赖哈希表也不改动节点。cp-algorithms 在 src/others/tortoise_and_hare.md 中给出了完整推导、证明与实现。它解决什么哈希表为什么不够用面试和竞赛中的经典题给定链表头节点若存在环找到环的起点 C否则报告无环。第一反应往往是给节点加一个 visited 标记或把走过的节点丢进哈希表。两者都能判环但都有代价标记字段需要改动节点结构链表被多处共享或只读时不可行哈希表需要 O(n) 额外空间随链长线性增长。Floyd 的做法反直觉不存任何东西只让两个指针以不同速度前进。空间开销为零且仍能精确定位环起点。机制拆解快慢指针的两段式配合第一步快慢指针检测环是否存在slow 每轮走 1 步fast 每轮走 2 步均从头节点出发无环时fast 会先碰到 null返回无环有环时fast 入环后在环内追赶 slow两者差距每轮缩小 1必然相遇。bool hasCycle(ListNode* h) { for (auto *s h, *f h; f f-next; s s-next, f f-next-next) if (s f) return true; return false; }相遇时刻两个指针停在环内同一个节点 G第二步slow 重置到 head各走一步定位环起点关键一步把 slow 拉回 head之后两个指针每轮各走 1 步它们第一次相遇处就是环起点 C。ListNode* cycleStart(ListNode* head, ListNode* meet) { auto slow head; while (slow ! meet) { slow slow-next; meet meet-next; } return slow; // 环起点 C }为什么成立一行距离关系设 head 到环起点 C 的距离为 a环长为 LC 到相遇点 G 的距离为 b相遇时 slow 已走 a xL bfast 已走 a yL bx、y 为非负整数且 fast 路程恒为 slow 的两倍$$a yL b 2(a xL b) \Rightarrow a (y - 2x)L - b$$含义从 head 走 a 步等价于在环内绕整圈后再从 G 后退 b 步。而 fast 此时正好在 G领先 C 共 b 步再走 a 步恰好落在 Cslow 从 head 出发走 a 步也落在 C。所以第二次相遇必然是环起点且与环长、绕圈次数无关。效果实证判环与定位起点方案的时空对比方案时间复杂度空间复杂度能定位环起点限制节点加 visited 字段O(n)O(1)是需改动节点共享/只读链表不可行哈希表记录已访问节点O(n)O(n)是额外空间随链长线性增长Floyd龟兔赛跑O(n)O(1)是仅两个指针变量步数上界由上文推导可得n 为链表总长阶段步数上界第一步判环≤ a L第二步定位起点≤ a合计≤ 2a L ≤ 2n总步数的常数因子不超过 2。数据来源基于 src/others/tortoise_and_hare.md 中 Why does it work 一节的距离推导与复杂度分析。 落地指南参数建议与常见坑配置项建议值作用fast 每轮步数2slow 的两倍保证收敛且边界检查最简改 3 步以上需另行证明初始位置均从 head 出发证明中距离关系成立的前提边界检查while (f f-next)防止无环链表上 fast 越界重置动作第二步开始前把 slow 拉回 head定位环起点的关键不可省略适用结构有界、有限状态、单后继同一结构可迁移到数组函数 f(i) a[a[i]]本地阅读原文可执行git clone https://gitcode.com/GitHub_Trending/cp/cp-algorithms。仓库 test/ 目录用g -stdc17 -fsanitizeundefined统一编译运行各文章中的 C 代码见 test/test.sh若你要处理的是普通图上的环检测前提是存在后指针链做法与链表不同见 src/graph/finding-cycle.md。常见坑与对策常见坑现象对策未先检查f-next就解引用f-next-next无环链表上段错误先检查后推进检查写进循环条件第二步忘记把 slow 重置到 head返回错误节点或死循环证明仅在slow 从头节点出发时成立数组变体结论误用首次相遇得到的是重复值不是重复下标f(i) a[i] 变体中定位第一个重复位置需额外一轮对状态空间不断扩张的迭代判环判出的环无意义前提是有界状态空间与确定性后继函数总结与上手动作全流程两段式第一步判环是否存在第二步重置后各走一步定位环起点。空间 O(1)、时间 O(n)总步数常数因子不超过 2。证明核心只有一条fast 步数恒为 slow 两倍推出 a (y − 2x)L − b。同一结构可平移到数组即链表场景f(i) a[a[i]] 用于判环与查重。先通读 src/others/tortoise_and_hare.md 的完整推导再在白板上默写hasCycle与cycleStart两个函数最后用数组中找到重复数变体自测一遍。【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址: https://gitcode.com/GitHub_Trending/cp/cp-algorithms创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 Floyd判圈算法：O(1)空间定位链表环起点的机制、证明与落地
Floyd判圈算法O(1)空间定位链表环起点的机制、证明与落地【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址: https://gitcode.com/GitHub_Trending/cp/cp-algorithms链表里存在环而你被要求用 O(1) 空间找到环的起点。Floyd判圈算法龟兔赛跑只用快、慢两个指针就能做到不依赖哈希表也不改动节点。cp-algorithms 在 src/others/tortoise_and_hare.md 中给出了完整推导、证明与实现。它解决什么哈希表为什么不够用面试和竞赛中的经典题给定链表头节点若存在环找到环的起点 C否则报告无环。第一反应往往是给节点加一个 visited 标记或把走过的节点丢进哈希表。两者都能判环但都有代价标记字段需要改动节点结构链表被多处共享或只读时不可行哈希表需要 O(n) 额外空间随链长线性增长。Floyd 的做法反直觉不存任何东西只让两个指针以不同速度前进。空间开销为零且仍能精确定位环起点。机制拆解快慢指针的两段式配合第一步快慢指针检测环是否存在slow 每轮走 1 步fast 每轮走 2 步均从头节点出发无环时fast 会先碰到 null返回无环有环时fast 入环后在环内追赶 slow两者差距每轮缩小 1必然相遇。bool hasCycle(ListNode* h) { for (auto *s h, *f h; f f-next; s s-next, f f-next-next) if (s f) return true; return false; }相遇时刻两个指针停在环内同一个节点 G第二步slow 重置到 head各走一步定位环起点关键一步把 slow 拉回 head之后两个指针每轮各走 1 步它们第一次相遇处就是环起点 C。ListNode* cycleStart(ListNode* head, ListNode* meet) { auto slow head; while (slow ! meet) { slow slow-next; meet meet-next; } return slow; // 环起点 C }为什么成立一行距离关系设 head 到环起点 C 的距离为 a环长为 LC 到相遇点 G 的距离为 b相遇时 slow 已走 a xL bfast 已走 a yL bx、y 为非负整数且 fast 路程恒为 slow 的两倍$$a yL b 2(a xL b) \Rightarrow a (y - 2x)L - b$$含义从 head 走 a 步等价于在环内绕整圈后再从 G 后退 b 步。而 fast 此时正好在 G领先 C 共 b 步再走 a 步恰好落在 Cslow 从 head 出发走 a 步也落在 C。所以第二次相遇必然是环起点且与环长、绕圈次数无关。效果实证判环与定位起点方案的时空对比方案时间复杂度空间复杂度能定位环起点限制节点加 visited 字段O(n)O(1)是需改动节点共享/只读链表不可行哈希表记录已访问节点O(n)O(n)是额外空间随链长线性增长Floyd龟兔赛跑O(n)O(1)是仅两个指针变量步数上界由上文推导可得n 为链表总长阶段步数上界第一步判环≤ a L第二步定位起点≤ a合计≤ 2a L ≤ 2n总步数的常数因子不超过 2。数据来源基于 src/others/tortoise_and_hare.md 中 Why does it work 一节的距离推导与复杂度分析。 落地指南参数建议与常见坑配置项建议值作用fast 每轮步数2slow 的两倍保证收敛且边界检查最简改 3 步以上需另行证明初始位置均从 head 出发证明中距离关系成立的前提边界检查while (f f-next)防止无环链表上 fast 越界重置动作第二步开始前把 slow 拉回 head定位环起点的关键不可省略适用结构有界、有限状态、单后继同一结构可迁移到数组函数 f(i) a[a[i]]本地阅读原文可执行git clone https://gitcode.com/GitHub_Trending/cp/cp-algorithms。仓库 test/ 目录用g -stdc17 -fsanitizeundefined统一编译运行各文章中的 C 代码见 test/test.sh若你要处理的是普通图上的环检测前提是存在后指针链做法与链表不同见 src/graph/finding-cycle.md。常见坑与对策常见坑现象对策未先检查f-next就解引用f-next-next无环链表上段错误先检查后推进检查写进循环条件第二步忘记把 slow 重置到 head返回错误节点或死循环证明仅在slow 从头节点出发时成立数组变体结论误用首次相遇得到的是重复值不是重复下标f(i) a[i] 变体中定位第一个重复位置需额外一轮对状态空间不断扩张的迭代判环判出的环无意义前提是有界状态空间与确定性后继函数总结与上手动作全流程两段式第一步判环是否存在第二步重置后各走一步定位环起点。空间 O(1)、时间 O(n)总步数常数因子不超过 2。证明核心只有一条fast 步数恒为 slow 两倍推出 a (y − 2x)L − b。同一结构可平移到数组即链表场景f(i) a[a[i]] 用于判环与查重。先通读 src/others/tortoise_and_hare.md 的完整推导再在白板上默写hasCycle与cycleStart两个函数最后用数组中找到重复数变体自测一遍。【免费下载链接】cp-algorithmsAlgorithm and data structure articles for https://cp-algorithms.com (based on http://e-maxx.ru)项目地址: https://gitcode.com/GitHub_Trending/cp/cp-algorithms创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考