Remove nth node from the end
We'll cover the following
Remove the nth node counting from the end, in one pass over the list.
Watch it run
Press Play or Step to walk through the example, or change the input and press Run. Each frame says what the algorithm does and why.
40
91
22
73
54
15
86
37
68
109
1210
1111
1412
1313
Remove the 4th node from the end in one pass. Both pointers start before the head. Move fast 4 steps ahead first.
1 / 16
The idea
Complexity
| Time | Space | Why |
|---|---|---|
O(n) | O(1) | One pass with a fixed gap between the pointers. |
In Python
def remove_nth(head, n):
dummy = ListNode(0, head)
slow = fast = dummy
for _ in range(n): fast = fast.next
while fast.next:
slow, fast = slow.next, fast.next
slow.next = slow.next.next
return dummy.nextSummary: say it in the interview
- You do not know the length, so move fast n steps first. Then move both until fast hits the end. The gap of n means slow is exactly one node before the one to remove.
- Time O(n), space O(1). One pass with a fixed gap between the pointers.