Find the entry of a cycle in a Java singly linked chain

Detect before locating

Move one pointer by one link and the other by two. If either reaches null, the chain terminates. If they meet, a cycle exists. A meeting node is not necessarily the entry. Reset one pointer to the head and move both one link at a time; their next meeting is the first node on the cycle.

The second walk follows from distances: after the first meeting, the head-to-entry distance and the meeting-to-entry distance differ by a whole number of cycle lengths. Advancing both at the same rate removes that difference. The fixture connects a tail back to an internal dispatch ID and separately checks an acyclic chain.

Choose the right container

This algorithm applies when code owns next references. Java's LinkedList collection keeps those references private, so its public API cannot expose a cycle entry. A collection cannot be made cyclic through ordinary List operations. The distinction matters when interview pseudocode is pasted into production code that actually holds a List<String>.

Before reversing or merging a custom chain, reject cycles or establish acyclicity at construction. Otherwise a traversal meant to be linear can run indefinitely.

Working program

public class DispatchCycleEntry {
    static final class Node {
        final String dispatchId;
        Node next;
        Node(String dispatchId) { this.dispatchId = dispatchId; }
    }
    static Node entry(Node head) {
        Node slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                Node fromHead = head;
                while (fromHead != slow) {
                    fromHead = fromHead.next;
                    slow = slow.next;
                }
                return fromHead;
            }
        }
        return null;
    }
    public static void main(String[] args) {
        Node intake = new Node("intake-47");
        Node verify = new Node("verify-82");
        Node ship = new Node("ship-15");
        intake.next = verify; verify.next = ship; ship.next = verify;
        System.out.println(entry(intake).dispatchId);
        ship.next = null;
        System.out.println(entry(intake) == null);
    }
}

Output

verify-82
true

Cost and ownership

Detection and entry search each take at most O(n) link visits, with O(1) extra references. The algorithm reads node identity, not payload equality; two records with the same dispatch ID are still distinct nodes.

Common Mistakes

• Do not return the first fast/slow meeting point as the entry without the second walk.
• Do not compare dispatch ID values to decide whether two pointers meet.
• Do not dereference fast.next.next before checking both fast and fast.next.

Read next

Reverse a singly linked chain in Java without allocating new nodes, merge sorted linked chains, Java LinkedList: operations, internals and failure cases, Java depth-first search: cycles and explicit work stacks.

Continue with owned-node algorithms

Continue with Remove the nth node from the end of a Java linked chain, Find the shared node of two Java linked chains by identity.