Remove Nth Node From End of List – Solution & Complexity
Solution Walkthrough
Step 1: Recognize the Pattern
The key pattern is: Two-pointer gap technique: advance a lead pointer n steps ahead, then move both until the lead hits the end. 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(L) where L is the list length. Space: O(1) auxiliary in every language. The Rust implementation uses two passes (one pass to count length, one to remove the node) because the classic one-pass pointer-gap technique runs into move/borrow conflicts on Option<Box<ListNode>>; the other implementations use the one-pass pointer-gap technique.
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.
