141. Linked List Cycle

Detecting a loop in a linked list looks like it needs a notebook of every node you’ve visited — and it does, until you realize two pointers running at different speeds settle it with no extra memory at all. That fast/slow trick is a staple of the linked list patterns, and it shows up far beyond this one problem.

The problem

You’re handed the head of a singly linked list. Somewhere down the line a node’s next might point back to an earlier node, forming a loop that never terminates. Return true if such a cycle exists, false otherwise. (Full statement on LeetCode.)

Picture three nodes A → B → C where C.next points back to B. Walk forward forever and you’ll loop B → C → B → C… — that’s a cycle. If C.next were null instead, you’d fall off the end and the answer is false.

Intuition: the tortoise and the hare

The naive fix is a HashSet: walk the list, and the first time you meet a node you’ve already stored, you’ve found the loop. Correct, but it costs $O(n)$ memory. The follow-up asks for constant space, and that’s where Floyd’s cycle detection comes in.

Run two pointers from the head. The slow one advances a single node per step; the fast one takes two. If the list ends, fast reaches null and you’re done — no cycle. But if there’s a loop, both pointers eventually enter it and can never leave. Once they’re both circling, think of it as a track: each step, fast closes the gap to slow by exactly one node. A gap that shrinks by one every step can’t skip over zero, so the two pointers are guaranteed to land on the same node.

$\text{gap}_{t+1} = \text{gap}_t - 1 \implies \text{they meet}$

That guaranteed collision is the whole proof. No cycle means fast falls off the end; a cycle means the hare catches the tortoise.

Solution

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        // fast moves two steps, so guard both fast and fast.next
        while (fast != null && fast.next != null) {
            slow = slow.next;        // tortoise: one step
            fast = fast.next.next;   // hare: two steps
            if (slow == fast) return true;  // they collided inside a loop
        }
        return false;                // fast ran off the end — no cycle
    }
}

The loop condition does double duty: it exits cleanly for an empty list (head == null) and for any list that terminates, since fast or fast.next becomes null. Note the comparison is slow == fast — reference identity, not .equals() — because a cycle is about the same node object being revisited, not about equal values.

Complexity

Approach	Time	Space
HashSet of visited nodes	$O(n)$	$O(n)$
Floyd’s fast/slow pointers	$O(n)$	$O(1)$

Both are linear time. Floyd wins on space: the hare needs at most one full lap around the loop to catch the tortoise, so the total steps stay bounded by $O(n)$.

In an interview

Offer the HashSet solution first to show you can solve it, then pivot: “but I can do it in constant space with two pointers.” The detail interviewers listen for is why the collision is guaranteed — the gap between the pointers shrinks by one each step, so it must hit zero. That reasoning is what separates reciting the algorithm from understanding it.

The classic trap is the null-pointer crash: since fast jumps two nodes, you must check both fast != null and fast.next != null before dereferencing, or a list of length one throws instantly. The same tortoise-and-hare setup finds the middle of a list in Reorder List and drives the gap technique in Remove Nth Node From End of List; the linked list patterns hub collects where two-pointer tricks recur.

References

• LeetCode 141 — Linked List Cycle