2Brute2Best
🔥0
01

Cycle detection (Linked List — Fast & Slow Sub-pattern)

Slow moves 1, fast moves 2. If fast reaches null, there's no cycle. If they meet, there is one. To find where it starts, reset one pointer to the head and move both 1 step until they meet again.

Signals in the problem statement
  • ›

    "does the linked list have a cycle?"

  • ›

    "return the node where the cycle begins"

  • ›

    "length of the loop"

  • ›

    a number or index keeps being replaced by a rule (n → digit squares, i → nums[i]) — does it repeat forever?

What makes it different

Linked List Cycle only asks yes/no: stop at the first meeting. Happy Number has no nodes — the "next node" is the sum of squared digits — but it's the same Floyd loop on numbers. Here the sequence never "ends" (1 → 1 forever), so the test is whether fast reaches 1 or the two meet somewhere else. Length of Loop meets, then walks once around from the meeting node counting nodes. Linked List Cycle II adds phase 2 to find the entry. Find the Duplicate Number is Cycle II on the invisible list i → nums[i]. Circular Array Loop runs Floyd from each index, but a valid loop must keep one direction and be longer than 1 node; mark dead paths as visited so the total stays O(N).

Questions

ordered from “learn the idea” to “recognise it without help”
  1. 1
    Linked List Cycle
    Basic Anchor·LeetCode #141
    Easy
  2. 2
    Happy Number
    Basic Reinforcement·LeetCode #202
    Easy
  3. 3
    Find Length of Loop
    Slight Variation·GeeksforGeeks
    Easy
  4. 4
    Linked List Cycle II
    Medium·LeetCode #142
    Medium
  5. 5
    Find the Duplicate Number (cycle view)
    Pattern Transfer·LeetCode #287
    Medium
  6. 6
    Circular Array Loop
    Pattern Transfer·LeetCode #457
    Medium

Template

floyd-template.cpp
// Floyd's cycle detection: slow moves 1, fast moves 2.
// Returns the node where the cycle starts, or nullptr if there is no cycle.
ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {               // check fast BEFORE fast->next
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {                    // phase 1: they met inside the loop
            ListNode* p = head;                // phase 2: one from head, one from the meeting node
            while (p != slow) { p = p->next; slow = slow->next; }
            return p;                          // both 1 step at a time → they meet at the entry
        }
    }
    return nullptr;                            // fast fell off the end → no cycle
}
Remember this · Linked List — Fast & Slow
Trigger
Cycle detection, middle of list, "n-th from end", two lists meeting, repeating sequences.
Think
If one pointer moves faster or starts earlier, where will they meet?
Key question
What speed or gap makes the meeting point tell me the answer?
Linked List — Fast & Slow overviewMiddle / split