Linked List Cycle

1. Problem & Core Objective

Return true if the list has a cycle — that is, if some node's next pointer leads back to an earlier node.

3 → 2 → 0 → -4
    ↑          ↓
    └──────────┘        cycle → true

1 → 2 → null            no cycle → false

Constraints: 0 <= n <= 10^4 · -10^5 <= Node.val <= 10^5

What's actually being tested: Floyd's cycle detection — the tortoise and hare — and specifically whether you can explain why it works rather than just recite it. The follow-up ("find where the cycle starts") is where most of the value is, and it feeds directly into question 8.

2. First-Principles Thought Process

What a cycle actually means

A null-terminated list ends. A cyclic one doesn't — walking it loops forever. So "detect a cycle" is really "detect that this walk will never terminate", and you can't detect that by waiting.

You need evidence of repetition: have I been here before?

The obvious answer: remember where you've been

Keep a HashSet of visited nodes. If you ever see one twice, there's a cycle. If you reach null, there isn't.

Correct, O(n) time — and O(n) space.

The insight: two speeds

Put two pointers on the list. slow moves one node per step, fast moves two.

• If there's no cycle, fast reaches null and you're done.
• If there is a cycle, both pointers eventually enter it and can never leave. Inside a finite loop with fast gaining on slow, they must collide.

Why they must meet — the part to actually explain

Once both are inside the loop, consider the gap from fast to slow measured around the cycle. Each step, slow advances 1 and fast advances 2, so the gap shrinks by exactly 1 per step.

A quantity that decreases by exactly 1 each step, in a finite cyclic space, must hit 0. It cannot skip past — that's what makes step size 2 special.

If fast moved 3 steps at a time, the gap would shrink by 2 per step and could jump from 1 to −1, stepping over the meeting point entirely. It would still work eventually in many cases, but the clean "must meet" argument is lost. That's the real reason the hare moves exactly twice as fast.

3. Solution Paths

Approach 1 — Visited set (brute force)

public boolean hasCycle(ListNode head) {
    Set<ListNode> seen = new HashSet<>();
    for (ListNode p = head; p != null; p = p.next)
        if (!seen.add(p)) return true;      // add returns false if already present
    return false;
}

• Time O(n) · Space O(n)

Counter-questions on this approach

⭐ "This is O(n) time, same as optimal. So what's wrong with it?"

The O(n) space. It stores every node just to answer a yes/no question. And the storage isn't buying information I couldn't get otherwise — the two-pointer version proves the same fact with two variables.

At n = 10^4 the set is fine. But this exact routine is the core of question 8, where the whole point is O(1) space, so it's worth having the better version ready.

⭐ "Why seen.add(p) rather than seen.contains(p) then seen.add(p)?"

add returns false if the element was already present, so it tests and inserts in one hash lookup instead of two. Same complexity, half the work, and it reads as a single atomic "have I seen this before?".

"Does this rely on ListNode.equals?"

It relies on ListNode not overriding equals/hashCode, so the set compares by identity. That's what's needed — two distinct nodes holding the same value are different nodes. If ListNode had value-based equality, a list like 1 → 1 → null would falsely report a cycle. Worth stating, because it's a silent correctness dependency. See 05.

Approach 2 — Mutate the list as a marker (rejected, but worth discussing)

public boolean hasCycle(ListNode head) {
    while (head != null) {
        if (head.val == Integer.MIN_VALUE) return true;   // been here
        head.val = Integer.MIN_VALUE;
        head = head.next;
    }
    return false;
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "This is O(1) space. Why is it a bad answer?"

It destroys the caller's data. Every node's value is overwritten, so the list is unusable afterwards — and the method's contract is to inspect, not modify.

It's also fragile: it assumes Integer.MIN_VALUE never occurs legitimately. Here the constraint is |val| <= 10^5, so that happens to hold, but the correctness now depends on a value-range assumption rather than on the algorithm. If the constraints changed, it would silently start reporting false positives.

"Is there ever a case where destructive marking is acceptable?"

Yes, when the structure is genuinely yours and the value range is truly reserved — some in-place array problems mark by negating elements, which is reversible. But here it's neither reversible nor safe, and Floyd's gives O(1) space without either flaw. I'd mention this approach only to dismiss it.

Approach 3 — Floyd's tortoise and hare (optimal)

public boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;                    // fast hit the end — no cycle
}

• Time O(n) · Space O(1)

Counter-questions on this approach

⭐ "Prove they actually meet. Why can't fast jump over slow?"

Once both are in the cycle, look at the distance from fast to slow going forward around the loop. Each step slow gains 1 and fast gains 2, so that distance decreases by exactly 1 every step.

A non-negative integer decreasing by exactly 1 must reach 0 — it can't skip a value. When it's 0, they're on the same node. That's the proof, and it's why the step sizes are 1 and 2 rather than any two different numbers.

With steps of 1 and 3, the gap falls by 2 each time and could go from 1 straight to −1 — passing through without landing.

⭐ "Why is the loop condition fast != null && fast.next != null?"

Both are needed, and the order matters. fast.next.next dereferences twice, so I must know fast is non-null and fast.next is non-null before taking the second hop. Java's && short-circuits, so if fast is null the second check is never evaluated — reversing the order would throw a NullPointerException on a null head.

