# 链表中环的入口
给定一个链表,若其中包含环,则输出环的入口节点。
若其中不包含环,则输出 `null`
### 样例

给定如上所示的链表:
```
[1, 2, 3, 4, 5, 6]
2
```
注意,这里的 2 表示编号是 2 的节点,节点编号从 0 开始。所以编号是 2 的节点就是 val 等于 3 的节点。
则输出环的入口节点 3 .
### 思路及证明过程
- **快慢指针法**
```mermaid
graph LR
f{FAST} -->|2| 1((HEAD)) -->|X| 2((Entrance)) -->|Y| 3((ptr)) -->|Z| 4((net)) --> |Y| 2((Entrance))
s{SLOW} -->|1| 1((HEAD))
```
设两指针初始化指向 `HEAD` 节点,指针 每次移动 1 位,另一指针每次移动 2 位,它们先后进入环中(如果有环的话),并必然相遇于节点 `ptr`
设 `HEAD` 与 `Entrance` 之间的距离为 $X$ ,`Entrance` 与 `ptr` 之间的距离为 $Y$ ,当其相遇时,此时有 $L_{FAST}=2(X + Y)$, $L_{SLOW} = X + Y$
令 $P_{SLOW}=1$ 退 $Y$ 步到达 `Entrance` ,则 $P_{FAST}$ 回退 $2Y$ 步到达 `net` ,则此时 $L_{HEAD->net} = 2X$ , 且有 $L_{HEAD->Entrance} = X$ ,则有 $L_{Entrance->net} = X$ ,则可得出 $L_{Entrance->Entrance} = X + Y$
故只需令一节点 $P_{FAST}$ 返回 `HEAD` 节点,并使 $P_{FAST}$ 位移步长为 1 ,$P_{SLOW}$ 在 `ptr` 继续移动直到其相遇,相遇点就是环的入口
```mermaid
graph LR
1((HEAD)) -->|X| 2((Entrance)) -->|Y| 3((ptr)) -->|Z| 4((net)) --> |Y| 2((Entrance))
```
### Code
```java
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
class Solution {
public ListNode entryNodeOfLoop(ListNode head) {
ListNode ptr = head, net = head;
while (ptr != null && net != null) {
ptr = ptr.next; net = net.next;
if (net != null) {
net = net.next;
if (net == null) return null;
}
if (ptr == net) {
ptr = head;
while(ptr != net) {
ptr = ptr.next;
net = net.next;
}
return net;
}
}
return null;
}
}
```

链表中环的入口 -- 剑指 Offer