题目
题解
# Definition for singly-linked list.# class ListNode:# def __init__(self, x):# self.val = x# self.next = NoneclassSolution:defdetectCycle(self,head:Optional[ListNode])->Optional[ListNode]:# 1、通过快慢指针的⽅式，在环中寻找它们的第⼀次相遇的节点位置# 2、定义⼀个慢指针，每次只会向前移动 1 步slow=head# 3、定义⼀个快指针，每次只会向前移动 2 步fast=head# 4、如果链表有环，那么⽆论怎么移动，fast 指向的节点都是有值的whilefast!=Noneandfast.next!=None:#慢指针每次只会向前移动 1 步slow=slow.next# 快指针每次只会向前移动 2 步fast=fast.next.next# 快慢指针相遇，说明有环# x 代表从头节点到环形⼊⼝节点的节点数（不包含头节点）# y 代表从环形⼊⼝到第⼀次相遇节点的节点数（不包含环形⼊⼝节点）# z 代表从第⼀次相遇节点到环形⼊⼝的节点数（不包含第⼀次相遇节点）# y + z 代表环的节点总数# 此时，快指针⾛了 x + y + n y + z)# 其中，x + y 表示快指针第⼀次到达相遇节点，n 代表快指针在环⾥⾯绕了多少圈# 此时，慢指针⾛了 x + y 步# 由于快指针每次⾛ 2 步，所以快慢指针第⼀次相遇的时候出现⼀个等式# x + y = [x + y + n y + z)] / 2# 即 2 * x + y) = x + y + n y + z)# 即 x + y = n（y + z）# 即 x = n（y + z）- y# 我们的⽬的就是去求 x# 定义两个指针，⼀个指向相遇节点，定义为 b，⼀个指向链表头节点，定义为 a# b 在环中绕圈圈，⾛了 n（y + z）步会回到原处，即回到相遇节点处# 由于 y 代表从环形⼊⼝到第⼀次相遇节点的节点数（不包含环形⼊⼝节点）# 所以 n（y + z） - y 时，b 到达了环形⼊⼝节点位置# 由于 x 代表从头节点到环形⼊⼝节点的节点数（不包含头节点）# 所以 a ⾛了 x 步时，a 到达了环形⼊⼝节点位置# 当 x = n（y + z）- y 时，找到了环形⼊⼝节点位置# 5、开始寻找环⼊⼝ifslow==fast:# 定义两个指针，⼀个指向相遇节点，定义为 b，⼀个指向链表头节点，定义为 a# ⼀个指向相遇节点，定义为 bb=fast# ⼀个指向链表头节点，定义为 aa=head# 让 a 、b 两个指针向前移动，每次移动⼀步，直到相遇位置# 由于有环，必然相遇# 当 b ⾛了 n（y + z） - y 时，b 到达了环形⼊⼝节点位置# 当 a ⾛了 x 步时，a 到达了环形⼊⼝节点位置# a 与 b 相遇whilea!=b:# a 指针每次只会向前移动 1 步a=a.next# b 指针每次只会向前移动 1 步b=b.next# 6、返回 a 和 b 相遇的节点位置就是环形⼊⼝节点位置returna# 没有环，返回 NonereturnNone图解
1通过快慢指针判断是否有环，快指针每次移动两步，慢指针每次移动一步
只要两个指针会相遇，那么这个链表必定有环
2如何寻找环的入口
第一个指针指向头节点
第二个指针指向快慢指针相遇的节点
这两个指针每次只移动一步，这两个指针相遇的节点就是入口
