129. Linked List Cycle

Walk the list one node at a time. If you ever encounter a node you've already seen, you've looped back — there's a cycle. A set of node references (not values) is the natural "seen" tracker.

Why we store references, not values

Two distinct nodes can hold the same value. If we stored values, we'd report a cycle whenever a duplicate value appeared. We need to detect that we've revisited the exact same node object. Python's set hashes objects by identity by default for custom classes, which is exactly what we want.

Steps

1. Initialise seen = set().
2. While head is not None:
   • If head is already in seen, return True — we've revisited a node, so there's a cycle.
   • Otherwise add head to seen and advance head = head.next.
3. If we fall off the end (head is None), there was no cycle — return False.

Walk-through

Cyclic case: 1 → 2 → 3 → 4 → 5 → 3 (back). The next of node 5 points back to node 3.

Acyclic case: 1 → 2 → 3 → None. The loop visits each node once, never finds a repeat, and head becomes None after step 3 — return False.

Edge cases

• Empty list: the while doesn't enter; return False.
• Single node, no cycle: one iteration, then head = None, return False.
• Single node looping to itself: head is added to seen, then head.next = head revisits, return True.

Complexity

• Time: O(n) — at most n insertions and lookups before either revisiting or hitting None.
• Space: O(n) — up to n references in the set.

import java.util.*;

class Solution {
    static class ListNode {
        int val;
        ListNode next;
        ListNode(int v) { val = v; }
    }

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

Send two pointers walking down the list — slow taking 1 step at a time, fast taking 2. On a straight list, fast falls off the end. On a cyclic list, both eventually enter the cycle, and from that moment fast gains 1 position on slow each iteration — so they're guaranteed to meet.

The picture

Imagine a tortoise and a hare running on the list. The hare is twice as fast. If the list is finite (no cycle), the hare reaches the end and stops. If the list loops, both eventually enter the loop and the hare keeps lapping the tortoise — and on a cyclic track, a faster runner must catch up to a slower one.

Why they must meet (on a cyclic list)

Once both pointers are inside the cycle (let it have length L), look at the gap d = (fast position - slow position) mod L. After every iteration, fast advances 2 and slow advances 1, so d decreases by 1 each step (modulo L). After at most L steps, d = 0 — they coincide.

Steps

1. Initialise slow = head, fast = head.
2. While fast and fast.next are both non-None (so we can take two .next steps without crashing):
   • slow = slow.next
   • fast = fast.next.next
   • If slow is fast, return True.
3. If we fall out of the loop (fast reached None), return False.

Walk-through

Cyclic case: 1 → 2 → 3 → 4 → 5 → 3 (5 loops back to 3, cycle length 3).

Acyclic case: 1 → 2 → 3 → 4 → None.

Why the loop guard is fast and fast.next

Each iteration does fast.next.next. To avoid a NoneType has no attribute 'next' crash, we need both fast and fast.next to exist before stepping.

Edge cases

• Empty list: fast = None, loop doesn't enter, return False.
• Single node, no cycle: fast.next = None, loop doesn't enter, return False.
• Single node looping to itself: slow = fast = node, then both step (slow → node, fast → node), they're equal — return True.

Complexity

• Time: O(n) — at most n iterations before either reaching None (acyclic) or completing one cycle pursuit (cyclic).
• Space: O(1) — two pointers, constant.