Remove Nth Node From End of List

Problem

Given the head of a linked list, remove the nth node from the end of the list and return the head.

Approach

Use two pointers that start at a dummy node placed before the head. Move the fast pointer n + 1 steps ahead first.

Then move both pointers together until the fast pointer runs off the end. The slow pointer now sits just before the node to remove, so relinking its next pointer removes it.

The dummy node handles the case where the node to remove is the head itself.

Solution

class Solution:
    def removeNthFromEnd(self, head: ListNode | None, n: int) -> ListNode | None:
        dummy = ListNode(0, head)
        fast = slow = dummy

        for _ in range(n + 1):
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next

        slow.next = slow.next.next
        return dummy.next

Complexity

• Time: O(L), where L is the length of the list, in a single pass.
• Space: O(1).

Edge cases

• Removing the only node returns an empty list.
• Removing the head works because of the dummy node.
• n always refers to a node that exists, per the constraints.