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:
        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
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments