Home/Questions/Q 3533
Next
In Process

RTSALL Latest Articles

aarav0
Asked: 2026-09-11T09:53:18-05:00 In: ,

Floyd’s Tortoise and Hare: Mathematical proof of why meeting point resolves cycle origin

In Floyd’s Cycle-Finding Algorithm (Tortoise and Hare), slow moves by 1 step and fast moves by 2 steps. If a cycle exists, they are guaranteed to meet.

Then comes part 2: to find the start of the cycle (the loop origin), you place one pointer back at the head, keep the other pointer at the meeting_point, and advance both at speed 1. When they meet again, that node is the cycle start. What is the formal modular arithmetic proof that guarantees this?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhay Tiwari
    Begginer

    Floyd’s cycle algorithm is pure mathematical poetry. Let’s write out the distances with simple algebra so the proof is crystal clear.

    1. Defining the Variables

    Let’s map out the linked list into three distinct segments:

    • L: Distance from the head to the cycle entrance.
    • C: Total length (circumference) of the cycle.
    • x: Distance from the cycle entrance to the meeting point inside the cycle.

    2. Distance Traveled by Each Pointer

    When the Tortoise (slow) and Hare (fast) meet:

    • Slow moved: Dist_slow = L + x
    • Fast moved: Dist_fast = L + n * C + x (where n is how many full laps fast ran around the cycle).

    Because the fast pointer moves at twice the speed of slow:

    Dist_fast = 2 * Dist_slow
L + n * C + x = 2 * (L + x)
L + n * C + x = 2L + 2x

    Now subtract L + x from both sides:

    n * C = L + x
L = n * C - x
L = (n - 1) * C + (C - x)

    3. What does L = (n – 1) * C + (C – x) mean?

    Look carefully at that equation:

    • L is the distance from head to the cycle entrance.
    • (C - x) is the distance from the meeting point to the cycle entrance!
    • (n - 1) * C is just zero or more full loops around the cycle!

    Conclusion: If you place Pointer 1 at head (which must travel distance L) and Pointer 2 at meeting_point (which travels distance (C - x) plus some optional full laps), both pointers will meet at the EXACT same node: the cycle entrance!

    Clean Python 3.12 Implementation

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

def detect_cycle_entry(head: ListNode | None) -> ListNode | None:
    """Finds the node where cycle begins in O(N) time and O(1) space."""
    if not head or not head.next:
        return None

    slow = head
    fast = head

    # Phase 1: Determine if a cycle exists
    has_cycle = False
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break

    if not has_cycle:
        return None

    # Phase 2: Find cycle entrance
    ptr1 = head
    ptr2 = slow
    while ptr1 != ptr2:
        ptr1 = ptr1.next
        ptr2 = ptr2.next

    return ptr1

    Complexity Breakdown

    • Time Complexity: O(N). Phase 1 takes at most $2N$ steps. Phase 2 takes at most $N$ steps.
    • Space Complexity: O(1). No hash set or memory allocation.
    • 0
  2. Abhishek
    Begginer

    Here is the production C++20 implementation of Floyd’s Tortoise and Hare Cycle Origin algorithm with pointer safety checks.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* detectCycleEntry(ListNode* head) {
    if (!head || !head->next) return nullptr;

    ListNode* slow = head;
    ListNode* fast = head;
    bool has_cycle = false;

    // Phase 1: Detect meeting point
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            has_cycle = true;
            break;
        }
    }

    if (!has_cycle) return nullptr;

    // Phase 2: Find cycle entrance
    ListNode* ptr1 = head;
    ListNode* ptr2 = slow;
    while (ptr1 != ptr2) {
        ptr1 = ptr1->next;
        ptr2 = ptr2->next;
    }
    return ptr1;
}

int main() {
    ListNode* n1 = new ListNode(3);
    ListNode* n2 = new ListNode(2);
    ListNode* n3 = new ListNode(0);
    ListNode* n4 = new ListNode(-4);

    n1->next = n2;
    n2->next = n3;
    n3->next = n4;
    n4->next = n2; // Loop back to n2

    ListNode* entry = detectCycleEntry(n1);
    if (entry) {
        std::cout << "Cycle detected at node with value: " << entry->val << "n";
    }
    return 0;
}

    Complexity: O(N) time and strictly O(1) auxiliary space.

    • 0