Remove Nth Node From End

The problem

Given the head of a linked list, remove the n-th node from the end and return the head.

Input:  1→2→3→4→5, n = 2
Output: 1→2→3→5

Input:  1, n = 1
Output: empty

Node shape

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

Brute force: two pass

Count length L, remove node at index L - n from start.

function removeNthFromEndTwoPass(head: ListNode | null, n: number): ListNode | null {
  let len = 0;
  let cur = head;
  while (cur) {
    len++;
    cur = cur.next;
  }
  const dummy = new ListNode(0, head);
  cur = dummy;
  for (let i = 0; i < len - n; i++) cur = cur!.next;
  cur!.next = cur!.next!.next;
  return dummy.next;
}

Time	O(L)
Space	O(1)

Optimal: one pass two pointers

Advance fast by n+1 from dummy (or n then move both). When fast hits null, slow is just before the victim.

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

  for (let i = 0; i < n + 1; i++) {
    fast = fast!.next;
  }

  while (fast) {
    fast = fast.next;
    slow = slow!.next;
  }

  slow!.next = slow!.next!.next;
  return dummy.next;
}

Time	O(L) one pass
Space	O(1)

Dummy handles deleting the original head cleanly.

Edge cases

• Remove head (n = length)
• Remove tail (n = 1)
• Single node list
• n always valid per constraints — still write safely

Common bugs

• Off-by-one gap between fast and slow
• No dummy → messy head delete
• Returning old head after deleting head

Interview delivery

1. Two-pass count is fine; offer one-pass.
2. Dummy + gap of n.
3. Relink.
4. Trace remove head and remove middle.
5. O(L)/O(1).

Related

• Reverse Linked List
• Merge Two Sorted Lists
• Reorder List
• Linked List Cycle

Gap intuition

If you want slow at the node before the delete target when fast hits null, fast should start n+1 steps ahead of slow from the dummy. Example length 5, n=2: delete node 4; slow should land on node 3.

Two-pass still OK

Many interviewers accept count-then-delete. One-pass is a nice upgrade if you have time. Lead with two-pass if you feel shaky on the gap, then offer the upgrade.

Memory safety

In GC languages you just drop references. Mention that in C++ you’d delete the node — shows systems awareness without derailing.

Further reading

• LeetCode 19 — Remove Nth Node From End of List
• Two pointers technique