检测环
快慢指针法是一种用于检测链表中是否存在环的有效方法，同时也可以找到环的起点。该方法的原理基于两个指针在链表上同时移动，其中一个移动得更快，而另一个移动得更慢。
-
检测环的存在：
- 使用两个指针，一个称为快指针（fast），一个称为慢指针（slow）。
- 在每一步中，快指针向前移动两步，而慢指针只移动一步。
- 如果链表中不存在环，那么快指针最终会到达链表的尾部，此时可以确定链表中无环。
- 如果链表中存在环，由于快指针的速度比慢指针快，它们最终会相遇。
-
找到环的起点：
- 一旦快慢指针相遇，说明链表中存在环。
- 将其中一个指针（例如慢指针）重新移到链表的头部，保持另一个指针在相遇点。
- 然后，两个指针以相同的速度前进，直到它们再次相遇。这次相遇点就是环的起点。
为什么这个方法有效？
- 如果链表中不存在环，快指针将最终到达链表的尾部，而慢指针也会到达链表的末尾。由于没有环，两者不会相遇。
- 如果链表中存在环，快慢指针最终会在环中的某一点相遇。此时，将其中一个指针移到链表头部，它们再次相遇的地方就是环的起点。
这个方法的时间复杂度为O(N)，其中N是链表的长度。因为快指针每次移动两步，而慢指针每次移动一步，所以快指针最多需要N/2步就能遇到慢指针。在找到相遇点后，重新移动指针的过程最多需要再走N步。
证明
让我们来证明一下，为什么上面两个说法是正确的。
首先，进入环之前的路越长，快慢指针之间的差距就越大，如果这段路足够长，甚至会出现快指针已经在环里面走了好几圈，但是慢指针还没有进入环的情况。
但是不管前面的路有多长，不管慢指针进入环的时候，快指针在环的哪个位置，慢指针进入环以后，快指针总是可以在慢指针走不到一圈的时候追上他，因为慢指针在环内走了一圈的时候，快指针已经走了两圈，一定可以追得上。
下面我们来列算式
进入环之前的路长度为：P
慢节点在环内走过的路为：S
环的总长度为：C
慢指针总共走过的长度：P+S
那么快指针走过的总长度：2(P+S)
快指针在环内走过的长度：P+2S
快慢指针相遇的时候，他们处在同一个位置上：S%C = (P+2S)%C
化简，(P+S)%C = 0，也就是说(P+S) = NC
现在我们在位置S上，再走P的长度就可以回到环的起点。
先来看如何判断是否有环
Leetcode 141. 环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
# 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:
return False
fast = head
slow = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
再来看环的起点在哪里
LCR 022. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head:
return False
fast = head
slow = head
while fast.next and fast.next.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
fast = head
while fast != slow:
fast = fast.next
slow = slow.next
return fast
return False