Linked List Cycle II – Solution & Complexity
Watch: Linked List Cycle II with fast and slow pointers
Run slow and fast pointers until they meet, but don't return the meeting point. Move one pointer back to the head and step both by one: the head is as far from the cycle start as the meeting point is, plus whole laps, so they meet at the start. O(n) time, O(1) space.
Solution Walkthrough
Step 1: Recognize the Pattern
The key pattern is: Floyd's tortoise-and-hare — advance slow by one step and fast by two; if they meet inside a cycle, resetting one pointer to the head and advancing both by one step at a time makes them meet exactly at the cycle's start.
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) — each pointer visits at most O(n) nodes before either reaching the end or meeting inside the cycle. Space: O(1) — only a constant number of index variables are used, no visited-set.
This problem reuses the same plain-array
nextIndicesencoding aslinked-list-cycle(rather than a realListNodestructure), since a genuinely cyclic linked-list value isn't something the judge's structural list/tree conversion supports as an input or output — the array of next-indices sidesteps that entirely while still exercising real cycle-detection logic in all 5 languages.