# Floyd’s Cycle Detection Algorithm – [Leetcode]142. Linked List Cycle II

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:
return None
# find where they meet
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