Description
Remove the nth node from the end of a list, where 1 <= n <= list length.
Solution
def remove_nth_from_end(head, n):
dummy = ListNode(0, head)
fast = slow = dummy
for _ in range(n):
fast = fast.next
while fast.next:
fast, slow = fast.next, slow.next
slow.next = slow.next.next
return dummy.nextExamples
Inputs are positional arguments. Trees use level-order arrays; linked lists use value arrays. Design problems list operations in order.
Example 1
- Input
[[1,2,3],2]- Output
[1,3]
The second node from the end contains 2.
Example 2
- Input
[[1],1]- Output
[]
Removing the only node leaves an empty list.
Example 3
- Input
[[1,2],2]- Output
[2]
The head is second from the end.
Approach
Place two pointers n nodes apart from a dummy head, then advance until the leading pointer reaches the tail.
Time & space
O(n) time; O(1) space, using n here for list length.