题目题解# 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 步slowhead# 3、定义⼀个快指针每次只会向前移动 2 步fasthead# 4、如果链表有环那么⽆论怎么移动fast 指向的节点都是有值的whilefast!Noneandfast.next!None:#慢指针每次只会向前移动 1 步slowslow.next# 快指针每次只会向前移动 2 步fastfast.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 ny z# 即 x ny z- y# 我们的⽬的就是去求 x# 定义两个指针⼀个指向相遇节点定义为 b⼀个指向链表头节点定义为 a# b 在环中绕圈圈⾛了 ny z步会回到原处即回到相遇节点处# 由于 y 代表从环形⼊⼝到第⼀次相遇节点的节点数不包含环形⼊⼝节点# 所以 ny z - y 时b 到达了环形⼊⼝节点位置# 由于 x 代表从头节点到环形⼊⼝节点的节点数不包含头节点# 所以 a ⾛了 x 步时a 到达了环形⼊⼝节点位置# 当 x ny z- y 时找到了环形⼊⼝节点位置# 5、开始寻找环⼊⼝ifslowfast:# 定义两个指针⼀个指向相遇节点定义为 b⼀个指向链表头节点定义为 a# ⼀个指向相遇节点定义为 bbfast# ⼀个指向链表头节点定义为 aahead# 让 a 、b 两个指针向前移动每次移动⼀步直到相遇位置# 由于有环必然相遇# 当 b ⾛了 ny z - y 时b 到达了环形⼊⼝节点位置# 当 a ⾛了 x 步时a 到达了环形⼊⼝节点位置# a 与 b 相遇whilea!b:# a 指针每次只会向前移动 1 步aa.next# b 指针每次只会向前移动 1 步bb.next# 6、返回 a 和 b 相遇的节点位置就是环形⼊⼝节点位置returna# 没有环返回 NonereturnNone图解1通过快慢指针判断是否有环快指针每次移动两步慢指针每次移动一步只要两个指针会相遇那么这个链表必定有环2如何寻找环的入口第一个指针指向头节点第二个指针指向快慢指针相遇的节点这两个指针每次只移动一步这两个指针相遇的节点就是入口