Linked List Cycle II — Floyd's Algorithm to Find Where the Cycle Starts

Problem Statement#

Given the head of 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. Do not modify the linked list.

Constraints:

• The number of nodes in the list is in the range [0, 10^4]
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked list

Example 1:

Input:  head = [3,2,0,-4], pos = 1
Output: Pointer to node with value 2
Explanation: Tail connects to index 1 (value 2) — that's the cycle entry.

Example 2:

Input:  head = [1,2], pos = 0
Output: Pointer to node with value 1
Explanation: Tail connects to index 0 — the head is the cycle entry.

Example 3:

Input:  head = [1], pos = -1
Output: null
Explanation: No cycle.

Why This Problem Matters#

Linked List Cycle II (LeetCode 142) is the harder follow-up to LC 141 (detect if a cycle exists). Here, you need to find the exact node where the cycle begins. Amazon, Microsoft, and Google ask this problem specifically because it requires you to understand the mathematical proof behind Floyd's algorithm — not just apply a memorized template.

The problem is also the foundation for Find the Duplicate Number (LC 287), where an array is treated as an implicit linked list with a cycle. Understanding Cycle II deeply means you can solve that problem too.

In real-world systems, finding where a cycle begins appears in debugging circular references in garbage collection (finding the root of a circular reference chain), deadlock detection in operating systems (finding the initial resource that started the circular wait), and detecting infinite loops in state machine execution.

The mathematical elegance of this algorithm — that a simple pointer reset leads both pointers to meet at the cycle entry — is the kind of result that rewards careful thinking over memorization.

The Core Insight#

Phase 1: Detect the cycle — use Floyd's fast/slow pointers. If they meet, a cycle exists.

Phase 2: Find the cycle entry — reset one pointer to head. Move both pointers one step at a time. They meet at the cycle entry.

Why this works (the math):

Let:

• d = distance from head to cycle entry
• c = length of the cycle
• m = distance from cycle entry to the meeting point (measured within the cycle)

When slow and fast first meet:

• slow has traveled: d + m
• fast has traveled: d + m + k*c (k full extra cycles)

Since fast moves 2x: d + m + k*c = 2(d + m)

Simplifying: k*c = d + m, so d = k*c - m

Now reset one pointer to head (distance d from entry) and keep the other at the meeting point (distance k*c - m from entry, which is equivalent to c - m within the cycle, i.e., d more steps to reach the entry).

Both pointers travel exactly d more steps and arrive at the cycle entry simultaneously.

Visual Dry Run#

Input: 3 -> 2 -> 0 -> -4, where -4.next = 2 (cycle starts at index 1)

Nodes: 3(idx 0) -> 2(idx 1) -> 0(idx 2) -> -4(idx 3) -> back to 2

d = 1 (steps from head to cycle entry at node 2) c = 3 (cycle: 2 -> 0 -> -4 -> back to 2)

Phase 1: Detect meeting point

Meeting at -4. m = 2 (steps from entry 2 to -4: 2->0->-4 is 2 steps).

Verify: d = kc - m. With k=1: 13 - 2 = 1 = d. Correct.

Phase 2: Find entry

Reset ptr = head = 3. Keep slow = -4.

Both at node 2 — cycle entry found!

Solution (Optimal)#

Python#

def detectCycle(head):
    slow = fast = head
 
    # Phase 1: Detect cycle with fast/slow pointers
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            # Cycle detected — move to Phase 2
            ptr = head
            # Phase 2: Find cycle entry
            while ptr is not slow:
                ptr = ptr.next
                slow = slow.next
            return ptr  # both meet at the cycle entry
 
    return None  # no cycle

Time complexity: O(n) — Phase 1 takes at most n steps; Phase 2 takes at most d steps (d <= n).

Space complexity: O(1) — three pointer variables.

JavaScript#

