Linked List Cycle

easyTests passed 2026-11-11v1.0.0

TC: O(N)|SC: O(1)

Linked Lists Original Statement (leetcode).md

1. Core Invariant / The Trick

Floyd’s Tortoise & Hare: advance `slow` by 1 and `fast` by 2. Inside a cycle of length C, their relative gap decreases by 1 per step, guaranteeing collision inside <= C iterations.

2. Complexity Bounds & Proof

If acyclic, `fast` reaches null in <= N/2 steps. If cyclic with prefix length F and cycle C, `fast` catches `slow` in <= F + C steps.

3. Minimal Idiomatic Code

def hasCycle(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

4. Failure Modes & Interview Follow-ups

Pitfalls:- Checking `fast.next` without first checking `fast != null` dereferences null on empty/even lists. - Returning true on initial `slow == fast` check before advancing.

Follow-ups:- Linked List Cycle II: after meeting, reset one pointer to `head` and move both by 1; they meet at the cycle entry because distance(head -> entry) === distance(meet -> entry) mod C.

Personal Notes & Scratchpad (Local-First Yjs CRDT)

Saved instantaneously in IndexedDB. Streams live across peers via Hocuspocus when signed in.

Related Invariants

Reorder List (O(N))Reverse Linked List (O(N))

Browser Scratchpad

Console Output

Click Run or press Cmd/Ctrl+Enter to execute locally in a Web Worker.