题目
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/linked-list-cycle-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解法思路
两种解法，
1、单指针，遍历链表。利用哈希表存储每个访问过的节点，当访问的节点已在哈希表中存在时，这个节点就是入环位置。
python解法
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
# 使用集合存储节点，查找效率为O(1)
node_set = set()
pointer = head
while pointer:
# 当前访问节点已存在，说明遇到入环节点
if pointer in node_set:
return pointer
node_set.add(pointer)
pointer = pointer.next
# 未遇到环
return None
JavaScript解法
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
const nodeSet = new Set();
while (head !== null) {
if (nodeSet.has(head)) {
return head;
}
nodeSet.add(head);
head = head.next;
}
return null;
};
2、双指针，快慢指针。快指针每次移动两个节点，慢指针每次移动一个节点。第一次相遇，说明有环。然后新定义一个指针p，指向head，同时移动p和慢指针，每次均移动一个节点。当p和慢指针再次相遇时，就是入环点。
假设：
链表头节点到入环点距离 i
入环点到相遇点距离 j
相遇点继续前移到入环点距离 k
快指针遇到慢指针前在环内走了 n 圈
可以得到快指针一共走的距离是 n * (j + k) + i
慢指针走的距离是 i + j
又因为快指针走的距离是慢指针的2倍。得到等式 `n * (j + k) + j + i = 2 * (i + j)`
消减得到：n (j + k) = i + j -> j(n - 1) + nk = i
假定 n 为 1.得到： k == i
说明链表头节点到入环点的距离，等于相遇点继续前移到入环点的距离
python解法
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
# 解法2 快慢指针
fast, slow, p = head, head, head
is_cycle = False
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if fast == slow:
# 有环
is_cycle = True
break
if not is_cycle:
# 未找到环
return None
while p != slow:
p = p.next
slow = slow.next
return p
js解法
/**
* @param {ListNode} head
* @return {ListNode}
*/
var detectCycle = function(head) {
let fast = head;
let slow = head;
while (fast !== null && fast.next !== null) {
fast = fast.next.next;
slow = slow.next;
if (fast === slow) {
// 有环 找入环点
let p = head;
while (p !== slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
};
