Floyd 判圈算法（Floyd’s Cycle Detection Algorithm）

什么是 Floyd 判圈算法？

Floyd 判圈算法，也叫 龟兔赛跑算法（Tortoise and Hare Algorithm），是一种用于检测链表中是否存在环的算法。该算法由 Robert W. Floyd 提出，旨在通过两个不同速度的指针遍历链表来判断链表是否存在循环。其时间复杂度为 O(n)，空间复杂度为 O(1)，因此在效率和资源占用方面非常优越。

算法原理

Floyd 判圈算法使用两个指针：

慢指针（Tortoise）：每次移动一步。
快指针（Hare）：每次移动两步。

如果链表中存在环，那么快指针和慢指针最终会在环中相遇。如果链表中不存在环，快指针会先到达链表的末端。

主要步骤如下：

初始化两个指针：慢指针 slow 和快指针 fast 都指向链表的头部。
快指针每次移动两步，慢指针每次移动一步。
如果快指针和慢指针在某个时刻相遇，则说明链表中存在环。
如果快指针到达 null（链表的末尾），则说明链表中没有环。

代码实现

下面是使用 Python 实现的 Floyd 判圈算法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def has_cycle(head):
    slow = head
    fast = head
    
    while fast is not None and fast.next is not None:
        slow = slow.next          # 慢指针每次移动一步
        fast = fast.next.next     # 快指针每次移动两步
        
        if slow == fast:          # 如果相遇，则存在环
            return True
    
    return False                  # 如果遍历结束没有相遇，则不存在环

示例解释

假设我们有一个链表，如下所示：

1

1 -> 2 -> 3 -> 4 -> 5 -> 2 (环)

在此例中，节点 5 指向节点 2，形成了一个环。使用上述代码，快慢指针最终会在环中相遇，从而检测出链表中存在环。

算法复杂度分析

时间复杂度：O(n)，其中 n 是链表的节点数量。虽然快指针每次走两步，但整体仍然是线性时间复杂度，因为每个节点最多会被访问两次。
空间复杂度：O(1)，因为该算法只使用了两个额外的指针，不需要额外的空间存储其他数据。

应用场景

Floyd 判圈算法主要用于检测链表中的环，但它在其他问题中也能发挥作用，例如：

图的遍历中用于检测循环路径。
编译器中检测循环依赖。
动态数据结构中检测重复模式或回路。

总结

Floyd 判圈算法是一种高效且简单的算法，适用于检测链表中的环。相比于其他算法，它的优势在于时间复杂度和空间复杂度的平衡。在解决链表环问题时，这个算法是首选之一。如果你正在处理链表结构或者需要在图结构中寻找循环，Floyd 算法将是一个强大的工具。