The cycle detection problem is to find the cycle in a sequence, and Floyd’s cycle detection algorithm, aka Tortoise and Hare algorithm, is a two pointers algorithm to detect the cycle and the start of the cycle as well.

## Detect the cycle

Assuming there are a hare and a tortoise at the beginning and the hare moves 2 steps at one time while the tortoise moves 1 step at a time. If there’s a loop in the sequence, they will meet finally at some point.

```
hare = tortoise = head
while hare and hare.next:
hare = hare.next.next
tortoise = tortoise.next
if hare == tortoise:
return True
return False
```

## Where does the cycle begin?

Firstly, we put a hare that moves 2 steps at a time and a tortoise which moves 1 step at a time at the start. Assuming they meet after i iterations, the length of the non-cyclic part is m, and length of the cycle is n, and the distance between the beginning of the cycle to the place they meet is k, we have:

- i=m+an+k. a is a non-negative integer and i is the distance that the tortoise moved.
- 2*i=m+bn+k. b is another non-negative integer and 2*i is the distance that the hare moved.

So that we have i=(b-a)n.

Now we put the hare back to the beginning and both the hare and the tortoise move 1 step at a time. The place where they meet is the start of the cycle because when the hare travelled m, the tortoise is at the i+m=(b-a)n+m.

Take Leetcode 142. Linked List Cycle II as an example:

Given a linked list, return the node where the cycle begins. If there is no cycle, return`null`

. To represent a cycle in the given linked list, we use an integer`pos`

which represents the position (0-indexed) in the linked list where tail connects to. If`pos`

is`-1`

, then there is no cycle in the linked list.Note:Do not modify the linked list.

```
class Solution:
def detectCycle(self, head: ListNode) -> ListNode:
if not head or not head.next:
return None
# find where they meet
hare = tortoise = head
while hare and hare.next:
hare = hare.next.next
tortoise = tortoise.next
if hare == tortoise:
break
if hare != tortoise:
return None
# put the hare back to the beginning
hare = head
while tortoise != hare:
hare = hare.next
tortoise = tortoise.next
return hare
```