Remove Nth Node From End of List
Remove Nth Node From End of List is a medium Linked List problem from the Blind 75. The key pattern is two pointers a fixed gap apart, and a good solution runs in O(n) time.
Problem
Remove the nth node counted from the end of the value-array list and return the remaining values.
Examples
Example 1
Input
{"values":[4,7,1,9],"n":2}Output
[4,7,9]Example 2
Input
{"values":[1,2],"n":1}Output
[1]Example 3
Input
{"values":[1,2,3,4,5],"n":2}Output
[1,2,3,5]Approach
Advance a lead pointer n steps, then move both pointers until the lead reaches the end; the trailing pointer sits just before the node to remove.
| Pattern | Two pointers a fixed gap apart |
|---|---|
| Time | O(n) |
| Space | O(1) |
Watch out for
A placeholder node before the head makes removing the first node a normal case.