环形链表的入口

链表是否有环可用使用快慢指针进行判断，快慢指针相遇则存在环。
在此基础上需要查找环的入口则需分析环形节点之间的关系。
使用set记录节点这种方式这里不讲很容易理解。

image.png

设 A 为起点到环入口节点的距离，B 为从环入口到快慢指针相遇节点的距离，C 为从快慢指针节点继续前进到再次到环入口节点的距离。
2A + 2B = A + n(B+C) + B
n为快指针在与慢指针相遇前在环内循环次数。
等式左边为两倍慢指针的距离，等式右边为快指针走的距离。
A = n-1(B+C)+ C
通过这个公式将P1指针指向起点，P2指针指向B,C节点就是快慢指针相遇节点。同时推进P1,P2。
当P1,P2相遇所在节点就是环的入口。

    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while(null != fast && null != fast.next){
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                fast = head;
                while(fast != slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
    }