在刷LeetCode时，我们经常用到快慢指针。那么它背后有怎样的数学原理呢，今天就给大家献丑了。
龟兔赛跑简述
Floyd判圈算法（Floyd Cycle Detection Algorithm），又称龟兔赛跑算法（Tortoise and Hare Algorithm），是一个可以在有限状态机、迭代函数或者链表上判断是否存在环，以及判断环的起点与长度的算法。
原理
如图，A为出发点，B为环的入口点。快慢指针都从A点出发，其中快指针的速度是慢指针的2倍。
判断是否有环
如果存在环，快慢指针必定相遇；否则，慢指针走到结尾还未相遇则不存在环。
求环的长度
假设两者在C点第一次相遇。再让两指针继续前进，下次相遇时快指针比慢指针多走了一圈。
求环的起点
假设AB的长度为m，BC的长度为n，环的周长为p。在相遇时，我们假设慢指针移动的距离为s，有： s = m + n + ap 而快指针的移动距离为： 2s = m + n + bp
两式相减有： s = (b - a)p 也就是说慢指针走过的距离为环长的整数倍。
在第一次相遇后，让慢指针从C点出发，另一个指针从A点出发，都以慢指针的速度移动。则它们必定在B点相遇。因为当从A点出发的指针走过m的距离到达B点时，慢指针已经走过了s+m的距离（也是从A点出发）。其中S为环长的整数倍，那么慢指针也必定再B点，所以相遇点为环的入口点B点。
应用
LeetCode 142题
这是求环形链表的入口，代码如下：
# 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 None
slow, fast = head, head.next
while slow != fast:
slow = slow.next if slow else None
fast = fast.next.next if fast and fast.next else None
if not slow:
return None
entry = head
slow = slow.next
while entry != slow:
entry = entry.next
slow = slow.next
return entry
LeetCode 287
这是数组形式的寻找起点：
class Solution:
def findDuplicate(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) <= 0:
return -1
slow = nums[0]
fast = nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
entry = nums[0]
slow = nums[slow]
while slow != entry:
entry = nums[entry]
slow = nums[slow]
return entry