如何判断一个链表是否有环

# 1. 链表基础知识**

链表是一种线性数据结构，由一系列节点组成，每个节点包含一个数据元素和指向下一个节点的指针。链表用于存储有序数据，并且可以动态地插入和删除元素。链表的优点在于插入和删除操作的时间复杂度为 O(1)，而数组的插入和删除操作则为 O(n)。

链表的常见操作包括：

* **插入：**在链表中插入一个新元素。
* **删除：**从链表中删除一个元素。
* **查找：**在链表中查找一个元素。
* **遍历：**访问链表中的所有元素。

# 2. 判断链表是否有环的理论基础

### 2.1 弗洛伊德判圈算法

弗洛伊德判圈算法是一种经典的判断链表是否有环的算法，其原理是：

1. 设置两个指针，一个称为快指针（fast），另一个称为慢指针（slow）。
2. 从链表的头结点开始，让快指针每次移动两步，慢指针每次移动一步。
3. 如果链表中有环，那么快指针最终会追上慢指针。

**算法流程：**

graph LR
subgraph 弗洛伊德判圈算法
    start[开始] --> slow[慢指针] --> [移动一步] --> slow
    slow --> fast[快指针] --> [移动两步] --> fast
    fast --> [判断 fast == slow] --> yes[有环]
    yes --> end[结束]
    no --> slow
end

**代码实现：**

def has_cycle_floyd(head):
    """
    弗洛伊德判圈算法

    :param head: 链表的头结点
    :return: 是否有环
    """
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

**逻辑分析：**

1. 初始化慢指针和快指针，都指向链表的头结点。
2. 进入循环，每次让慢指针移动一步，快指针移动两步。
3. 如果链表中有环，那么快指针最终会追上慢指针，此时返回 True。
4. 如果链表中没有环，那么快指针会一直移动到链表的末尾，此时返回 False。

### 2.2 快慢指针法

快慢指针法也是一种判断链表是否有环的算法，其原理与弗洛伊德判圈算法类似，但实现方式略有不同。

**算法流程：**

graph LR
subgraph 快慢指针法
    start[开始] --> slow[慢指针] --> [移动一步] --> slow
    slow --> fast[快指针] --> [移动一步] --> fast
    fast --> [判断 fast == slow] --> yes[有环]
    yes --> end[结束]
    no --> slow
end

**代码实现：**

def has_cycle_fast_slow(head):
    """
    快慢指针法

    :param head: 链表的头结点
    :return: 是否有环
    """
    if not head or not head.next:
        return False

    slow = head
    fast = head.next

    while slow != fast:
        if not fast or not fast.next:
            return False

        slow = slow.next
        fast = fast.next.next

    return True

**逻辑分析：**

1. 判断链表是否为空或只有一个结点，如果是，则返回 False。
2. 初始化慢指针和快指针，慢指针指向头结点，快指针指向头结