Floyd 判圈算法

贡献者： int256

1. Floyd 判圈算法

　　首先需要注意的一点，Floyd 判圈算法不是 Floyd 全源最短路算法。Floyd 判圈算法是用来判断链表中是否有圈（或环）的存在的。

　　 Floyd 判圈算法（又称为 Floyd 判环算法或龟兔赛跑算法）的思想类似于快慢指针。原理是 “龟兔赛跑”，慢指针每次向前移动 $1$ 步、快指针每次向前移动两步。如果两者在遍历链表的过程中相遇，则说明链表存在一个圈；如果快指针达到了链表的结尾（有尾则一定无环），说明链表无环。

　　下面给出一个常见的实现方法：

bool hasCyc(ListNod* head) {
    if(head == nullptr)  return false;
    ListNod *slow = head, *fast = head;
    fast = fast -> next;

    while(fast != nullptr && fast -> next != nullptr) {
        if(slow == fast)  return true;
        slow = slow -> next;
        fast = fast -> next -> next;
    }
    
    return false;
}

2. Floyd 判圈算法的拓展

求环的长度

　　在找到环后可以很容易地求出环的长度，固定 fast 快指针不动，然后让 slow 慢指针一直移动直到再与 fast 快指针相遇，这移动的距离恰好就是环的长度。

求环的起点

　　假设链表是类似于如下形式：

图 1：链表示意图

　　不失一般性地，考虑这个环的逆时针走的。

　　设环长 $L$ （可以通过刚才的方法求出），非环部分（也就是头节点到环）长 $a$ ，环的起点到快慢指针第一次相遇点的距离为 $b$ （对应图的劣弧部分）、剩余的优弧长 $c = L - b$ 。设快指针走了 $f$ 圈、慢指针走了 $s$ 圈。

　　而我们知道，快慢指针速度是两倍关系，而 $s_{f a s t} = a + b + f L$ 、 $s_{s l o w} = a + b + s L$ ，故 $s_{f a s t} = 2 s_{s l o w}$ ，故 $(f - 2 s) L = a + b$ ，即 $a + b$ 是 $L$ 的整数倍。不妨设 $a + b = k L$ ，即 $a + b = k (b + c)$ ，则 $a = (k - 1) (b + c) + c$ 。所以我们可以让一个指针停留在首次相遇位置，另一个指针回到起点。这两个指针以相同速度同时再出发，必定会在环起点的位置相遇。

　　注意这里，快慢指针要从同一起点出发。快指针 fast 不可以先走一步。

ListNod* getCycBeginNod(ListNod* head) {
    if(head == nullptr)  return nullptr;
    ListNod *slow = head, *fast = head;

    while(fast != nullptr && fast->next != nullptr) {
        slow = slow -> next, fast = fast -> next -> next;
        if(slow == fast) {
            // 发现环后, 一指针停留，另一指针回起点
            slow = head;
            while(slow != fast) {
                slow = slow -> next, fast = fast -> next;
            }
            return slow;
        }
    }
    return nullptr;
}