Only fast needs checking; slow is always behind it, so if fast is safe, slow is.

"Why start both at head rather than slow = head, fast = head.next?"

Either works for detection. Starting both at head means the first comparison happens after both have moved, so the trivial slow == fast at step zero is never a false positive. Starting fast one ahead requires checking after the move too, and it breaks the clean distance argument used in phase 2 for question 8 — where slow = fast = head is required for a = c to hold. I use the same convention in both for consistency.

"How many steps before they meet?"

At most O(n). slow takes at most λ steps to enter the cycle, and then at most another cycle-length worth of steps for the gap to close — so under 2n total. Each pointer moves a bounded number of times, so it's linear.

Comparison

4. Why the Optimal Wins

All three are O(n) time, so the comparison is space and safety.

The visited set stores n node references to answer one boolean. Floyd's proves the same fact with two pointers, by converting "have I been here before?" into "does a shrinking gap reach zero?" — a question answerable with no memory at all.

The destructive version matches on space but trades away the caller's data and depends on a sentinel value being unused. Floyd's needs neither concession.

The framing worth keeping:

Two pointers at different speeds turn "detect repetition" into "detect a collision" — and a gap that shrinks by exactly 1 cannot skip zero.

That reframing is what makes question 8 possible at all, where there is no list to put in a set.

5. Java Prerequisites

The Floyd template

ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) { /* cycle */ }
}

Short-circuit evaluation. && stops at the first false, which is what makes fast != null && fast.next != null safe. Swapping the operands throws.

Reference vs value comparison

slow == fast              // same object — correct here
slow.val == fast.val      // same value — WRONG, duplicates give false positives

Set.add as a test-and-insert

if (!seen.add(p)) { /* was already present */ }

6. Interview Communication Guide

Clarifying questions: Can the list be empty (yes)? Can a node point to itself (yes — a one-node cycle)? May I modify the list (prefer not to)? Is O(1) space required (ask; it changes the answer)? Do I need to return where the cycle starts (that's LC 142 — worth offering)?

The pitch

"A cyclic list never terminates, so I can't detect it by walking and waiting. I need evidence of repetition.

The direct approach is a HashSet of visited nodes — see one twice and there's a cycle. O(n) time, O(n) space, and it relies on ListNode using identity equality, which it does since it doesn't override equals.

Floyd's gets it to O(1). Two pointers: slow moves one node per step, fast moves two. No cycle, and fast runs off the end. A cycle, and both pointers end up trapped inside it — and then they must collide.

The reason they must collide is worth being precise about. Once both are in the loop, the forward distance from fast to slow shrinks by exactly 1 each step, since fast gains 2 and slow gains 1. A non-negative integer that decreases by exactly 1 has to hit zero — it can't jump over it. That's why the speeds are 1 and 2; at 1 and 3 the gap falls by 2 and could step straight past.

The loop condition checks both fast and fast.next before the double hop, relying on && short-circuiting.

O(n) time, O(1) space, and the input is untouched."

Edge cases to volunteer:

Name the self-loop and the duplicate-values case. The first is the minimal cycle; the second catches anyone comparing slow.val == fast.val instead of slow == fast.

7. Follow-Up Questions — Modified Constraints

⭐ "Return the node where the cycle begins, not just whether one exists."

LeetCode 142, and the reason this question matters. After they meet, reset one pointer to head and advance both one step at a time — they meet at the entrance.

The proof: let a be the distance from head to the entrance, b from the entrance to the meeting point, and c from the meeting point back around to the entrance. slow travelled a + b; fast travelled twice that. If fast went around exactly once more, it travelled a + b + (b + c). Setting 2(a + b) = a + 2b + c gives a = c.

So the distance from the head to the entrance equals the distance from the meeting point to the entrance — walk both at speed 1 and they arrive together.

If fast lapped k times the identity becomes a = c + (k−1)(b+c), which is a ≡ c modulo the loop length. The conclusion is unchanged: walking a steps from the head lands on the entrance either way.

⭐ "Find the length of the cycle."

Once they meet, hold one pointer still and walk the other around until it returns. The number of steps is the cycle length. O(n) time, still O(1) space.

"What if it were a doubly linked list?"

Floyd's works unchanged — it only uses next. But you'd also have the option of validating node.next.prev == node at every step, which catches corruption a cycle check alone wouldn't.

"Detect a cycle in a general directed graph."

Floyd's doesn't apply, because a node can have many successors and there's no single "walk". Use DFS with three colours — unvisited, in-progress, done — and report a cycle on reaching an in-progress node. That's O(V + E) time and O(V) space, and it's the standard approach for Course Schedule.

"Apply this to something that isn't a list at all."

That's question 8. Any function f iterated from a starting point — x, f(x), f(f(x)), … — forms a chain that must eventually repeat if the domain is finite. Floyd's works on the sequence, with no data structure required. It's also how Pollard's rho factorisation finds collisions.

"What if you could not modify anything and had only O(1) space, but the list were on disk?"

Floyd's is poor here — fast and slow read different regions, so it thrashes. Brent's algorithm finds cycles with the same O(1) space but fewer pointer dereferences and better locality, by doubling the search distance rather than running two concurrent walks.