LeetCode 141 Linked List Cycle - Example and Complexity Analysis

Trace a list 1 → 2 → 3 → 4 → 2 (node 4 points back to node 2).

Initialize: slow = 1, fast = 1.

Step 1: slow = 2, fast = 3.

Step 2: slow = 3, fast = 2 (fast went 4 → 2).

Step 3: slow = 4, fast = 4.

They meet at node 4. Return true.

For a list without cycle: fast reaches null and we return false.

Slow moves $n$ steps at most. Fast moves $2n$ steps at most. Both are $O(n)$ time.

Only two pointers used. $O(1)$ space.