LeetCode 142. 环形链表 II哈希表与快慢指针Floyd 判圈双解法详解【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文讲解 LeetCode 142. 环形链表 II 的两种经典解法哈希表法与快慢指针法Floyd 判圈算法涵盖完整思路、数学证明、伪代码与 JS / Go / PHP / C 四种语言实现。读完本文你将掌握如何在 O(1) 空间内定位链表环入口的核心推导过程并能将快慢指针这一双指针套路迁移到 141. 环形链表、287. 寻找重复数等同类问题中。本仓库 thinkings/linked-list.md 与 91/two-pointers.md 将快慢指针归为双指针三大题型之首本文即是对该算法框架的一次完整实战拆解。题目描述与考点分析给定一个链表返回链表开始入环的第一个节点。如果链表无环则返回null。为了表示给定链表中的环题目使用整数pos表示链表尾连接到链表中的位置索引从 0 开始如果pos是-1则在该链表中没有环。注意pos仅仅是用于标识环的情况并不会作为参数传递到函数中。题目有两个关键约束不允许修改给定的链表因此不能通过标记、断链等方式原地改造输入进阶要求使用 O(1) 空间解决此题直接淘汰了哈希表的线性空间开销。该题的本质与 141. 环形链表仅判环相比多了一步定位环入口。而根据本仓库 thinkings/linked-list.md 中的总结判断链表是否有环以及环的入口都是使用快慢指针即可解决的经典套路这类题目不知道就不会知道了就不容易忘。下面分别介绍哈希法与快慢指针法。解法一哈希法哈希表记录访问过的节点思路哈希法的思路非常直白遍历整个链表同时将每个节点插入哈希表如果当前节点在哈希表中不存在继续遍历如果当前节点在哈希表中已经存在那么当前节点就是环的入口节点。其正确性依赖一个简单事实链表一旦成环从入环点开始所有节点都会被反复访问遍历过程中第一个重复出现的节点必然是环的入口。伪代码如下data new Set() // 声明哈希表 while head不为空{ if 当前节点在哈希表中存在{ return head // 当前节点就是环的入口节点 } else { 将当前节点插入哈希表 } head指针后移 } return null // 环不存在代码JS本仓库给出的实现直接使用Set存储节点引用判断节点是否重复时利用的是引用相等性因此无需自定义哈希函数let data new Set(); while (head) { if (data.has(head)) { return head; } else { data.add(head); } head head.next; } return null;复杂度分析时间复杂度$O(N)$每个节点至多被访问一次哈希表的插入与查询均为 $O(1)$空间复杂度$O(N)$需要存储链表中每个节点的引用。哈希法简单直观但它不满足题目进阶的 O(1) 空间要求因此面试中往往还需要掌握下面的快慢指针法。解法二快慢指针法Floyd 判圈算法思路快慢指针法分两个阶段阶段一判环并找到第一次相遇点定义 fast 指针每次前进两步slow 指针每次前进一步两个指针都从头节点出发。若链表无环fast 会先走到末尾若链表有环两指针必然在环内某点相遇。阶段二找环入口当两个指针相遇时将 fast 指针重新指向链表头部同时让 fast 指针每次只前进一步slow 指针继续前进每次前进一步。当两个指针再次相遇时当前节点就是环的入口。为什么第二次相遇的点就是环的入口数学推导这是本题最核心的推导也是面试考察的重点。设A 表示链表头节点到环入口的距离B 表示环入口沿前进方向到第一次相遇点的距离L 表示环的长度第一次相遇时慢指针移动距离为 $s_1 A B n_1 \times L$在相遇前可能已在环内绕了 $n_1$ 圈快指针移动距离为 $s_2 A B n_2 \times L$绕了 $n_2$ 圈。由于快指针速度是慢指针的两倍所以 $s_2 2 \times s_1$代入得$$ A B n_2 \times L 2A 2B 2 \times n_1 \times L $$化简$$ A -B (n_2 - 2n_1) \times L $$由于 $(n_2 - 2n_1) \times L$ 表示绕环的整数圈等价于回到原地因此从第一次相遇点出发沿环走 A 步与向后逆着前进方向走 B 步到达的位置相同即$$ A -B \quad (\text{模 } L \text{ 意义下}) $$换句话说从第一次相遇点再前进 A 步等价于后退 B 步而后退 B 步恰好回到环入口。因此第一次相遇后fast 从头节点走 A 步会到达环的入口slow 从第一次相遇点走 A 步相当于向后走 B 步也会到达环的入口两指针以相同步长前进必然在环入口再次相遇。伪代码fast head slow head //快慢指针都指向头部 do { 快指针向后两步 慢指针向后一步 } while 快慢指针不相等时 if 指针都为空时{ return null // 没有环 } while 快慢指针不相等时{ 快指针向后一步 慢指针向后一步 } return fast代码本仓库的题解给出了 JS、Go、PHP、C 四种语言实现下面逐一列出。JS CodeJS 实现用do...while保证 slow 与 fast 从同一节点出发时至少先各自移动一次再用fast null判断是否无环if (head null || head.next null) return null; let fast (slow head); do { if (fast ! null fast.next ! null) { fast fast.next.next; } else { fast null; } slow slow.next; } while (fast ! slow); if (fast null) return null; fast head; while (fast ! slow) { fast fast.next; slow slow.next; } return fast;Go CodeGo 实现把数学结论直接写进了注释kxayz; 2kxbyz xzcy, xcy-z其中 x 为头节点到环入口距离、y 为环长、z 为相遇点位置。实现中用布尔变量k处理首次执行与指针相等同时成立的情况/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func detectCycle(head *ListNode) *ListNode { // x 到环的距离; y 环的长度; z p/q环上相遇的位置; a/b/c 正整数, 表示绕环整数圈 // kxayz; 2kxbyz xzcy, xcy-z p : head // 快指针, 2倍速 q : head // 慢指针, 1倍速 k : true // 第一次执行 for p ! q || k { k false if p nil || p.Next nil { return nil } p p.Next.Next q q.Next } // 由于 xcy-z, p 重置为 head, q 此时在 z 处, 则正好在环起点相遇 p head for p ! q { p p.Next q q.Next } return p }PHP CodePHP 实现与 Go 完全同构同样用$k true处理首次迭代用!$p || !$p-next判空/** * Definition for a singly-linked list. * class ListNode { * public $val 0; * public $next null; * function __construct($val) { $this-val $val; } * } */ class Solution { /** * param ListNode $head * return ListNode */ function detectCycle($head) { // x 到环的距离; y 环的长度; z p/q环上相遇的位置; a/b/c 正整数, 表示绕环整数圈 // kxayz; 2kxbyz xzcy, xcy-z $p $q $head; // $p 快指针, 2倍速; $q 慢指针, 1倍速 $k true; // 第一次执行 while ($p ! $q || $k) { $k false; if (!$p || !$p-next) return null; $p $p-next-next; $q $q-next; } // 由于 xcy-z, p 重置为 head, q 此时在 z 处, 则正好在环起点相遇 $p $head; while ($p ! $q) { $p $p-next; $q $q-next; } return $p; } }C CodeC 实现先在while中寻找相遇点并break随后通过if (!p || !p-next)区分因无环退出与因相遇退出两种情况class Solution { public: ListNode *detectCycle(ListNode *head) { if (!head) return NULL; auto p head, q head; while (p p-next) { p p-next-next; q q-next; if (p q) break; } if (!p || !p-next) return NULL; p head; for (; p ! q; p p-next, q q-next); return p; } };复杂度分析时间复杂度$O(N)$阶段一快慢指针在环内相遇前两指针合计走过的距离与链表长度同阶阶段二两指针同步前进步长不超过 A 步整体仍为线性空间复杂度$O(1)$全程只使用两个指针变量满足题目进阶要求。快慢指针从一道题到一个算法框架本仓库将本题置于更宏观的算法框架中值得展开说明在 thinkings/linked-list.md 中作者将快慢指针列为链表专题的四大技巧之一虚拟头、快慢指针、穿针引线、先穿再排后判空并指出判断链表是否有环、环的入口、求链表交点都属于快慢指针这一类不知道就不会知道了就不容易忘的题型。在 91/two-pointers.md 中双指针被归纳为三类快慢指针两个指针步长不同、左右端点指针分别指向头尾并向中间移动、固定间距指针间距与步长相同。本题正是快慢指针的典型代表由于步长为常数 2时间复杂度为 $O(N)$且全程只需两个指针空间复杂度为 $O(1)$。同一算法框架下的经典变式还有141. 环形链表只判环不找入口、287. 寻找重复数把数组下标映射为链表节点用快慢指针找重复值以及求链表中间节点、倒数第 k 个节点等固定间距指针套路。小结本题是链表双指针的经典考题两种解法形成鲜明的对比解法核心思想时间复杂度空间复杂度是否满足 O(1) 进阶哈希法借助Set记录已访问节点首个重复节点即环入口$O(N)$$O(N)$否快慢指针法快慢指针先相遇判环再同速前进在环入口重逢$O(N)$$O(1)$是需要记住的核心结论是第一次相遇后把 fast 重置到头节点两指针同速前进再次相遇处即为环入口其正确性由 $A -B \pmod L$ 这一数学关系保证。掌握了这道题的推导快慢指针系列141 判环、287 找重复数、链表交点、中间节点、倒数第 k 节点便都可以融会贯通。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/19 0:17:19 · 阅读 1.2k LeetCode 142. 环形链表 II：哈希表与快慢指针（Floyd 判圈）双解法详解
LeetCode 142. 环形链表 II哈希表与快慢指针Floyd 判圈双解法详解【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode导读本文讲解 LeetCode 142. 环形链表 II 的两种经典解法哈希表法与快慢指针法Floyd 判圈算法涵盖完整思路、数学证明、伪代码与 JS / Go / PHP / C 四种语言实现。读完本文你将掌握如何在 O(1) 空间内定位链表环入口的核心推导过程并能将快慢指针这一双指针套路迁移到 141. 环形链表、287. 寻找重复数等同类问题中。本仓库 thinkings/linked-list.md 与 91/two-pointers.md 将快慢指针归为双指针三大题型之首本文即是对该算法框架的一次完整实战拆解。题目描述与考点分析给定一个链表返回链表开始入环的第一个节点。如果链表无环则返回null。为了表示给定链表中的环题目使用整数pos表示链表尾连接到链表中的位置索引从 0 开始如果pos是-1则在该链表中没有环。注意pos仅仅是用于标识环的情况并不会作为参数传递到函数中。题目有两个关键约束不允许修改给定的链表因此不能通过标记、断链等方式原地改造输入进阶要求使用 O(1) 空间解决此题直接淘汰了哈希表的线性空间开销。该题的本质与 141. 环形链表仅判环相比多了一步定位环入口。而根据本仓库 thinkings/linked-list.md 中的总结判断链表是否有环以及环的入口都是使用快慢指针即可解决的经典套路这类题目不知道就不会知道了就不容易忘。下面分别介绍哈希法与快慢指针法。解法一哈希法哈希表记录访问过的节点思路哈希法的思路非常直白遍历整个链表同时将每个节点插入哈希表如果当前节点在哈希表中不存在继续遍历如果当前节点在哈希表中已经存在那么当前节点就是环的入口节点。其正确性依赖一个简单事实链表一旦成环从入环点开始所有节点都会被反复访问遍历过程中第一个重复出现的节点必然是环的入口。伪代码如下data new Set() // 声明哈希表 while head不为空{ if 当前节点在哈希表中存在{ return head // 当前节点就是环的入口节点 } else { 将当前节点插入哈希表 } head指针后移 } return null // 环不存在代码JS本仓库给出的实现直接使用Set存储节点引用判断节点是否重复时利用的是引用相等性因此无需自定义哈希函数let data new Set(); while (head) { if (data.has(head)) { return head; } else { data.add(head); } head head.next; } return null;复杂度分析时间复杂度$O(N)$每个节点至多被访问一次哈希表的插入与查询均为 $O(1)$空间复杂度$O(N)$需要存储链表中每个节点的引用。哈希法简单直观但它不满足题目进阶的 O(1) 空间要求因此面试中往往还需要掌握下面的快慢指针法。解法二快慢指针法Floyd 判圈算法思路快慢指针法分两个阶段阶段一判环并找到第一次相遇点定义 fast 指针每次前进两步slow 指针每次前进一步两个指针都从头节点出发。若链表无环fast 会先走到末尾若链表有环两指针必然在环内某点相遇。阶段二找环入口当两个指针相遇时将 fast 指针重新指向链表头部同时让 fast 指针每次只前进一步slow 指针继续前进每次前进一步。当两个指针再次相遇时当前节点就是环的入口。为什么第二次相遇的点就是环的入口数学推导这是本题最核心的推导也是面试考察的重点。设A 表示链表头节点到环入口的距离B 表示环入口沿前进方向到第一次相遇点的距离L 表示环的长度第一次相遇时慢指针移动距离为 $s_1 A B n_1 \times L$在相遇前可能已在环内绕了 $n_1$ 圈快指针移动距离为 $s_2 A B n_2 \times L$绕了 $n_2$ 圈。由于快指针速度是慢指针的两倍所以 $s_2 2 \times s_1$代入得$$ A B n_2 \times L 2A 2B 2 \times n_1 \times L $$化简$$ A -B (n_2 - 2n_1) \times L $$由于 $(n_2 - 2n_1) \times L$ 表示绕环的整数圈等价于回到原地因此从第一次相遇点出发沿环走 A 步与向后逆着前进方向走 B 步到达的位置相同即$$ A -B \quad (\text{模 } L \text{ 意义下}) $$换句话说从第一次相遇点再前进 A 步等价于后退 B 步而后退 B 步恰好回到环入口。因此第一次相遇后fast 从头节点走 A 步会到达环的入口slow 从第一次相遇点走 A 步相当于向后走 B 步也会到达环的入口两指针以相同步长前进必然在环入口再次相遇。伪代码fast head slow head //快慢指针都指向头部 do { 快指针向后两步 慢指针向后一步 } while 快慢指针不相等时 if 指针都为空时{ return null // 没有环 } while 快慢指针不相等时{ 快指针向后一步 慢指针向后一步 } return fast代码本仓库的题解给出了 JS、Go、PHP、C 四种语言实现下面逐一列出。JS CodeJS 实现用do...while保证 slow 与 fast 从同一节点出发时至少先各自移动一次再用fast null判断是否无环if (head null || head.next null) return null; let fast (slow head); do { if (fast ! null fast.next ! null) { fast fast.next.next; } else { fast null; } slow slow.next; } while (fast ! slow); if (fast null) return null; fast head; while (fast ! slow) { fast fast.next; slow slow.next; } return fast;Go CodeGo 实现把数学结论直接写进了注释kxayz; 2kxbyz xzcy, xcy-z其中 x 为头节点到环入口距离、y 为环长、z 为相遇点位置。实现中用布尔变量k处理首次执行与指针相等同时成立的情况/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */ func detectCycle(head *ListNode) *ListNode { // x 到环的距离; y 环的长度; z p/q环上相遇的位置; a/b/c 正整数, 表示绕环整数圈 // kxayz; 2kxbyz xzcy, xcy-z p : head // 快指针, 2倍速 q : head // 慢指针, 1倍速 k : true // 第一次执行 for p ! q || k { k false if p nil || p.Next nil { return nil } p p.Next.Next q q.Next } // 由于 xcy-z, p 重置为 head, q 此时在 z 处, 则正好在环起点相遇 p head for p ! q { p p.Next q q.Next } return p }PHP CodePHP 实现与 Go 完全同构同样用$k true处理首次迭代用!$p || !$p-next判空/** * Definition for a singly-linked list. * class ListNode { * public $val 0; * public $next null; * function __construct($val) { $this-val $val; } * } */ class Solution { /** * param ListNode $head * return ListNode */ function detectCycle($head) { // x 到环的距离; y 环的长度; z p/q环上相遇的位置; a/b/c 正整数, 表示绕环整数圈 // kxayz; 2kxbyz xzcy, xcy-z $p $q $head; // $p 快指针, 2倍速; $q 慢指针, 1倍速 $k true; // 第一次执行 while ($p ! $q || $k) { $k false; if (!$p || !$p-next) return null; $p $p-next-next; $q $q-next; } // 由于 xcy-z, p 重置为 head, q 此时在 z 处, 则正好在环起点相遇 $p $head; while ($p ! $q) { $p $p-next; $q $q-next; } return $p; } }C CodeC 实现先在while中寻找相遇点并break随后通过if (!p || !p-next)区分因无环退出与因相遇退出两种情况class Solution { public: ListNode *detectCycle(ListNode *head) { if (!head) return NULL; auto p head, q head; while (p p-next) { p p-next-next; q q-next; if (p q) break; } if (!p || !p-next) return NULL; p head; for (; p ! q; p p-next, q q-next); return p; } };复杂度分析时间复杂度$O(N)$阶段一快慢指针在环内相遇前两指针合计走过的距离与链表长度同阶阶段二两指针同步前进步长不超过 A 步整体仍为线性空间复杂度$O(1)$全程只使用两个指针变量满足题目进阶要求。快慢指针从一道题到一个算法框架本仓库将本题置于更宏观的算法框架中值得展开说明在 thinkings/linked-list.md 中作者将快慢指针列为链表专题的四大技巧之一虚拟头、快慢指针、穿针引线、先穿再排后判空并指出判断链表是否有环、环的入口、求链表交点都属于快慢指针这一类不知道就不会知道了就不容易忘的题型。在 91/two-pointers.md 中双指针被归纳为三类快慢指针两个指针步长不同、左右端点指针分别指向头尾并向中间移动、固定间距指针间距与步长相同。本题正是快慢指针的典型代表由于步长为常数 2时间复杂度为 $O(N)$且全程只需两个指针空间复杂度为 $O(1)$。同一算法框架下的经典变式还有141. 环形链表只判环不找入口、287. 寻找重复数把数组下标映射为链表节点用快慢指针找重复值以及求链表中间节点、倒数第 k 个节点等固定间距指针套路。小结本题是链表双指针的经典考题两种解法形成鲜明的对比解法核心思想时间复杂度空间复杂度是否满足 O(1) 进阶哈希法借助Set记录已访问节点首个重复节点即环入口$O(N)$$O(N)$否快慢指针法快慢指针先相遇判环再同速前进在环入口重逢$O(N)$$O(1)$是需要记住的核心结论是第一次相遇后把 fast 重置到头节点两指针同速前进再次相遇处即为环入口其正确性由 $A -B \pmod L$ 这一数学关系保证。掌握了这道题的推导快慢指针系列141 判环、287 找重复数、链表交点、中间节点、倒数第 k 节点便都可以融会贯通。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考