【LeetHOT100】环形链表Ⅱ——寻找环的入口（Java多解法详解）

一、题目描述142. 环形链表 II给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改给定的链表。示例 1输入head [3,2,0,-4]pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2]pos 0输出返回索引为 0 的链表节点解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1]pos -1输出返回null解释链表中没有环。提示链表中节点的数目范围是[0, 10⁴]-10⁵ Node.val 10⁵pos为-1或者链表中的一个有效索引进阶你是否可以使用 O(1) 空间解决此题二、解题思路概览与 141 题“判断是否有环”不同本题需要找到环的入口节点。常见解法有两种解法时间复杂度空间复杂度特点哈希表法O(n)O(n)最简单直观但空间不是最优快慢指针法Floyd判圈算法O(n)O(1)数学推导精妙面试必考三、解法一哈希表法最直观3.1 思路遍历链表使用HashSet存储已经访问过的节点。当第一次遇到某个节点已经存在于集合中时该节点就是环的入口。如果遍历到null说明无环。3.2 代码实现javapublic class Solution { public ListNode detectCycle(ListNode head) { SetListNode visited new HashSet(); ListNode p head; while (p ! null) { if (visited.contains(p)) { return p; // 第一个重复的节点即为环入口 } visited.add(p); p p.next; } return null; } }3.3 复杂度分析时间复杂度O(n)每个节点最多被访问一次。空间复杂度O(n)最坏情况下需要存储所有节点。四、解法二快慢指针法Floyd判圈算法⭐4.1 核心思想该解法分为两步判断是否有环使用快慢指针如果相遇则有环找到环的入口利用数学推导从相遇点和头节点同时出发每次走一步再次相遇的位置即为环入口。4.2 数学推导重要设x从头节点到环入口的节点数不包含环入口节点本身即从 head 走到入口需要的步数y从环入口到第一次相遇点的节点数沿着链表方向z从第一次相遇点绕环回到环入口的节点数即剩余环的长度那么环的长度为y z。相遇时的路程分析当快慢指针第一次相遇时慢指针slow走过的路程x y快指针fast走过的路程x y n(yz)其中n是快指针在环内绕的圈数n 1因为快指针速度是慢指针的两倍所以text2(x y) x y n(yz)化简得textx y n(yz) x n(yz) - y x (n-1)(yz) z这个等式的含义从头节点走到环入口的距离x等于从相遇点出发绕环(n-1)圈再走z步的距离。换句话说如果此时将一个指针ptr放回头节点另一个指针slow保持在相遇点然后两者以相同速度每次一步向前移动那么它们最终会在环入口处相遇。因为ptr 走x步到达入口slow 走(n-1)(yz) z步也到达入口即从相遇点出发先绕环 n-1 圈再走 z 步回到入口。4.3 算法步骤初始化slow headfast head循环移动slow每次走一步fast每次走两步直到fast null或fast.next null无环或slow fast有环如果无环返回null如果有环将ptr指向head然后ptr和slow同时每次移动一步直到它们相遇相遇的节点就是环的入口返回该节点。4.4 代码实现javapublic class Solution { public ListNode detectCycle(ListNode head) { if (head null || head.next null) { return null; } ListNode slow head; ListNode fast head; // 1. 判断是否有环并找到第一次相遇点 while (fast ! null fast.next ! null) { slow slow.next; fast fast.next.next; if (slow fast) { // 2. 有环找入口 ListNode ptr head; while (ptr ! slow) { ptr ptr.next; slow slow.next; } return ptr; } } return null; } }4.5 另一种等价写法有些实现会将fast初始化为head.next但原理相同只是相遇点会不同最终入口位置仍然正确。不过上述写法最为常见和简洁。4.6 复杂度分析时间复杂度O(n)。慢指针在进入环之前走x步进入环后最多走(yz)步就会相遇然后找入口时最多再走x步总步数2x y z≤ 3n所以 O(n)。空间复杂度O(1)只使用了常量个指针。4.7 图解示例以链表3 → 2 → 0 → -4pos1为例text链表结构 3 → 2 → 0 → -4 ↑__________↓x 1从头节点3到入口节点2的步数y 0从入口2出发到第一次相遇点如果环内相遇点恰好是入口则 y0z 3环内剩余节点数快慢指针相遇后slow指向相遇点ptr指向头节点3然后同时移动ptr: 3 → 21步到达入口slow: 从相遇点开始走 z3 步也会绕回到入口2所以相遇于节点2即环入口。五、解法对比与总结方法优点缺点适用场景哈希表简单直观不易出错空间 O(n)快速实现无空间限制快慢指针空间 O(1)满足进阶要求数学推导稍复杂面试、大链表、内存敏感5.1 面试建议强烈推荐使用快慢指针法因为这是本题的标准解法体现了 Floyd 判圈算法的精髓面试官常考数学推导需要能够清晰解释x (n-1)(yz) z的含义满足 O(1) 空间的进阶要求。回答要点先讲快慢指针判断有环再画图推导入口公式最后说明如何利用该公式找到入口。5.2 常见误区误以为相遇点就是环入口不一定相遇点可能在环内任意位置需要二次推导。认为需要统计环的长度不需要直接利用上述数学关系即可。忘记处理无环情况必须判断fast null或fast.next null提前返回。5.3 扩展思考如果要求返回环的长度可以在快慢指针第一次相遇后固定其中一个指针另一个指针继续绕环一圈再次相遇时的步数即为环长。如果要求恢复原链表即断开环可以在找到入口后遍历到入口的前一个节点将其next置为null。六、相关链接题目链接142. 环形链表 II - 力扣LeetCode官方题解环形链表 II 官方题解141. 环形链表LeetCode 141 题解