单链表：寻找环形链表的入口点_判断环形链表入口

1、在寻找环形链表的入口之前，如何判断链表是环形的？

定义两个指针fast和slow，fast每次走两步，slow每次走一步，如果fast和slow可以相遇，说明链表带环。

2、如何找到环形链表的入口？

如图是一个环形链表。

设a点为链表头结点，b点为环的入口点，c点为fast和slow的第一次相遇点。

设ab长度为x，bc长度为y，z为环的长度。

则fast在相遇前走的距离应该是：x+nz+y（n为fast运动的圈数）。

slow的距离：x+y。

因为fast的速度是slow的二倍；

则有：2（x+y）= x+nz+y

                   x+y = nz

                       x = nz - y

当n为1的时候，x = z - y ，z是环的长度，可知 m = x，正好是第一次相遇点和环的入口点的距离。

此时让一个引用slow或者fast从头结点开始走，另一个引用在第一次相遇点，两个引用同时走，每次走一步，，下次相遇点就是环的入口点。

代码如下：

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