0142.环形链表 II
难度：🟡 中等
标签：哈希表、链表、双指针
链接：142. 环形链表 II
题目描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 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
解释：链表中没有环。
解题思路
核心思想
本题是“环形链表”问题的进阶，不仅要判断是否存在环，还要找到环的入口节点。解决此问题的最优方法是 弗洛伊德的龟兔赛跑算法（Floyd's Cycle-Finding Algorithm），它分为两个阶段：
相遇：使用快慢指针，快指针每次走两步，慢指针每次走一步。如果它们能够相遇，则证明链表中存在环。
寻找入口：当快慢指针相遇后，将其中一个指针（例如，一个新的指针
ptr）放回链表头部head，然后让ptr和相遇点的慢指针slow同时以每次一步的速度前进。它们再次相遇的节点，就是环的入口。
思路选择
快慢指针法 是解决此问题的标准最优思路，因为它不需要额外的存储空间，空间复杂度为 O(1)。
第一阶段（判断环并相遇）：与判断环形链表（141题）的逻辑完全相同。
第二阶段（寻找入口）：这一步的正确性基于一个数学推导。设链表头到环入口的距离为
a，环入口到相遇点的距离为b，相遇点再到环入口的距离为c。当快慢指针相遇时，慢指针走了a+b的距离，快指针走了a+b+k(b+c)（其中k是快指针在环内多跑的圈数）。因为快指针速度是慢指针的两倍，所以2(a+b) = a+b+k(b+c)，化简得a = k(b+c) - b = (k-1)(b+c) + c。这个公式的物理意义是：从头节点到环入口的距离a，等于从相遇点到环入口的距离c再加上k-1圈环的长度。因此，一个指针从head出发，另一个指针从相遇点出发，都以相同速度前进，它们必然会在环的入口相遇。
关键步骤
初始化：创建快慢指针
fast和slow，都指向头节点head。第一阶段：寻找相遇点： a. 在循环中，
fast每次移动两步，slow每次移动一步。 b. 如果fast到达链表末尾 (null)，说明无环，返回null。 c. 如果fast === slow，说明相遇，跳出循环。第二阶段：寻找入口点： a. 创建一个新的指针
finder，指向头节点head。 b. 同时移动finder和slow指针，每次都移动一步。 c. 当finder === slow时，它们相遇的节点就是环的入口，返回该节点。
代码实现
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function (head) {
let slow = head, fast = head;
while (fast !== null && fast.next !== null) {
fast = fast.next.next;
slow = slow.next;
// 快慢指针相遇
if (fast === slow) {
let finder = head;
// 从头节点和相遇点同时出发
while (finder !== slow) {
finder = finder.next;
slow = slow.next;
}
// 再次相遇点即为环的入口
return finder;
}
}
// 没有相遇，说明无环
return null;
};
复杂度分析
时间复杂度：O(n) 其中 n 是链表的长度。两个阶段的遍历都与链表长度成线性关系。
空间复杂度：O(1) 我们只使用了常数个额外变量作为指针，空间消耗是恒定的。
相关题目
总结
本题是快慢指针技巧的深度应用，完美地展示了该算法不仅能判断环的存在，还能精确定位环的入口。理解其背后的数学原理是掌握此算法的关键，也是面试中常被追问的要点。