Free lesson · DSA Mastery - Interview Prep, End to End

Linked List Cycle II

Medium7 min readdsalinked-list

Linked List Cycle II

Linked List Cycle II brings fast-and-slow back to an explicit list and to its full power: not just detecting a cycle, but pinpointing where it begins. This is Floyd's complete two-phase algorithm - detect the meeting point inside the loop (phase 1), then reset one pointer to the head and walk both at equal speed until they meet again, exactly at the cycle's entrance (phase 2). We climb two approaches: a hash set of visited nodes (O(n) space, trivially correct) and the optimal Floyd's algorithm (O(1) space), with the distance proof that makes phase 2 work.

This is the capstone of the module - the elegant result that two pointers and a short piece of modular arithmetic can locate a cycle's start with no extra memory.

The Problem

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.

Example 1:

Input:  head = [3, 2, 0, -4], tail connects to node index 1 (value 2)
Output: node with value 2 (index 1)

Example 2:

Input:  head = [1, 2], tail connects to node index 0 (value 1)
Output: node with value 1 (index 0)

Example 3:

Input:  head = [1], no cycle
Output: null

Constraints:

• The number of nodes is in [0, 10^4].
• -10^5 <= Node.val <= 10^5

Follow-up: Can you solve it using O(1) (i.e. constant) memory?

Approaches Overview

Both find the cycle entrance (or null). The hash set records every node visited and returns the first repeat; Floyd's achieves O(1) space through the two-phase meet-then-walk technique and its distance argument.

Approach 1: Hash Set of Visited Nodes

The Idea

Walk the list, inserting each node (by reference) into a hash set. The first node you encounter that's already in the set is the cycle's entrance. If you reach null, there's no cycle. Simple and obviously correct, but O(n) space.

Logic Flowchart

graph TD
    A["seen = {}; cur = head"] --> B{"cur != null?"}
    B -->|No| C["Return null (no cycle)"]
    B -->|Yes| D{"cur in seen?"}
    D -->|Yes| E["Return cur (cycle entrance)"]
    D -->|No| F["seen.add(cur); cur = cur.next"]
    F --> B

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9

This flowchart shows the hash-set approach. We walk the list adding each node to a set; the first node already in the set is the cycle's entrance. Reaching null means there is no cycle.

Code

public static ListNode detectCycleSet(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    for (ListNode cur = head; cur != null; cur = cur.next) {
        if (!seen.add(cur)) return cur;   // add returns false if already present
    }
    return null;
}

This Java code walks the list adding each node to a set by reference; the first node that fails to add - because it is already present - is the cycle's entrance. Reaching null returns null.

Complexity

Time: O(n). Space: O(n) for the set.

Approach 2: Floyd's Two-Phase Algorithm - Optimal

The Idea

Phase 1 - detect. Run slow (+1) and fast (+2). If fast reaches null, there's no cycle - return null. Otherwise they meet at some node inside the loop.

Phase 2 - locate. Reset one pointer to the head, keep the other at the meeting point, and advance both one step at a time. They meet exactly at the cycle's entrance.

Why phase 2 works (distance proof). Let a be the distance from head to the cycle entrance, b the distance from the entrance to the meeting point (along the loop), and c the loop length. When they meet, slow has traveled a + b and fast has traveled a + b + k·c for some integer k (it looped k times). Since fast moves twice as fast, 2(a + b) = a + b + k·c, so a + b = k·c, giving a = k·c − b. That means walking a steps from the head lands at the same node as walking a steps from the meeting point (which advances k·c − b around the loop back to the entrance). Hence the equal-speed walk meets at the entrance.

Logic Flowchart

graph TD
    A["Phase 1: slow+1, fast+2"] --> B{"fast or fast.next null?"}
    B -->|Yes| C["Return null (no cycle)"]
    B -->|No| D{"slow == fast?"}
    D -->|No| A
    D -->|Yes| E["meeting point found"]
    E --> F["Phase 2: ptr = head"]
    F --> G{"ptr == slow?"}
    G -->|No| H["ptr = ptr.next; slow = slow.next"]
    H --> G
    G -->|Yes| I["Return ptr (cycle entrance)"]

    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style C fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style D fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style E fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9

This flowchart shows Floyd's two phases. In phase one, slow and fast move at speeds one and two; if fast reaches null there is no cycle, otherwise they meet inside the loop. In phase two, one pointer resets to the head and both advance one step at a time, meeting exactly at the cycle's entrance.

Code

