142. 环形链表 II (Medium)
专题归类： 04-链表 LeetCode 链接： https://leetcode.cn/problems/linked-list-cycle-ii/
在线做题： 写 Python 代码并运行 · Java 跳转 LeetCode
题目描述
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递。
示例：
- 输入：head = [3,2,0,-4], pos = 1
- 输出：返回索引为 1 的节点
题目详细分析
- 数据范围： 链表中节点数在 [0, 10^4] 范围内，节点值在 [-10^5, 10^5] 范围内
- 输入特征： 与 141 题相同，但需要不仅判断是否有环，还需要找到环的入口
- 核心约束： 进阶要求 O(1) 空间，不能使用哈希表
- 隐藏条件： 环入口的确定需要借助数学推导——快慢指针相遇点到入口的距离等于头节点到入口的距离
- 边界条件： 无环返回 None、头节点就是环入口（头节点被包含在环中）、整个链表是一个环
小白版直白理解
还是那个环形跑道的例子，但这次不仅要判断有没有环，还要找到环的入口在哪里（即从哪里开始进入环的）。
Floyd 发现了一个巧妙的规律：如果两个人在跑道上相遇了，让一个人回到起点，然后两个人以相同速度走，他们再次相遇的地方就是环的入口。这个规律可以用数学证明，就像解一个追及问题的方程。
解题思路
思路一：Floyd 判圈法（快慢指针 + 数学推导，推荐）
为什么这样想： 快慢指针相遇后，我们需要知道环入口的位置。通过数学推导发现一个关键等式：从 head 到环入口的距离 = 从相遇点到环入口的距离（沿着前进方向）。
数学推导： 设 head 到入口距离为 a，入口到相遇点距离为 b，相遇点到入口距离为 c（环剩余部分）。
- slow 走的距离：a + b
- fast 走的距离：a + b + c + b = a + 2b + c（fast 在环里多走了一圈多）
- 因为 fast 走的距离 = 2 * slow 走的距离：a + 2b + c = 2(a + b) → c = a
所以从 head 和相遇点同步出发，相遇处就是入口。
def detectCycle(head):
"""Floyd 判圈法：快慢指针 + 数学推导"""
if not head or not head.next:
return None
# 第一阶段：快慢指针相遇
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# 第二阶段：找环入口
slow = head # 一个指针回到头节点
while slow != fast:
slow = slow.next
fast = fast.next
return slow # 再次相遇点即环入口
return None # 无环思路二：哈希集合法
思路讲解： 遍历链表，将节点存入哈希集合。遇到的第一个已经存在于集合中的节点就是环的入口。思路简单直观，但需要 O(n) 空间。
def detectCycle(head):
"""哈希集合法"""
visited = set()
cur = head
while cur:
if cur in visited:
return cur # 第一个重复的就是入口
visited.add(cur)
cur = cur.next
return None思路三：先判环再数环长法
思路讲解： 先找相遇点，然后从相遇点绕环一圈数出环的长度 L。再用两个指针，一个先走 L 步，另一个从头出发，它们相遇的地方就是环入口。
def detectCycle(head):
"""先找环长再找入口"""
if not head or not head.next:
return None
# 找相遇点
slow, fast = head, head
has_cycle = False
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
has_cycle = True
break
if not has_cycle:
return None
# 计算环的长度
cycle_len = 1
p = slow.next
while p != slow:
cycle_len += 1
p = p.next
# 找入口：一个先走 cycle_len 步
p1, p2 = head, head
for _ in range(cycle_len):
p1 = p1.next
while p1 != p2:
p1 = p1.next
p2 = p2.next
return p1易错点
- 第二阶段指针速度相同： 找到相遇点后，两个指针都一次走一步，不是快慢指针了
- 起点设置： 第二阶段必须让其中一个指针回到 head，另一个留在相遇点，然后同时移动
- 无环处理： 如果第一阶段没有相遇，直接返回 None，不进入第二阶段
- 空链表和单节点： 空链表或只有一个自环的节点需要处理——如果是自环则返回 head，无环则返回 None
- 头节点就是入口： 如果头节点就在环中，此时 a = 0，第一阶段 slow 和 fast 在 head 相遇，第二阶段直接返回 head
框架提炼
Floyd 判圈完整模板： 判环 + 找环入口。
def detect_cycle(head):
if not head or not head.next:
return None
# 阶段一：判环
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
# 阶段二：找入口
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
return None数学本质： a = c（头到入口距离 = 相遇点到入口距离）。这个等式成立的前提是 fast 比 slow 多走了一圈（即相遇时 fast 在环中多绕了一圈）。如果环很小，fast 可能多走了多圈，但等式 a = c 的变体依然成立：a = c + k * L（L 为环长），但从 head 出发的指针走 a 步，从相遇点出发的指针走 c 步加 k 圈，两者最终还是在入口相遇。