一、算法介紹

Floyd 龜兔賽跑算法（也稱(chēng)為 Floyd 判圈算法或 Floyd 循環(huán)檢測(cè)算法）
是一種用于檢測(cè)鏈表中是否存在環(huán)的算法。如果鏈表上存在環(huán)，那么在環(huán)上以不同速度前進(jìn)的兩個(gè)指針必定會(huì)在某個(gè)時(shí)刻相遇。

1.判斷是否有環(huán)

龜一次走一步，兔子一次走兩步：

• 當(dāng)兔子能走到終點(diǎn)時(shí)，不存在環(huán)
• 當(dāng)兔子能追上龜時(shí)，存在環(huán)

2.尋找環(huán)入口

從它們第一次相遇開(kāi)始，龜回到起點(diǎn)，兔子保持原位不變

• 龜和兔子一次都走一步
• 當(dāng)再次相遇時(shí)，地點(diǎn)就是環(huán)的入口

設(shè)起點(diǎn)到環(huán)入口長(zhǎng)度為步，環(huán)的長(zhǎng)度為步，那么步的長(zhǎng)度為環(huán)的入口處。(因?yàn)榄h(huán)的長(zhǎng)度是y，一個(gè)y就是從起點(diǎn)到終點(diǎn)，n個(gè)y就是重疊了n次，還是在入口處)

第一次相遇龜和兔走的路程：

• （必須是在繞環(huán)的過(guò)程中才能追上龜）
• （）

因?yàn)橥米拥木嚯x是烏龜?shù)膬杀叮ㄍ米右淮?步，烏龜一次1步），所以：

所以烏龜走的距離正好是整數(shù)倍的環(huán)長(zhǎng)度，即。
根據(jù)前面環(huán)入口處的長(zhǎng)度為，所以，在烏龜和兔子相遇之后，烏龜只需要再走步，此時(shí)距離就為，即環(huán)入口的長(zhǎng)度。

此時(shí)，要計(jì)算出為具體為多少，可以讓兔子模擬烏龜（即每次只走一步），那么兔子需要前進(jìn)步走到環(huán)入口；讓烏龜回到起點(diǎn)，烏龜前進(jìn)步也能走到環(huán)入口，所以的值就是他們相遇時(shí)候所走的步數(shù)；即相遇的點(diǎn)就是環(huán)的入口。

二、Leetcode141.環(huán)形鏈表（判斷是否有環(huán)）

判斷是否有環(huán)：
使用兩個(gè)指針，一個(gè)快指針和一個(gè)慢指針，分別以不同的速度遍歷鏈表，兩個(gè)指針相遇代表有環(huán)，否則無(wú)環(huán)。

    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (true) {
            fast = fast.next.next;
            slow = slow.next;
            // 有環(huán)
            if (fast == slow) {
                return true;
            }
            // 無(wú)環(huán)
            if (fast == null || fast.next == null) {
                return false;
            }
        }
    }

三、Leetcode142.環(huán)形鏈表II（尋找環(huán)入口）

尋找環(huán)的入口：
在第一次相遇后，將 slow 指針重新指向鏈表頭節(jié)點(diǎn)，然后 slow 和 fast 指針都以相同的速度（每次移動(dòng)一步）前進(jìn)，當(dāng)它們?cè)俅蜗嘤鰰r(shí)，相遇點(diǎn)即為環(huán)的入口點(diǎn)。

    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (true) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                // 相遇 讓slow回到起點(diǎn)
                slow = head;
                while (fast != slow) {
                    // 分別前進(jìn)一步
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
            if (fast == null || fast.next == null) {
                return null;
            }
        }
    }