A queue-drain worker follows next through a chain of delivery hops. Linked List Cycle already returned true: some hop points at an earlier node. On-call still cannot cut the ring. They need that earlier node — the entrance — so the predecessor can point at null. The intern stuffed every hop into a HashSet and returned the first repeat. Staging’s twelve-hop chain was fine. Production’s hundred-thousand-hop loop allocated a set the size of the prefix plus the ring; the heap dumped before anyone saw the splice.

Linked List Cycle II asks for the node where the cycle begins, or null if there is none. Identity, not value. Cycle I already answers whether two pointers on next ever land on the same object. This writeup starts after that meet.

This is an interview writeup, not a two-pointers lecture. The linked list post owns splice and why get(i) walks. The two pointers post owns the slow/fast move rule. Cycle I owns the collision. A general graph’s colors and back edges are a different procedure. Here we only care about the second walk: one pointer back at head, both one step, next collision is the entrance.

The problem

Given the head of a singly linked list, return the node where a cycle begins, or null if the list is acyclic. An empty list has no cycle. A node that points at itself is its own entrance.

1 → 2 → 3 → 4 → 5,  5.next = node 3     →  node 3
1 → 2 → 3 → null                        →  null
(empty)                                 →  null
1.next = 1                              →  node 1
1 → 2 → 3,  3.next = node 1             →  node 1

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = val;
    }
}

Note: The answer is a node object, not an index and not val. [1, 1] with both nodes pointing forward to a real tail is acyclic. The last next pointing at the first node is a cycle that starts at head.

A HashSet of nodes is the honest brute force

Walk from head. Before you step to next, ask whether this node object is already in the set. The first repeat is the entrance: every node on the prefix was new; the splice is the first you have already held.

ListNode detectCycleSeen(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    ListNode current = head;
    while (current != null) {
        if (seen.contains(current)) {
            return current;
        }
        seen.add(current);
        current = current.next;
    }
    return null;
}

ListNode does not override equals / hashCode, so the set hashes identity. That is the correct brute. A HashSet of val is not an entrance. Duplicate amounts are false positives; a loop of unique amounts never reports. The set of nodes is honest and still costs one extra entry per hop. Interviewers will ask whether you can drop it.

After they meet, reset one pointer to head

Run the same slow/fast loop Cycle I already wrote. If fast cannot take two steps, there is no cycle — return null. If they meet, that node sits somewhere on the ring, not necessarily at the splice.

Leave one pointer on the meeting node. Put the other back at head. Both take one next per step. The next time they refer to the same object, that object is the entrance.

Walk 1 → 2 → 3 → 4 → 5 with 5.next pointing at node 3. Cycle I’s meet lands on node 4. Then:

reset:  a=head(1)  b=4
step 1: a=2        b=5
step 2: a=3        b=3     meet — entrance

Short reason you can say at the board: let μ be hops from head to the entrance and λ the ring length. After they meet, fast has run twice as far, so the extra distance is a multiple of λ. That identity rearranges to: remaining distance from the meeting node around to the entrance equals μ (mod λ). Same remaining distance, same speed — they collide at the splice.

ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

Time is O(n) — the Cycle I pass, then at most μ more steps on the prefix. Space is O(1) besides the two pointers. The HashSet walk is also O(n) time and spends O(n) extra; the reset walk spends the same time without pinning every node.

Do not return the first meeting node. That is a point on the ring. Returning it as the entrance is wrong unless the cycle happens to start there. == is still reference equality; do not switch to equals on val.

Empty list: fast is already null, you never enter, you return null. Acyclic tail: fast cannot take two steps, same return. Self loop: they meet on that node, slow = head is already that node, the inner while does not run, you return it. Cycle that starts at head: same shape — after the reset the two names already match. No special cases.

What interviewers usually poke next

  • Length of the cycle. Freeze one pointer at the entrance (or at the Cycle I meet) and count the other’s lap back to it.
  • Break the cycle. This writeup’s node is the entrance. Walk once more to its predecessor, then set next to null.
  • Boolean only. That is Linked List Cycle. Stop at the first meet.
  • Two lists, shared suffix. Different job: first common node by identity, not a ring. Already covered in Intersection of Two Linked Lists.
  • Reverse the list. Different job: rewire next, return a new head. Already covered in Reverse Linked List.
  • Graph coloring / DFS. A general directed graph needs visited-state on an adjacency walk. A singly linked list has at most one next. Slow and fast, then the reset, is the procedure; do not reach for colors.

You are done with this problem when you can say, out loud, why the first collision is only “on the ring,” why sending one pointer back to head finds the entrance, and why a set of nodes is honest extra space.