public static ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;

    // Phase 1: detect a meeting point
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {                 // cycle detected
            // Phase 2: find the entrance
            ListNode ptr = head;
            while (ptr != slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;                     // cycle entrance
        }
    }
    return null;                            // fast hit null: no cycle
}

// Usage:
// detectCycle([3,2,0,-4] with tail->index 1) -> node value 2
// detectCycle([1] no cycle)                  -> null

This Java code runs phase one with slow and fast pointers; if they meet, a cycle exists. It then resets a pointer to the head and advances it and slow one step at a time until they meet at the cycle's entrance. If fast reaches null, it returns null for no cycle.

Step-by-Step Walkthrough

A frame-by-frame trace on [3, 2, 0, -4] with tail linking back to index 1 (value 2):

graph LR
    F0["Phase 1<br/>slow & fast advance<br/>meet inside loop"]
    F1["meeting point<br/>somewhere in 2,0,-4"]
    F2["Phase 2: ptr=head(3)<br/>slow at meeting point"]
    F3["both +1 step<br/>until equal"]
    F4["meet at node 2<br/>= cycle entrance"]
    F0 --> F1 --> F2 --> F3 --> F4

    style F0 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F1 fill:#dc2626,stroke:#ef4444,color:#f1f5f9
    style F2 fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F3 fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style F4 fill:#16a34a,stroke:#10b981,color:#f1f5f9

This walkthrough finds the cycle entrance in three, two, zero, minus four, whose tail links back to two. Phase one advances slow and fast until they meet inside the loop. Phase two resets a pointer to the head and walks both one step at a time; they meet at node two, the cycle's entrance.

Result: the node with value 2 (the cycle entrance).

Complexity

Time: O(n) - phase 1 is at most O(n); phase 2 walks a < n steps. Space: O(1).

Complexity Comparison

Both O(n) time. Floyd's is the expected answer for its O(1) space and for demonstrating the meet-then-walk insight with its distance proof. The hash set is a fine fallback when space isn't constrained and is easier to state under pressure.

Variations & Follow-ups

How does this differ from Linked List Cycle I (detect-only)?

Cycle I only asks whether a cycle exists - phase 1 alone (meeting = cycle, null = none). Cycle II adds phase 2 to find where the cycle starts. The detection step is shared; the entrance-location is the new part.

Why reset to the head and walk at equal speed?

The distance identity a = k·c − b proves that a steps from the head and a steps from the meeting point both arrive at the entrance. Equal speed preserves that a-step alignment, so they coincide precisely at the start of the loop.

Why must the speeds be 1 and 2 specifically?

Speed 2 makes fast gain exactly one step on slow per move, guaranteeing they meet (the gap shrinks by 1 each step), and it yields the clean 2·slow = fast relation that the distance proof relies on. Larger speeds complicate the meeting guarantee and the arithmetic.

What about edge cases?

• No cycle: fast reaches null; return null (Example 3).
• Cycle includes the head (a = 0): Phase 2 starts with ptr == slow immediately at the head (Example 2).
• Whole list is one big loop: Entrance is the head.
• Single node, self-loop: Detected; entrance is that node.

Common Interview Pitfalls

• Returning the meeting point instead of the entrance. The meeting point is inside the loop, not its start - phase 2 is required.
• Skipping the null guard in phase 1. fast != null && fast.next != null prevents a null dereference on acyclic lists.
• Advancing both at speed 2 in phase 2. Phase 2 must use equal speed (both +1).
• Modifying the list. The problem forbids it; Floyd's doesn't need to.

Why This Problem Matters

Linked List Cycle II is the module's capstone: it shows that two pointers plus a short modular-arithmetic argument can not only detect a cycle but locate its entrance in O(1) space - a result that feels almost magical until the distance proof makes it inevitable. The meet-then-reset-and-walk pattern, and the discipline of proving why a pointer trick lands where it does, is exactly the rigor that distinguishes deep understanding from memorized templates.

This completes Section 15 - Linked List. Across 28 topics you've built the three pillars of linked-list problem-solving: basic pointer surgery (dummy heads, predecessor tracking, two-pointer gaps, two-builder weaves, precise splicing), in-place reversal (the three-pointer dance scaled from whole lists to sublists to k-groups), and fast-and-slow pointers (middle-finding, cycle detection, entrance-location, and the leap to implicit sequences). These patterns recur far beyond linked lists.

The next section, Section 16 - Stacks, is the largest in the course at 37 topics. Stacks formalize the last-in-first-out discipline that underlies expression evaluation, monotonic-stack range queries, backtracking, and the call stack itself - a foundational structure whose patterns will reshape how you approach an enormous class of problems.

Back to DSA Mastery - Interview Prep, End to End