var detectCycle = function(head) {
    let slow = head, fast = head;
 
    // Phase 1: Detect
    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) {
            // Phase 2: Find entry
            let ptr = head;
            while (ptr !== slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
 
    return null;
};

Complexity:

Hash set alternative (O(n) space):

def detectCycle(head):
    seen = set()
    while head:
        if id(head) in seen:
            return head
        seen.add(id(head))
        head = head.next
    return None

Common Mistakes#

1. Returning the meeting node instead of the cycle entry. The meeting node is NOT the cycle entry in general. After Phase 1, you must do Phase 2 (reset one pointer to head) to find the entry. Many candidates skip Phase 2 and return the Phase 1 meeting node.

2. Moving both pointers at once in Phase 2. In Phase 2, both ptr and slow move one step at a time. Using fast speed for either pointer in Phase 2 breaks the math.

3. Using value equality instead of reference equality. ptr == slow compares values; ptr is slow (Python) or ptr === slow (JavaScript) compares references. Two different nodes can have the same value. Always use reference equality.

4. Not checking for no-cycle before entering Phase 2. If there's no cycle, Phase 1's while loop terminates without the if slow is fast branch being hit. Phase 2 is only entered inside that branch. Ensure Phase 2 code is inside the cycle-detection conditional.

5. Modifying the list. The problem says "Do not modify the linked list." The Floyd's algorithm approach only reads — it's read-only. The hash set approach is also read-only. Do not break cycles or modify next pointers.

Interview Tips#

1. Explain both phases clearly: "Phase 1 uses fast/slow pointers to detect the meeting point. Phase 2 resets one pointer to head and moves both at speed 1 until they meet at the cycle entry."

2. Explain the math at a high level: "The key insight is that d = k*c - m, where d is head-to-entry distance, c is cycle length, m is meeting-to-entry distance. After resetting, both pointers travel exactly d steps to the entry."

3. Verify with a concrete example: Walk through the 3 -> 2 -> 0 -> -4 example showing Phase 1 meeting at -4 and Phase 2 finding 2.

4. Mention the hash set approach first: "The simplest approach is a hash set — O(n) space. Floyd's algorithm gets O(1) space."

5. Bridge to LC 287: "This pattern directly solves Find the Duplicate Number — treat the array as an implicit linked list where index i points to nums[i]. The duplicate creates a cycle, and the entry is the duplicate."

Follow-up Questions#

Q: How does this relate to Find the Duplicate Number (LC 287)? In LC 287, the array nums of length n+1 with values in [1,n] is treated as a linked list: index i links to index nums[i]. Since one value is duplicated, two indices point to the same next index — creating a cycle. Floyd's Cycle II finds the cycle entry, which is the duplicate value.

Q: What if there are multiple cycles? A standard singly linked list cannot have multiple independent cycles (each node has one next pointer). The list can have at most one cycle.

Q: Can the cycle entry be the head? Yes — if the tail points back to the head. In Phase 2, ptr starts at head and slow is at the meeting point. If the entry is the head, ptr == slow is true on the first comparison (both are at head), returning head immediately.

Q: What is the meeting point in terms of cycle distance? The meeting point is c - (d mod c) steps after the cycle entry (equivalently d mod c steps before the entry when traversing the cycle backwards). This is where the fast pointer catches the slow pointer after lapping it.

Q: Is there a simpler way to prove Phase 2 works? Yes: after meeting, the slow pointer has c - m more steps to complete the cycle back to the entry. The head pointer has d steps to reach the entry. We showed d = k*c - m. For k=1, d = c - m. Both reach the entry in the same number of steps.

Key Takeaways#

• Floyd's Cycle II has two phases: Phase 1 detects the meeting point; Phase 2 finds the cycle entry by resetting one pointer to head.
• Mathematical proof: d = k*c - m ensures both pointers meet at the cycle entry after Phase 2.
• Use reference equality (is in Python, === in JavaScript) — not value equality.
• Phase 2 moves both pointers at speed 1 — do not use fast speed.
• The hash set approach (O(n) space) is simpler; Floyd's is O(1) space.
• This pattern directly solves Find the Duplicate Number (LC 287) by treating the array as an implicit linked list.