Floyd判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法，该算法可以：

• 判断链表是否有环
• 计算环的长度
• 寻找环的起点

原理：可以想象两个人在操场上跑步，A跑得快，B跑得慢。A领先，然后在超过B一圈的地方和B相遇，假设A和B的步伐是匀速的，那么他们相遇的位置一定是起始位置，因为超过的一定是圈的N倍。

判断链表是否有环

【快慢指针】定义两个指针，慢指针slow（每次前进一步），快指针（fast）每次前进两步，这里只要fast比slow前进的快即可，但前进步长太多会增加代码运行时间，所以采用步长2。

• 若无环，fast先走到终点；若有环，最终slow和fast相遇，且fast比slow多走了N圈
• 因此循环的结束条件为要么快的先为null，要么slow==fast
• 初始化slow=head，fast=head.next，是因为如果fast初始化为head，那循环的第一个条件slow!=fast永远都不成立

public boolean isLoop(Node head) {
    if (head == null) {
        return false;
    }
    Node slow = head;
    Node fast = head.next;
    // fast比slow快，判空仅判断fast即可。
    // fast != null && fast.next != null因为fast每次走过两个格，不确定此时在最后一个位置还是在空位置，因此都需判断
    while (slow != fast && fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow == fast;
}

计算环的长度

当slow和fast相遇时，说明存在环，然后用一指针从相遇点走，直到走回来，记录长度。没有环长度返回0

public static int length(ListNode head) {
        if (head == null) {
            return 0;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast && fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        // 确定有环，开始计算长度
        if (slow == fast) {
            int num = 1;
            ListNode temp = slow.next;
            while (temp != slow) {
                temp = temp.next;
                num++;
            }
            return num;
        }
        return 0;
    }

寻找环的起点

• 若slow和fast从环内同一起点出发，那么再次相遇的位置一定是起点
• 若slow和fast从环内不同起点出发，那么再次相遇的位置会发生偏移
• 若slow和fast从环外同一起点出发，在进入环之前还有一段距离，因此相遇的位置不一定就是起点

解法一【无需知道环的长度】：

假设：环的长度为L，非环部分长度为a，快慢指针相遇的地方距离环的入口位置为b。slow走过的圈数为N(slow)，fast走过的圈数为N(fast)

此时：

• slow走过的长度为：a+N(slow) * L+b
• fast走过的长度为：a+N(fast) * L+b

因此此时两者的差值为N(圈)的整数倍。然后将slow挪至最开始的起点，同时fast和slow开始同时移动步长1直至相遇。

• 由于fast移动步长为2，当slow和fast相遇，fast走过的路长是slow的两倍，假设slow走过的总距离为S，那么fast总距离则为2S
• 而fast与slow总距离差为环长L的整倍数，因此S总距离就是环长L的整数倍
• 当slow从起点走到入口，走过的距离为a；fast从相遇位置走距离a，共走过距离为2S+a
• 因此fast从起点开始，走过了2S+a的路程，去掉前面的a，2S又是环长的整数倍，此时即为入口处，且slow和fast相遇。

以上所有的计算都是以slow和fast同一起点出发计算

public static ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                // 相遇后，将slow挪至起点
                slow = head;
                while (slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                return slow;
            }
        }
        return null;
    }

解法二【需要知道环的长度】：代码略

首先知道环的长度为L，非环部分长a。将快慢指针同时指向头结点。快指针首先移动距离L后，慢指针开始移动，其相遇时就在环的入口，此时fast走过的距离为a+L，slow走过的距离为a，因此fast-slow=L，刚好一圈。