Floyd's Tortoise and Hare Algorithm

Floyd's Tortoise and Hare algorithm is an elegant cycle detection technique that finds whether a cycle exists in a linked list (or any cyclic structure) and can locate where the cycle begins. The genius of the algorithm lies in using two pointers moving at different speeds.

Why It Works Mathematically

If a cycle exists, the pointers will inevitably collide. Let's say the list has:

• a = distance from head to cycle start
• b = distance from cycle start to meeting point (where slow and fast meet)
• c = total cycle length

When the tortoise enters the cycle, the hare is already somewhere inside it. Once both are in the cycle, the hare is moving faster, so it closes the gap between them by one position each step. Since the gap is at most c positions, they must eventually meet within c steps.

When Slow and Fast Meet:

Slow pointer travels:a + b steps (to reach the meeting point)

Fast pointer travels:a + b + k*c steps (for some integer k ≥ 1, meaning it completed k extra cycles)

Since fast moves at 2x speed: a + b + k*c = 2(a + b)

so k*c = a + b,

From k*c = a + b, we can rearrange: a = k*c - b.

According to the defination of c and b:

• c - b = distance from meeting point forward around the cycle back to cycle start

so after they meet, put one pointer to the head and move both pointers with 1x speed at the same time, they will meet again at the start position of the cycle.

Solution:

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var detectCycle = function(head) {
    let fast = head;
    let slow = head;
    while(fast && fast.next){
        fast = fast.next.next;
        slow = slow.next;
        if(fast === slow) {
            // is a cycle, let's check the start point
            let slow = head;
            while(slow!==fast){
                fast = fast.next
                slow = slow.next
            }
            return slow;
        }
    }
    return null;
};

Question 1: what if the fast pointer moves 3x faster than slow pointer, will they meet?

If there is a cycle and fast > slow, they will always meet eventually — even with 3× or 4× speed. Meeting is guaranteed.

But it is not stable,

if 2x, then faster pointer moves 1x relatively, it means it will traversal every node in the cycle, but if faster pointer moves 3x or even faster, it may skip over the slow pointer in one move.

Question 2: Why we can get a = c - b from a = k*c - b

a = k*c - b*

a = c - b + (k-1)*c

This means pointer in the cycle takes extra (k-1)c loops when the other pointer arrived and meet each other. The whole loop don’t change the destination.

If you go forward a steps from the head, you land at the same node as going backward b steps from the meeting point, looping around the cycle as necessary.