Linked List Cycle II – Solution & Complexity
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.
