Reverse Linked List II – Solution & Complexity
Solution Walkthrough
1. Recognize the Pattern
The key pattern is: a dummy-node walk to the node just before left, then repeatedly splicing the next node to the front of the reversed segment. Identify the state and invariant before coding.
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) — a single pass to reach left plus one pass to reverse the segment. Space: O(1) auxiliary in Python/JavaScript/Java/Go, which splice pointers in place. The Rust implementation instead collects values into a Vec and rebuilds the list (O(n) auxiliary) because the classic pointer splice runs into move/borrow conflicts on Option<Box<ListNode>> chains — see the inline comment on the Rust solution.
All 5 languages below run and submit against the remote judge for this problem — Java/Go/Rust use the same real ListNode structural-type support the judge added for the rest of the linked-list/tree track.
