Linked List Cycle II

MediumLinked List · Fast & Slow Pointers🧩 Fast & Slow Pointers LeetCode #142 ↗Updated Oct 30, 2026

Problem

You get the head of a singly linked list whose tail may point back to an earlier node, forming a cycle. Return the node where the cycle begins (the first node reached twice when walking from head), or null if the list ends. Do not modify the list.

Input[3,2,0,-4], tail → idx 1Outputnode at index 1 (val 2)

Input[1,2], tail → idx 0Outputnode at index 0 (val 1)

Input[1], no cycleOutputnull

0 ≤ nodes ≤ 10⁴ · -10⁵ ≤ Node.val ≤ 10⁵ · Follow-up: O(1) extra memory.

Try it yourself

Java

class Solution {
    public ListNode detectCycle(ListNode head) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

When the hare (2 steps) meets the tortoise (1 step) inside the loop, the distance from head to the cycle entry equals the distance from the meeting point to the entry (mod cycle length). So restart one pointer at head and step both by 1.

PatternFast & Slow Pointers

Instinct A next-step function you can follow (list nodes, digit-square sums, array-as-pointers) and you need a cycle, its entry, or the middle in O(1) space.

Memory hack Tortoise and hare - on a loop track the hare laps the tortoise; restart the tortoise at the gate and they meet at the loop's door.

Open the Fast & Slow Pointers guide →

Approaches

Brute ForceRescan the Prefix for Each Node

Time O(n²)Space O(1)

Walk the list counting steps. For the node reached at step s, scan the first s nodes of the walk again; if it is among them, it is the first node visited twice — the cycle entry. Reaching null means no cycle.

Java

public ListNode detectCycle(ListNode head) {
    ListNode cur = head;
    for (int steps = 0; cur != null; steps++, cur = cur.next) {
        ListNode p = head;
        for (int k = 0; k < steps; k++, p = p.next) {
            if (p == cur) return cur; // seen before -> cycle entry
        }
    }
    return null;
}

Constant memory, but quadratic — ~5·10⁷ checks at n = 10⁴.

BetterHash Set of Visited Nodes

Time O(n)Space O(n)

Store each node (by reference) in a HashSet as we walk. The first node that is already in the set is the first one visited twice, which is exactly the start of the cycle.

Java

public ListNode detectCycle(ListNode head) {
    Set<ListNode> visited = new HashSet<>();
    for (ListNode cur = head; cur != null; cur = cur.next) {
        if (!visited.add(cur)) return cur; // add() is false if already present
    }
    return null;
}

Linear and obvious, but O(n) extra memory fails the follow-up.

OptimalFloyd's Tortoise & Hare

Time O(n)Space O(1)

Let a = head→entry, b = entry→meeting point, L = cycle length. At the meeting, fast walked twice as far: 2(a+b) = a+b+kL, so a = kL − b. A pointer from head and one from the meeting point, both stepping by 1, therefore meet exactly at the entry.

Java

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {          // inside the cycle
            ListNode start = head;
            while (start != slow) {
                start = start.next;
                slow = slow.next;
            }
            return start;            // cycle entry
        }
    }
    return null;                     // fast fell off: no cycle
}

Linear time, O(1) memory, list untouched — answers the follow-up.

Pro tip

Phase 1 alone solves Linked List Cycle (141); phase 2 is the extra step for the entry. Cycle length = steps for slow to return to the meeting node.

At a glance

Level	Approach	Time	Space
Brute Force	Rescan the Prefix for Each Node	`O(n²)`	`O(1)`
Better	Hash Set of Visited Nodes	`O(n)`	`O(n)`
Optimal	Floyd's Tortoise & Hare	`O(n)`	`O(1)`

Common pitfalls

Checking slow == fast before moving — they start equal at head.
Loop guard fast.next != null without fast != null — NPE on even-length lists.
Comparing vals instead of references — duplicate values are not a cycle.

Interview tips

Draw the a / b / L diagram and derive a = kL − b on the whiteboard.
Mention the HashSet version first, then optimise memory with Floyd.
Argue termination: inside the loop the gap shrinks by 1 each step, so they meet within L steps.

Pattern

Fast & slow pointers → detect a cycle (and its entry) in a linked list or functional graph.

My notes saved in this browser