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
poswhich represents the position (0-indexed) in the linked list where tail connects to. If
-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