你如何用Floyd的龟兔算法检测循环？

Question

你如何用Floyd的龟兔算法检测循环？

Accepted Answer

**Floyd's cycle detection** 使用两个以不同速度移动的指针在序列（如链表）中寻找循环。如果循环存在，快指针最终会追上并与慢指针相遇。它使用 **O(1)** 额外空间。

## 思路

将 **slow** 指针向前移动一步，将 **fast** 指针向前移动两步。在循环中，间距每步减少一个，所以它们必然会碰撞；不存在循环时，快指针到达末尾。

## 示例

```python
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next            # +1 step
        fast = fast.next.next       # +2 steps
        if slow is fast:            # pointers met -> cycle
            return True
    return False                    # fast hit the end -> no cycle
```

## 复杂度

- **时间：** O(n)。**空间：** O(1)。

哈希集合方法也可行，但需要 O(n) 空间；Floyd 算法使用常数空间。

## 何时使用 / 陷阱

用于 **链表循环检测**、查找循环的起始点以及在函数图中检测循环（每个节点有一个后继）。始终保护 `fast.next` 以避免空指针解引用。对于一般图，改用具有递归栈的 DFS。

## 为什么这很重要

循环检测对于安全的遍历至关重要——未检测到的循环意味着无限迭代。

Floyd 算法是一个漂亮的例子，展示了如何用巧妙的不变量将一个 O(n) 空间问题解决为 O(1) 空间。

它出现在链表面试中，以及在状态机和数列中检测无限循环的问题中。