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

 # 1. 链表基础知识** 链表是一种线性数据结构，由一系列节点组成，每个节点包含一个数据元素和指向下一个节点的指针。链表用于存储有序数据，并且可以动态地插入和删除元素。链表的优点在于插入和删除操作的时间复杂度为 O(1)，而数组的插入和删除操作则为 O(n)。 链表的常见操作包括： * **插入：**在链表中插入一个新元素。 * **删除：**从链表中删除一个元素。 * **查找：**在链表中查找一个元素。 * **遍历：**访问链表中的所有元素。 # 2. 判断链表是否有环的理论基础 ### 2.1 弗洛伊德判圈算法 弗洛伊德判圈算法是一种经典的判断链表是否有环的算法，其原理是： 1. 设置两个指针，一个称为快指针（fast），另一个称为慢指针（slow）。 2. 从链表的头结点开始，让快指针每次移动两步，慢指针每次移动一步。 3. 如果链表中有环，那么快指针最终会追上慢指针。 **算法流程：** ```mermaid graph LR subgraph 弗洛伊德判圈算法 start[开始] --> slow[慢指针] --> [移动一步] --> slow slow --> fast[快指针] --> [移动两步] --> fast fast --> [判断 fast == slow] --> yes[有环] yes --> end[结束] no --> slow end ``` **代码实现：** ```python 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 快慢指针法 快慢指针法也是一种判断链表是否有环的算法，其原理与弗洛伊德判圈算法类似，但实现方式略有不同。 **算法流程：** ```mermaid graph LR subgraph 快慢指针法 start[开始] --> slow[慢指针] --> [移动一步] --> slow slow --> fast[快指针] --> [移动一步] --> fast fast --> [判断 fast == slow] --> yes[有环] yes --> end[结束] no --> slow end ``` **代码实现：** ```python 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. 初始化慢指针和快指针，慢指针指向头结点，快指针指向头结