力扣链表
142. 环形链表 II
142. 环形链表 II
https://leetcode.cn/problems/linked-list-cycle-ii/
题目
给定一个链表的头节点 head，返回链表开始入环的第一个节点。如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。示例 2：
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。示例 3：
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。提示
- 链表中节点的数目范围在范围
[0, 10^4]内 -10^5 <= Node.val <= 10^5pos的值为-1或者链表中的一个有效索引
进阶： 你是否可以使用 O(1) 空间解决此题？
思路（快慢指针 / 弗洛伊德判圈法）
本题分为两步：先判断链表是否有环，再定位环的入口节点。经典解法是 Floyd 判圈算法（又称龟兔赛跑算法）：
- 判断是否有环：使用快慢指针，
slow每次走一步，fast每次走两步。如果链表存在环，两者一定会在环内相遇；如果fast走到null，则无环。 - 定位环入口：假设从头节点到环入口的距离为
a，环入口到相遇点的距离为b，相遇点回到环入口的距离为c。快慢指针相遇时：slow走了a + bfast走了a + b + n(b + c)（n为 fast 在环内绕的圈数）- 由于
fast速度是slow的 2 倍，有2(a + b) = a + b + n(b + c)，化简得a = (n - 1)(b + c) + c。 - 这意味着：从相遇点再走
a步，等价于在环内绕若干整圈后再走c步，最终一定停在环入口。 - 因此，相遇后将其中一个指针放回
head，两个指针每次各走一步，再次相遇的位置就是环入口。
该思路时间复杂度为 O(n)，空间复杂度为 O(1)。
解法
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
slow = fast = head
# 第一步：判断链表是否有环，并找到快慢指针相遇点
while fast and fast.next:
slow = slow.next # 慢指针每次走一步
fast = fast.next.next # 快指针每次走两步
if slow == fast:
# 第二步：找到环的入口节点
ptr = head
while ptr != slow:
ptr = ptr.next
slow = slow.next
return ptr
# fast 走到 None，说明链表无环
return None解释
| 代码片段 | 作用与原因 |
|---|---|
slow = fast = head | 初始化快慢指针，均从链表头部出发 |
while fast and fast.next: | 循环条件：快指针及其下一个节点均非空，确保可以走两步 |
slow = slow.next | 慢指针每次前进一步 |
fast = fast.next.next | 快指针每次前进两步，相对速度为 1，保证能追上慢指针 |
if slow == fast: | 快慢指针相遇，说明链表存在环 |
ptr = head | 相遇后，令 ptr 从头节点重新出发 |
while ptr != slow: | ptr 和 slow 同步前进，直到再次相遇 |
ptr = ptr.next; slow = slow.next | 两个指针每次各走一步，由于 a = c + k×圈长，最终会在环入口相遇 |
return ptr | ptr 与 slow 相遇的位置即为环的入口节点 |
return None | 链表无环时返回 null |