Remove Nth Node From End

Remove the nth node counted from the end.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Remove Nth Node From End: Maintain a two-node gap so left stops immediately before the second node from the end.

Input and goalRemove the `n`th node counted from the end.

Start both pointers at the dummyA dummy points to 1, so removing the head would use the same link update. Both left and right start at dummy.

dummyleft→1→2→3→4→5

inputhead=[1,2,3,4,5], n=2rightdummygap0 nodes

Recognize it

The node is identified relative to the list end, but only one forward pass is allowed, so a leading pointer can convert distance-from-end into a simultaneous stopping position.

Keep true

After the initial advance, right remains exactly n links ahead of left. Therefore, when right is the tail, left.next is the nth node from the end.

Reuse it

Use a fixed lead whenever a linked-list target is defined by distance from the end; add a dummy when the operation may change the head.

Pattern: Two pointers with a fixed gap.

Simple idea: Move right ahead by n nodes. Then move both pointers together. When right reaches the end, left is just before the node to remove. A dummy node handles removing the head without a special case.

def remove_nth_from_end(head: ListNode | None, n: int) -> ListNode | None:
   dummy = ListNode(0, head)
   left = dummy
   right = dummy

   for _ in range(n):
      if right.next is None:
         return head
      right = right.next

   while right.next:
      left = left.next
      right = right.next

   if left.next:
      left.next = left.next.next
   return dummy.next

Cost: $O(n)$ time and $O(1)$ space.

The platform supplies ListNode with val and next; this snippet assumes that definition.