算法证明

a是起点，b是环的入口，c是两个指针第一次相遇的地方，d是c关于b对称的点，ab = x，bc = y，bd = x，db = y

first走x步，second走2x步，此时first走到了b点，second走到了d点，因为bd = x

first再向前走y步，走到c点，second会走2y步，然后在c点相遇，所以db = y

因为bc = y, bd = x, db = y,所以bd + db = x + y是一圈的整数倍

因为bd = bd + cd = y + cd = x,所以cb也等于x，那么让first从起点a开始走，second从c点开始走，每次都走一步，走x步就会相遇，相遇的地方就是环的入口

注意点

1：初始化要是初始化为 p = head,q = head.next 的话，在进行第二个循环的时候会出现死循环，因为无法保证p，q 距离环入口节点是相等的，总是会差1，那么p，q就永远不会相等。

所以 初始化一定要是 p = head.next, q = head.next.next;

2：在判断是否有环的时候，条件一定是 q == null || q.next == null，因为q是快指针，每次走两步，如果只判断q == null的话，会跳过一个节点，那么就无法顾及每个情况了,甚至会越过链表的长度。

不需要判断 p == null，因为q走的会比p快，如果没有环的话，会比p早点到尾节点。

java代码

class Solution {
    public ListNode entryNodeOfLoop(ListNode head) {

        ListNode first = head, second = head;
        while(first != null && second != null)
        {
            first = first.next;
            second = second.next;
            if(second.next == null) return null;
            else second = second.next;

            if(first == second)
            {
                first = head;
                while(first != second)
                {
                    first = first.next;
                    second = second.next;
                }
                return first;
            }
        }
        return null;
    }
}