A billing worker walks a singly linked chain of retry hops. Each hop’s next should hit null when the attempt is finished. After a botched splice, one hop pointed at an earlier node. The intern version stuffed amounts into a HashSet. Two hops billed $12.00 looked like a loop. A real loop of unique amounts never collided. The worker was still walking when the job timed out.

A linked-list cycle means some node’s next points at an earlier node. Values can repeat without a loop.

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. Here we only care about whether two walks of next ever land on the same node object.

The problem

Given the head of a singly linked list, return whether the list contains a cycle. An empty list has no cycle. A single node whose next is null has no cycle. A node that points at itself does.

1 → 2 → 3 → 4,  4.next = node 2   (a loop)     →  true
1 → 2 → 3 → null                               →  false
(empty)                                        →  false
1 → null                                       →  false
1.next = 1            (self loop)              →  true

A node is the usual two fields:

final class ListNode {
    int val;
    ListNode next;

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

Note: Detection is node identity, not values. [1, 1] with both nodes pointing forward to a real tail is not a cycle. [1, 2, 3] with the last next pointing at the first node is.

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. If it is, some earlier hop pointed here — that is a cycle. If next is null, the list ended.

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

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

Slow and fast meet on the loop

Apply two pointers on next, not a coloring walk over a graph. Both start at head. slow takes one next. fast takes two. If fast cannot take two steps, there is no cycle. If they ever refer to the same node after a move, fast lapped slow on a loop.

Walk 1 → 2 → 3 → 4 with 4.next pointing at node 2:

start:  slow=1  fast=1

step 1: slow=2  fast=3     2 != 3
step 2: slow=3  fast=2     3 != 2   (fast: 3 → 4 → 2)
step 3: slow=4  fast=4     meet     (slow: 3 → 4; fast: 2 → 3 → 4)

return true

Acyclic 1 → 2 → 3 → null dies when fast cannot take two steps: after slow=2, fast=3, fast.next is null. You never claim a meeting at the start — both names begin on head.

boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

Time is O(n) — acyclic, fast hits null; cyclic, they meet after a linear number of steps. Space is O(1) besides the two pointers. The HashSet walk is also O(n) time and spends O(n) extra; slow and fast spend the same time without pinning every node.

Compare after both pointers have moved. Checking slow == fast before the first step is always true. == is reference equality; do not switch to equals on val.

Empty list: fast is already null, the loop never runs, you return false. One node, next null: fast.next is null, same return. Self loop: the first iteration lands both on that node, you return true. No special cases.

What interviewers usually poke next

  • Where the cycle starts. After they meet, put one pointer back at head and walk both one step at a time; the next meeting is the entrance. That writeup will live at /interview/linked-lists/medium/linked-list-cycle-ii/.
  • Length of the cycle. Freeze one pointer at the meeting node and count the other’s lap back to it.
  • Break the cycle. Find the entrance, then the predecessor of that node, then set next to null.
  • 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 on that pointer is the procedure; do not reach for colors.

You are done with this problem when you can say why a set of values is the wrong test, why a set of nodes is honest extra space, and why slow and fast must move before you compare them.