# 链表中环的入口 给定一个链表，若其中包含环，则输出环的入口节点。 若其中不包含环，则输出 `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; } } ```