Remove Nth Node From End of List

MediumLinked ListLinked ListTwo Pointers

Problem

You are given the head of a linked list and an integer n. Remove the node that sits n positions from the end of the list (counting the very last node as position 1) and return the resulting head. You may assume n is always a valid position within the list.

Example. In 1 -> 2 -> 3 -> 4 -> 5 with n = 2, the node two from the end is 4, so the result is 1 -> 2 -> 3 -> 5.

Key idea

The straightforward approach counts the total length of the list in one pass, then walks a second time to the node just before the one that needs removing. That works, but it touches the list twice. A single traversal is enough if two pointers are kept a fixed distance apart: advance a lead pointer n steps ahead before the trailing pointer starts moving at all, then move both forward together, one step at a time. Since the gap between them never changes, the moment the lead pointer runs off the end of the list, the trailing pointer sits exactly one node before the target, ready to unlink it by pointing its next past it.

Solution

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let lead: ListNode = dummy;

  for (let i = 0; i < n; i++) {
    lead = lead.next as ListNode; // advance lead n steps ahead first
  }

  let trail: ListNode = dummy;
  while (lead.next !== null) {
    lead = lead.next; // move both pointers, keeping the n-node gap fixed
    trail = trail.next as ListNode;
  }

  trail.next = trail.next!.next; // trail sits right before the target, so skip past it

  return dummy.next;
}

Complexity

  • Time: O(n). A single pass through the list, with only a fixed constant-size lead before both pointers move together.
  • Space: O(1). Just the two pointers, no auxiliary storage.

Watch out for

  • If the node to remove is the head itself, the trailing pointer has no valid predecessor; starting both pointers from a dummy node before the head sidesteps this case entirely.
  • Advancing the lead pointer exactly n times before starting the trailing pointer is easy to get off by one: check with a short list by hand.
  • The removed node's own next pointer becomes irrelevant once unlinked.

Pattern

This is the fixed-gap variant of the two-pointer technique: rather than searching for a value, the two pointers maintain a constant offset to locate a position relative to the list's end without ever knowing its length in advance.

Related questions