环形链表
本文详细讲解 LeetCode 141. 环形链表的 Floyd 判环算法（龟兔赛跑），包含原理证明和 Python 代码实现。
阅读要点
- Floyd 判环算法使用快慢指针，空间复杂度 O(1)。
- 快慢指针在环中必然相遇，因为相对速度为 1。
- 相遇后重置快指针到头结点，再同步移动可找到环入口。
题目
解法
最简单的做法是用哈希集合记录出现过的节点，但空间复杂度为 O(n)。本文重点介绍 Floyd 判环算法（龟兔赛跑算法），空间复杂度仅为 O(1)。
核心思想：使用快慢两个指针，从链表头同时出发。慢指针每次走一步，快指针每次走两步。如果链表中有环，快指针最终会追上慢指针，且可以根据相遇点推出环的入口位置。
为何一定相遇
假设链表存在环，快指针和慢指针进入环后，快指针相对于慢指针的速度为 1 步/次（快指针每次比慢指针多走一步）。由于环是有限的，快指针必然在有限步数内追上慢指针。例如，在一个长度为 b 的环中，最坏情况下快指针需要追 b-1 步即可相遇。
如何求出环的入口位置
设定参数如下：
- a：链表头结点 H 到环入口 E 的距离（步数）。
- b：整个环的长度（步数）。
- k：从环入口 E 出发，沿环的方向走到第一次相遇点 M 的距离（步数），显然 0 ≤ k < b。
推导：
设慢指针走过的距离为 s，则快指针走过的距离为 2s。相遇时，快指针比慢指针多走了 n 圈环的长度，即 2s = s + n * b，所以 s = n * b。
慢指针从起点到相遇点的距离为 a + k，因此 a + k = n * b。
整理得 a = n * b - k = (n - 1) * b + (b - k)。
这意味着从起点出发走 a 步，与从相遇点出发走 (b - k) 步（即逆时针方向）会到达同一点——环入口。因此，将快指针重置到头结点，然后快慢指针各走一步，再次相遇的节点即为环入口。
举例说明：假设环的长度 b = 5，头结点到环入口距离 a = 2，环入口到相遇点距离 k = 3。那么慢指针走过的距离 s = a + k = 5，快指针走过的距离 2s = 10，快指针比慢指针多走了 5 步，正好一圈。根据公式 a = (n-1)*b + (b-k)，取 n=1，得 a = 0 + (5-3)=2，与假设一致。
代码
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
# 没有节点或只有一个节点
if not head or not head.next:
return False
fast, slow = head, head
while fast and fast.next and slow:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False返回环入口的代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next:
return None
fast, slow = head, head
while fast and fast.next and slow:
fast = fast.next.next
slow = slow.next
if fast == slow:
pt = head
while pt != slow:
pt = pt.next
slow = slow.next
return slow
return None扩展思考
如果题目要求返回环的入口节点，可以在检测到相遇后，将快指针重置到头结点，然后快慢指针各走一步，再次相遇的节点即为环入口。代码只需稍作修改。
复杂度分析：时间复杂度 O(n)，其中 n 为链表节点数。空间复杂度 O(1)，只使用了两个指针。