Overview

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-pointer algorithm to detect the cycle and locate 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. If there’s a cycle in the sequence, they will meet finally at some point. OR if there's no such a cycle, they will both reach the end.

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

hare = tortoise = head

while hare and hare.next:
    # hare moves 2 steps while tortoise moves 1 step
    hare = hare.next.next
    tortoise = tortoise.next
    if hare == tortoise:
        return True

return False

Where does the cycle begin?

Firstly, we put the hare and the tortoise at the start. Similarly, the hare moves 2 steps at a time while the tortoise moves 1 step. Assuming they meet after i iterations, the length of the non-cyclic part is m, perimeter 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 representing the number of loops that tortoise traveled, and i is also the distance that the tortoise moved.
• 2*i=m+bn+k. b is another non-negative integer representing the number of loops that hare traveled, and 2∗i is the distance that the hare moved.

After some simply math, we get: i = (b - a) * n.

Now we put the hare back to the beginning and both hare and tortoise move 1 step at a time. The place where they meet is the start of the cycle. This is because when the hare travelled another 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.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.

Notice that you should 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 reaches the end first, then there's no cycle
        if hare != tortoise:
            return None
        # or, put the hare back to the beginning
        hare = head
        while tortoise != hare:
            hare = hare.next
            tortoise = tortoise.next
        return hare