Detect Cycle in Linked List (and Find Cycle Start)

Problem Statement

Part A (LC 141): Given the head of a singly linked list, return true if the list contains a cycle, else false.

Part B (LC 142): Return the node where the cycle begins, or null if there is no cycle.

Example 1:

Input: 3 -> 2 -> 0 -> -4
                  ^       |
                  |_______|  (last node points back to node with value 2)
Output (A): true
Output (B): node with value 2

Example 2:

Input: 1 -> 2 -> null
Output (A): false
Output (B): null

Constraints:

• 0 <= list length <= 10^4.
• Node values within int range.

Difficulty: Medium (141 is Easy, 142 is Medium) LC: 141, 142 Round: Technical R1

---

Pattern Recognition

• What is the input structure? Singly linked list that may contain a cycle.
• What are we optimizing? O(1) space solution.
• What pattern does this fit? Floyd's tortoise-and-hare (slow/fast pointers).
• Why does this pattern fit? If a cycle exists, a fast pointer (2 steps) will eventually lap a slow pointer (1 step) — they must meet. If no cycle, fast hits null first.

The cycle-start math is a slick but well-known identity: after they meet, reset one pointer to head, advance both by 1, and they meet again at the cycle entrance.

---

Approach

Brute Force — Hash Set

Walk the list, adding each visited node to a hash set. If you revisit, return true (and that node is the cycle start).

Time: O(n). Space: O(n). Why not optimal: Uses O(n) memory.

Optimal — Floyd's Tortoise and Hare

Key Insight for Detection: Two pointers at different speeds in a cyclic structure must meet. The speed difference is 1, so the hare gains 1 position per step. In a cycle of length L, they meet within L steps once both are inside the cycle.

Detection step-by-step:

1. slow = head, fast = head.
2. While fast and fast.next are non-null:
   • slow = slow.next.
   • fast = fast.next.next.
   • If slow == fast, cycle detected.
3. If loop exits (fast or fast.next is null), no cycle.

Key Insight for Cycle Start: When they meet, let d = distance from head to cycle entry, c = cycle length, m = distance from entry to meeting point. Floyd's math shows d = (c - m) mod c. Practically: reset one pointer to head, step both by 1, they meet at the cycle entry.

Finding start (after detection):

1. Set a = head, b = meeting point.
2. While a != b: advance both by 1.
3. Return a (the cycle entry).

Time: O(n). Space: O(1).

---

Walkthrough (Detection)

Trace on 3 -> 2 -> 0 -> -4 -> (back to 2):

Positions: 0, 1, 2, 3 (with next of 3 → node 1).

step	slow pos	fast pos	equal?
0	0	0	(start)
1	1	2	no
2	2	1 (wrapped: 3 → 1)	no
3	3	3	yes — cycle detected

Walkthrough (Cycle Start)

After detection, slow/fast meet at position 3 (value -4).

Set a = head (position 0, value 3), b = position 3 (value -4).

step	a	b	a == b?
0	pos 0	pos 3	no
1	pos 1	pos 1 (wrap)	yes

Cycle entry is at position 1 (value 2). Answer: node with value 2.

---

Implementation

TypeScript

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(v: number = 0, n: ListNode | null = null) {
        this.val = v;
        this.next = n;
    }
}

function hasCycle(head: ListNode | null): boolean {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

function detectCycle(head: ListNode | null): ListNode | null {
    let slow = head, fast = head;
    while (fast && fast.next) {
        slow = slow!.next;
        fast = fast.next.next;
        if (slow === fast) {
            // Phase 2: find cycle start.
            let a: ListNode | null = head, b = slow;
            while (a !== b) {
                a = a!.next;
                b = b!.next;
            }
            return a;
        }
    }
    return null;
}

C++

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

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

ListNode* detectCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) {
            ListNode *a = head, *b = slow;
            while (a != b) { a = a->next; b = b->next; }
            return a;
        }
    }
    return nullptr;
}

Watch out:

1. Null dereference. Check fast && fast->next before every double-step advance.
2. slow.next == fast.next comparison. Compare node identities (slow == fast), not values.
3. Phase 2 reset direction. After meeting, reset one pointer to head (either one). The other stays at the meeting point. Both advance by 1.

---

Complexity Analysis

	Time	Space
Hash Set	O(n)	O(n)
Floyd's (Optimal)	O(n)	O(1)

Bottleneck: You must traverse at least once to find the cycle (or confirm absence). O(n) is optimal. Floyd's wins by matching that time with constant space.

---

Edge Cases

1. Empty list — return false / null.
2. Single node, no cycle — return false / null. fast.next is null immediately.
3. Single node, self-loop — slow and fast meet at the head; cycle start is the head.
4. Two-node cycle — small; Floyd's handles fine.
5. No cycle, even number of nodes — fast hits null first.
6. No cycle, odd number of nodes — fast.next hits null first.

---

Related Problems

• LC 202 — Happy Number — Same slow/fast pattern on an integer sequence.
• LC 287 — Find the Duplicate Number — Treat the array as an implicit linked list; Floyd's finds the duplicate.
• LC 876 — Middle of the Linked List — Slow/fast to find the middle.
• LC 143 — Reorder List — Combines slow/fast with list reversal and merge.

---

Interview Strategy Notes

Classic Technical R1 problem. 15-20 minutes for both parts. The interviewer will expect you to derive the cycle-start math or at least accept the identity. If you forget the math, state: "Once they meet, the distance from head to entry equals the distance from the meeting point to the entry (modulo cycle length). So reset one pointer to head, step both by 1, they meet at the entry." Then prove it if asked.

---

What is Expected at Each Level

Junior: Solves LC 141 with hash set. With prompting, writes Floyd's. May not know the cycle-start math.

Mid-level: Writes Floyd's directly for both parts. Explains why slow/fast meet. Cites the distance identity for cycle start.

Senior: Proves the distance identity on the whiteboard (2 * slow = fast, so 2(d + m) = d + m + k*c for some k, giving d = k*c - m = (c - m) mod c in the simplest case). Discusses Brent's algorithm as an alternative with better constant factors.