Given the head of a linked list and an integer n, remove the n-th node counted from the end of the list and return the head of the updated list. Try to do it in a single pass.
- The list has `sz` nodes, 1 <= sz <= 30
- 0 <= Node.val <= 100
- 1 <= n <= sz
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The two pass solution finds the length first and then walks to the node before the target. To do it in one pass, keep two pointers exactly n + 1 nodes apart. When the leading pointer falls off the end, the trailing pointer sits just before the node to remove, so we can unlink it with slow.next = slow.next.next. A dummy node in front of head handles the case where the head itself is removed, with no special code.
Algorithm
- Create
dummywithdummy.next = head. Setslow = fast = dummy. - Move
fastforwardn + 1times. - Move
slowandfasttogether untilfastis null. - Unlink the target:
slow.next = slow.next.next. - Return
dummy.next.
O(L), one pass over the listSpace: O(1)n == length (removing the head) crashes many solutions. Always test head = [1], n = 1 and head = [1,2], n = 2.class Solution: def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]: dummy = ListNode(0, head) # handles removing the head slow = fast = dummy for _ in range(n + 1): fast = fast.next # gap of n + 1 nodes while fast: slow = slow.next fast = fast.next slow.next = slow.next.next # unlink the target return dummy.next