142 - Linked List Cycle II

Difficulty: Medium | Pattern: Floyd's Cycle Detection (Two Pointers) | Company tags: Amazon, Microsoft, Uber, Bloomberg

Problem Statement

Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: Reference to node with value 2
Explanation: Cycle starts at the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: Reference to node with value 1

Approach: Floyd's Tortoise and Hare — O(n), O(1)

Algorithm (two phases):

Phase 1: Detect cycle

• slow moves 1 step at a time; fast moves 2 steps.
• If they meet, there is a cycle.

Phase 2: Find entry point

• Reset slow to head. Keep fast at meeting point.
• Move both 1 step at a time. Where they meet = cycle entry.

def detectCycle(head):
    slow = fast = head
    
    # Phase 1: detect cycle
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            break
    else:
        return None  # no cycle
    
    # Phase 2: find entry node
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

Algorithm Flow

Mathematical Proof

Let:

• F = distance from head to cycle entry
• C = cycle length
• h = distance from cycle entry to meeting point

At meeting point: slow traveled F + h, fast traveled F + h + n×C (n full cycles).

Since fast = 2 × slow: 2(F + h) = F + h + n×C → F = n×C - h

After phase 1, resetting slow to head: slow travels F steps, fast travels n×C - h steps from meeting point = exactly the cycle entry. They meet at the entry node.

Dry Run

List: 3→2→0→-4→(back to 2), cycle starts at node 2 (index 1)

Step	slow	fast
init	3	3
1	2	0
2	0	2 (via -4)
3	-4	-4 (via 0)
4	2	2
meet!	2	2

Phase 2: slow=head(3), fast=2

• step 1: slow=2, fast=0 → not equal
• step 2: slow=0, fast=-4 → not equal

Wait, let me redo: F=1, h=3, C=4. Phase 2: slow starts at 3, fast at -4. Both move 1 step: slow→2, fast→2. They meet at node 2 ✓.

Edge Cases

• No cycle → return None (phase 1 fast reaches end)
• Cycle at head → F=0, entry = head
• Single node pointing to itself → detected

Complexity

• Time: O(n)
• Space: O(1) — no extra data structures

Compare with LC 141: LC 141 only detects existence of a cycle (returns bool). LC 142 finds the actual entry node.

Key Terms

Term	Definition
Floyd's cycle detection	Two-pointer technique (tortoise and hare) that detects a cycle in O(1) space by moving pointers at different speeds.
Fast/slow pointers	slow advances 1 node per step, fast advances 2; if a cycle exists they eventually occupy the same node.
Cycle entry point	The node where the tail of the list re-connects into an earlier node, creating the loop.
Meeting point	The node at which slow and fast first collide inside the cycle; used to derive the entry point in phase 2.
Distance invariant	The relation F = n×C - h linking head-to-entry distance, cycle length, and meeting-point offset.

FAQ

Q: Can this be solved without extra space? Yes — that's the point of Floyd's algorithm. A hash-set approach also works (store visited nodes, return the first repeat) but uses O(n) space; the two-pointer approach is the O(1)-space expected solution.

Q: What if there is no cycle? Phase 1's while fast and fast.next loop terminates naturally when fast hits None, so the else clause on the while fires and the function returns None without entering phase 2.

Q: Why does resetting slow to head and moving both pointers 1 step at a time find the entry node? The math works out because at the meeting point slow has traveled F + h and fast has traveled 2(F + h), which also equals F + h + n×C. Solving gives F = n×C - h, meaning walking F steps from head lands on the same node as walking n×C - h steps from the meeting point — both reach the entry.

Q: How would this change if you needed the cycle length instead of the entry node? Once slow and fast meet in phase 1, keep one pointer fixed and advance the other until it returns to the same node, counting steps — that count is the cycle length C.

Q: What if the list could have multiple disjoint cycles? Not possible in a singly linked list — each node has exactly one next pointer, so once you enter a cycle you can never branch into a second one; the structure is always a "rho" (ρ) shape with a single loop.

Quick Revision

• Pattern: Floyd's tortoise and hare, two phases.
• Phase 1: slow moves 1 step, fast moves 2 steps; they meet inside the cycle if one exists.
• If fast or fast.next becomes None, there is no cycle — return None.
• Phase 2: reset slow to head, keep fast at the meeting point, move both 1 step at a time.
• The node where they meet in phase 2 is the cycle's entry point.
• Key identity: F = n×C - h (F = head-to-entry distance, C = cycle length, h = meeting-point offset from entry).
• Time complexity O(n), space complexity O(1) — no hash set needed.
• Contrast with LC 141 (Linked List Cycle): that problem only needs a boolean, so it stops after phase 1.
• Edge cases: no cycle, cycle starting at head (F = 0), single self-looping node.

Related Problems

• 876-MiddleOfTheLinkedList.md — same fast/slow pointer mechanics, simpler goal (find the middle node).
• 19-RemoveNthNodeFromEndOfList.md — two-pointer technique on a linked list with an offset gap.
• LeetCode 141 (Linked List Cycle) — the boolean-only variant of this problem; solved by stopping after Floyd's phase 1 (no dedicated file in this directory).