Remove Nth Node From End of List

Intuition

Removing a node requires standing on the node right before it so we can rewire the next pointer. To find that predecessor in one pass, open a gap of n + 1 nodes between a fast and a slow pointer. When the fast pointer walks off the end, the slow pointer is precisely one node ahead of the one we need to delete. A dummy node placed before the head removes the special case of deleting the very first node, since the dummy always has a valid predecessor. We then unlink the target and return the node after the dummy.

Algorithm walkthrough

1. 1Create a dummy node whose next points to head, and set both slow and fast to the dummy.
2. 2Advance fast by n + 1 steps so the gap between fast and slow is exactly n + 1.
3. 3Move slow and fast together, one node at a time, until fast becomes null.
4. 4Now slow sits just before the node to delete; set slow.next to slow.next.next to skip it.
5. 5Return dummy.next as the new head of the list.

Implementation

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        slow = fast = dummy
        for _ in range(n + 1):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
        slow.next = slow.next.next
        return dummy.next