Linked List Cycle – Solution & Complexity
Watch: Linked List Cycle with fast and slow pointers
A hash set of visited nodes works but costs O(n) memory. Instead, move a slow pointer one step and a fast pointer two. If there's a cycle, the fast one laps the slow one and they meet; if not, fast hits the end. O(n) time, O(1) space.
Solution Walkthrough
Step 1: Recognize the Pattern
The key pattern is: Floyd slow/fast pointers detect repeated traversal state. Identify the state and invariant before coding.
Step 2: Build the Algorithm
Advance one state transition at a time. Mark or update state before exploring dependent work.
Step 3: Check Edge Cases
Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.
Step 4: Solution and Complexity
Time: O(n). Space: O(1).
