1.问题描述

Floyd判圈算法(Floyd Cycle Detection Algorithm)，又称龟兔赛跑算法(Tortoise and Hare Algorithm),是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，以及判断环的起点与长度的算法。

2.判断是否有环

可以把链表比作操场的环形跑道，当两个人以不同的速度一直跑下去时，总有一个时间点，跑得快的人会追上跑得慢的人，这时就必定存在环。

以这样的思路类推，在链表中，我们使用两个不同速度的指针，遍历该链表，当两个指针相遇时，即存在环路。如果快指针达到末尾了，那么说明该链表不存在环路。

3.找出环的起点

假设出发点到环的起点的距离是m

环的长度为n

第一次相遇时，慢指针走过a圈，快指针走过b圈，指针到环的起点的距离是k

那么，当两指针第一次相遇时，慢指针走过的距离是slow = m + a * n + k

慢指针走过的距离是fast = m + b * n +k

当快指针的速度是慢指针的2倍时，有fast = 2 * slow

则slow = (b - a) * n

此时，将快指针移到链表的起点，快指针和慢指针每次都前进一步

当快指针走过m步时，慢指针也走过m步，此时慢指针走过的距离是(b - a) * n + m

由于m是出发点到环的起点的距离，所以此时慢指针和快指针所在的位置即是环的起点

代码实现：

ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    // 判断是否存在环路
    do {
        if (!fast || !fast->next) return nullptr;
        fast = fast->next->next;
        slow = slow->next;
    } while (fast != slow);    
    // 如果存在，查找环路节点
    fast = head;
    while (fast != slow){
    slow = slow->next;
    fast = fast->next;
    }
    return fast;
}