链表 - 检测环 & 环入口点

对于链表检测是否有环，大家都知道 使用快慢指针就可以了。只要快慢指针可以相遇，那么链表一定是有环的。

一般我们都是对如何找到环入口点，以及为什么这个点就是入口点有疑惑。我们一步步来，我先告诉你如何找入口点，再告诉你为什么这个点就是入口点。

快指针：一步走2个结点
慢指针：一步走1个结点

如何找入口？
当快慢指针相遇时，我们把快指针移动到链表的头结点，然后把步伐设置为一步走1个结点。那么当快慢指针再次相遇时的结点，就是环的入口点。

为什么这个点是入口？
快慢指针第一次相遇时，快指针走了2N的结点，慢指针走了N个结点。
我们想一下，如果慢指针再走N步，是不是还是会回到当前和快指针相遇的这个点？那必然啊，再走N步，那么慢指针一共走了N+N = 2N个结点，和快指针走的结点一样了，那必然还是在相遇的这个点的位置。
那相遇到时候，我们把快指针移回到链表的头结点，步伐设置为一步一个节点，再走N步，是不是也会走到刚才快慢指针相遇的那个结点？这是废话，这不就把刚才的慢指针走过的节点又走了一遍，也必然是走到了刚才快慢相遇的节点了。

所以当第一次快慢指针相遇的时候，我们让慢指针接着走，快指针移回到头结点，并且步伐设置为1，在走N步，这时候快慢指针又会再次在同一个节点相遇。又因为快指针走了N个结点，慢指针也是N个结点，步伐此时都为1，那么它们2个相遇的节点，就一定是环的入口点了，毕竟步伐一样为1。

代码：

    private static ListNode findNode(ListNode node) {

        if (node == null || node.next == null) return null;
        
        ListNode quickNode = node;
        ListNode slowNode = node;

        //先判断是否有环,如果有环，找到相遇的结点
        do {
            quickNode = quickNode.next.next;
            slowNode = slowNode.next;
        } while (quickNode != null && quickNode.next != null && quickNode != slowNode);

        if (quickNode == null || quickNode.next == null) return null;

        quickNode = node;

        //找到环的入口
        while (quickNode != slowNode) {
            quickNode = quickNode.next;
            slowNode = slowNode.next;
        }

        return quickNode;
    }