Linked List Cycle II – Solution & Complexity
Solution Walkthrough
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.
2. Build the Algorithm
Advance one state transition at a time. Mark or update state before exploring dependent work.
3. Check Edge Cases
Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.
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 nextIndices encoding as linked-list-cycle (rather than a real ListNode structure), 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.
