介绍

阶段1(判断是否有环)
龟一次走一步，免子一次走两步。
当兔于能走到终点时，不存在环。
当兔子能追上龟时，可以判断存在环
阶段2(判断环的入口)
从它们第一次相遇开始，龟回到起点(注意特殊情况)，兔于保持原位不变。
龟和兔子一次都走一步
当再次相遇时，地点就是环的入口

题目

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

题解

弗洛伊德龟兔赛跑算法

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode t = head; //兔子
        ListNode g = head; //乌龟
        while (t != null && t.next != null) {
            g = g.next;
            t = t.next.next;
            if (t == g) { //相遇
                g = head; //乌龟回到起点
                while (true) {
                    if (g == t) { //判断是否相遇，排除特殊情况
                        return t;
                    }
                    t = t.next;
                    g = g.next;
                }
            }
        }
        return null;
    }
}