LeetCode 141 – Linked List Cycle

Linked List Cycle is where Floyd's tortoise and hare earns its keep. The hash-set answer is correct, obvious and takes thirty seconds; the two-pointer answer takes constant space and rests on an argument you should be able to give, because "they meet eventually" is an assertion, not a proof.

The problem

Given the head of a linked list, determine whether it contains a cycle — whether some node can be reached again by following next.

3 -> 2 -> 0 -> -4        -> true
     ^          |
     +----------+

1 -> 2 -> 1 (back to head)  -> true
1                           -> false
[]                          -> false
1 -> 1 (self loop)          -> true

The follow-up asks for O(1) space, which is the entire reason this problem is interesting.

The hash set answer

Walk the list adding each node to a set; if a node is already there, it is a cycle; if you reach null, it is not. O(n) time, O(n) space, four lines.

Give it first. It proves you understand what a cycle is, and it is the correct answer when the constraint is not stated. Then say "the follow-up wants constant space, which rules out remembering what I have seen — so I need two things moving at different speeds".

Note the set must be keyed by identity, not by value. A list containing two separate nodes both holding 1 is not a cycle, and a value-keyed set would say it is.

Two pointers, and why they must meet

Move one pointer one step at a time and another two steps. If the list ends, there is no cycle. If there is a cycle, both pointers eventually enter it and then the fast one gains on the slow one by exactly one node per step.

once both are inside the cycle:

  gap shrinks by 1 every step:   k, k-1, k-2, ..., 1, 0

  it cannot jump over, because the gap decreases by exactly one.

That is the proof, and it is short enough to say out loud. The fast pointer closing at one node per step is what rules out the intuition that it might repeatedly leapfrog the slow one — a gap decreasing by exactly 1 must pass through 0.

Speeds of 1 and 3 would also terminate, but the gap then changes by 2 per step and can skip zero in an even-length cycle. One and two is not an arbitrary choice.

Java

class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;

        // fast is the only one that can fall off the end, so it is the only one checked.
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) return true;    // reference equality, not .equals
        }

        return false;                          // fast reached the end: no cycle
    }
}

Both conditions in the loop are needed. fast != null guards the first hop and fast.next != null guards the second — dropping either throws on a list with an even or odd number of nodes respectively, so a quick test on one parity will not catch it.

slow == fast compares references. Using equals would report a cycle on any list containing two equal values, which is the same trap as the value-keyed hash set.

Starting both at head means they are equal before the loop body runs — which is why the comparison sits after the moves, not before. Checking first would return true immediately on every input.

Python

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        slow = fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow is fast:          # `is`, not `==` -- identity, not value
                return True

        return False

is rather than == for the same reason. If ListNode ever defined __eq__, the value comparison would silently start reporting cycles that are not there.

Complexity

The time bound deserves a word, because it is not obvious. Let the tail before the cycle be length t and the cycle length c. The slow pointer takes t steps to enter the cycle, and once both are inside, the gap is at most c and closes by one per step. So the meeting happens within t + c ≤ n steps — linear, not quadratic, which is the question that follows "prove they meet".

The pattern

Fast and slow pointers solve a family of list problems in constant space:

Problem 202 is the one worth noticing: the "list" is n → sum of squared digits, with no nodes at all. Floyd's algorithm needs a successor function, not a data structure.

What the interviewer is checking

• That you offer the hash set first and then meet the space constraint.
• That you can argue why the pointers must meet, not just that they do.
• Both null checks in the loop condition.
• Identity comparison rather than value equality.
• That the comparison happens after the moves, since both start at the head.
• Empty list, single node, and a single node pointing at itself.
• That the bound is O(n), with the t + c argument.