Problem 24 · Linked Lists

Linked List Cycle II (Find Cycle Start)

MediumClassic DSA & systems

01Problem

Given a linked list, return the node where a cycle begins, or None if there is no cycle, using O(1) extra space.

02Key insight

Floyd's tortoise and hare: after slow and fast meet, a pointer from head and one from the meeting point, both moving one step, meet at the cycle start because the distances are congruent mod the cycle length.

03Solution

solution.pypython19 lines

from __future__ import annotations
from dataclasses import dataclass, field
from typing import Optional

@dataclass(eq=False)
class ListNode:
    val: int
    next: Optional[ListNode] = field(default=None, repr=False)

def detect_cycle(head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            finder = head
            while finder is not slow:
                finder, slow = finder.next, slow.next
            return finder
    return None

Try it first.

TimeO(n)

SpaceO(1)

tests.py · 4 passing

tests.pypython9 lines

nodes = [ListNode(i) for i in range(5)]
for x, y in zip(nodes, nodes[1:]):
    x.next = y
assert detect_cycle(nodes[0]) is None
nodes[-1].next = nodes[2]
assert detect_cycle(nodes[0]) is nodes[2]
solo = ListNode(9); solo.next = solo
assert detect_cycle(solo) is solo
assert detect_cycle(None) is None

04Staff-level follow-up

Same idea elsewhere? Find the duplicate in an array of n+1 values in [1, n] by treating i -> nums[i] as a linked list; also used for cycle detection in PRNG/hash iteration (Pollard's rho).