Linked List Cycle II: Finding the Cycle Entry Point

"Linked List Cycle II" is a Medium-level staple in Amazon, Meta, Nvidia loops, and it is a textbook fit for the Fast and Slow Pointers pattern — one of the nine patterns that cover the bulk of what FAANG coding interviews actually test. Part 2 of 11 in the Fast and Slow Pointers arc.

The Problem

Given the head of a linked list, return the node where a cycle begins, or None if there is no cycle. Same O(1)-space expectation as cycle detection, but now you must know why Floyd's algorithm works, not just that it does.

Input:  3 -> 2 -> 0 -> -4 -> (back to 2)
Output: the node holding 2

Recognizing the Fast and Slow Pointers Pattern

Fast and slow pointers (Floyd's tortoise and hare) walk the same structure at different speeds. If there is a cycle they must meet; if there is not, the fast pointer finds the end in half the iterations — which also locates midpoints without knowing the length. It is the default tool for linked lists and for any sequence defined by repeatedly applying a function, all in O(1) space.

This is the mathematical half of the tortoise-and-hare pattern. The meeting point is not the entry — but it is positioned so that a second, equal-speed walk from the head and from the meeting point collide exactly at the entry.

The Approach

Phase one: standard fast and slow until they meet (or no cycle). Phase two: reset one pointer to the head; advance both one step at a time; they meet at the cycle entry.

The why, compactly: with head-to-entry distance a, entry-to-meeting distance b, and cycle length c, the meeting satisfies 2(a + b) = a + b + kc, so a = kc − b. Walking a steps from the head therefore lands exactly at the entry, because kc − b steps from the meeting point is the entry too. Write those three variables on the whiteboard — it is expected.

Python Solution

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


def detect_cycle(head: ListNode | None) -> ListNode | None:
    """Node where the cycle begins, or None. O(1) space."""
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            probe = head                 # phase two: equal speeds
            while probe is not slow:
                probe = probe.next
                slow = slow.next
            return probe
    return None

Complexity

• Time: O(n) — two linear phases
• Space: O(1) — three pointers total across both phases

Interview Tips and Follow-Ups

• Derive a = kc − b live at least once before your onsite; it is the single most-asked proof in linked list interviews.
• The hash-set answer (first revisited node is the entry) is a fine warm-up — state its O(n) space cost as you discard it.
• Same two-phase machinery solves Find the Duplicate Number on arrays — later in this arc — and saying so early earns pattern points.

That wraps part 2 of the Fast and Slow Pointers arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.