4.9.7 — Linked List Cycle

LeetCode 141 · Easy · ★ Blind 75

The problem

Return true if the linked list has a cycle — that is, if following next repeatedly ever revisits a node.

3 → 2 → 0 → -4
    ↑         |
    └─────────┘        →  true

1 → 2 → null           →  false

The follow-up asks for $O(1)$ space.

The pattern

The straightforward answer is a hash set of visited nodes: walk forward, and if you meet a node you have already seen, there is a cycle. $O(n)$ time and $O(n)$ space, and it is a perfectly good first answer.

The $O(1)$ -space answer is Floyd's cycle detection, usually called the tortoise and the hare.

Move slow one node per step and fast two. If the list ends, fast falls off and there is no cycle. If there is a cycle, both pointers end up inside it, and then they must meet.

Why they must meet

Once both pointers are inside the loop, look at the gap between them, measured as how far slow is ahead of fast going around the loop.

Every step, fast gains one node on slow — it moves two while slow moves one. So the gap shrinks by exactly 1 per step. A quantity that decreases by exactly one each step and cannot go below zero must reach zero. When it does, the two pointers are on the same node.

The step size of 1 is what makes this airtight. If fast moved three at a time, the gap would shrink by 2 each step and could jump straight over zero without ever landing on it, depending on the loop length. Moving by one guarantees no skipping.

That is the entire proof, and it is short enough to say out loud.

The solution

PythonTypeScript

python

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

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow is fast:
                return True

        return False

function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;

  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }

  return false;
}

while fast and fast.next checks both nodes that fast is about to step through. Checking only fast would crash when fast.next is null.

Compare identity, not value. slow is fast in Python, slow === fast in TypeScript. Two different nodes can hold the same value.

Check after moving, not before. Both pointers start on the head, so checking first would report a cycle immediately on every list.

Complexity

$O(n)$ time. Before entering the loop, slow walks at most n steps. Inside the loop, the gap starts at less than the loop length and shrinks by one per step, so at most another n steps.

$O(1)$ space.

Finding where the cycle starts

Linked List Cycle II (LeetCode 142) asks for the node where the cycle begins. There is a small piece of arithmetic that gives it, and it is worth having.

Let a be the distance from the head to the start of the cycle, b the distance from there to the meeting point, and c the rest of the loop.

When they meet, slow has walked a + b. fast has walked exactly twice that, and it has also gone around the loop some whole number of times:

2(a + b) = a + b + k(b + c)

Cancel a + b from both sides:

a + b = k(b + c)

a = k(b + c) - b = (k-1)(b+c) + c

Read that in words: the distance from the head to the cycle start is the same as the distance from the meeting point to the cycle start, plus some whole number of laps. Laps do not matter, because going around the loop returns you to the same place.

So: put one pointer back at the head, leave the other at the meeting point, and move both one step at a time. They meet at the start of the cycle.

python

def detectCycle(self, head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            slow = head                  # restart one pointer
            while slow is not fast:
                slow, fast = slow.next, fast.next
            return slow
    return None

Where this goes next

The technique is not really about linked lists. It is about any sequence where each state has exactly one successor, and it detects that the sequence eventually repeats.

Find the Duplicate Number — treat nums[i] as a pointer from i, and the duplicate becomes the entry to a cycle. That is 4.9.8, and it is the most surprising application in the set.
Happy Number — repeatedly sum the squares of the digits; the process either reaches 1 or cycles. Chapter 4.28.
Detecting cycles in a state machine or a random number generator — the same test, and the same reason it works.

The rule: when a process has exactly one next state, two pointers at different speeds detect repetition in $O(1)$ space.

What the interviewer will push on

"Prove the pointers must meet." The gap shrinks by exactly one per step and cannot skip zero.

"Why does fast move two and not three?" Moving by three shrinks the gap by two, which can step over zero without landing on it.

"Find where the cycle starts." The algebra above. Being able to derive it rather than recite it is what they are checking.

"What about the hash set version?" $O(n)$ space, simpler, and completely acceptable if the follow-up has not been asked yet. Say it first.

One thing to volunteer: name the technique — Floyd's cycle detection — and say it works on any sequence with a single successor, not just lists. That opens the door to the next problem.

Next: 4.9.8 Find the Duplicate Number — an array problem that turns out to be this one in disguise.

4.9.7 — Linked List Cycle ​

The problem ​

The pattern ​

Why they must meet ​

The solution ​

Complexity ​

Finding where the cycle starts ​

Where this goes next ​

What the interviewer will push on ​