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

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
阶段二：寻找环的入口
      当兔子追上龟时，让龟 到起点  兔子保持再原地不变
      龟和兔子一次都走一步
      当再次相遇就是环的入口

原理：
从起点开始  走a步走到环的入口  环一圈的长度是：b     结论：走a步 + 绕环n圈就能到环的入口

如果有环  兔子和龟一定可以相遇

1：兔子走的距离：a + 绕环n1圈 + k(相遇时候距离 环入口的位置)
2：龟走的距离： a + 绕环n2圈 + k(相遇时候距离 环入口的位置)
3：兔子走的距离 = 2 * 龟走的距离
由上面的三个公式：推导
由1 2 3 式堆到：龟走的距离 = 兔子走的距离 - 龟走的距离 = 绕环n圈  设是w倍的圈数 设为n3
龟的距离是2式子  a + n2 + k = n3   n3 和n2 都是 绕环n圈的距离 但是 a + n2 + k = n3 说明 n2 和n3 中间差了一圈 这个一圈的距离是 a + k来弥补的 
所以 龟 和 兔子再走a步 就能到环口   但是a不知道  所以让随意一个回到起点 同时走a步即可到环口
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode fast = pHead;
        ListNode slow = pHead;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                slow = pHead;
                // 这个是一个特殊情况 这个链表直接就是一共环  你让随便一个回到起点 起点就是 环口 直接返回
                if (slow == fast) {
                    return slow;
                }
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }
}