题解 | #链表中环的入口结点#

数学原理：

v1 = x, v2 = 2x 相遇时s2 = 2*s1

假设起点到入口为 X，入口到相遇点为 Y，环长L。则有：s1 = X + Y; s2 = (X+Y)+L；

由于 s2 = 2s1,

所以 （X+Y）+ L = 2（X+Y），

那么，L = X+Y；

相遇点是 X+Y 处，也就是说，无论快慢指针只需要再走 X，就能走到环的起点处。因此，我们可以创造条件如下：

慢指针 low 从头开始走，走 X 的距离正好是环的起点，

快指针 fast 降到慢指针的速度继续往前走，走 X 的距离正好是环的起点，

这样，快慢指针以相同速度在起点处相遇，循环结束。同时，也找到了起点位置。

这里也说明，数学算法确实可以省钱（内存）～～～

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) {
            return null;
        }

        ListNode head = pHead;

        // 初始化快慢指针
        ListNode slow = head;
        ListNode fast = head;

        // 第一步：使用快慢指针检测是否有环
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 第二步：找到环的入口
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow; // 环的入口节点
            }
        }
        return null;
    }
}