Remove Nth Node From End | Two Pointers | Linked List

Overview

Remove the nth node from the end means deleting the node that is n steps from the tail (1-based: the last node is "1st from end"). Doing it in one pass and O(1) space requires two pointers: advance one pointer n steps (or n+1) ahead, then move both until the leading pointer reaches the end; the trailing pointer is then just before the node to remove. A dummy head simplifies the case when the node to remove is the head.

Key idea: The nth-from-end node is (length - n) steps from the head. Instead of computing length, use a gap of n (or n+1) between two pointers so that when the front hits the end, the back is at the right place.

When to Use

Remove nth from end — classic one-pass problem.
Any "kth from end" — same two-pointer gap technique.
Find nth from end without deleting — same gap; then read the node (or its predecessor).

How It Works

Use a dummy so the node before the head exists: dummy.next = head.
Move fast (n+1) steps from the dummy so that when fast is at the end (null), slow is the predecessor of the nth-from-end node.
Set slow.next = slow.next.next to remove the node.
Return dummy.next (handles removal of the original head).

Why n+1? We want slow to land on the predecessor of the node to delete. If we put fast exactly n steps ahead and move until fast is at the last node, slow is (n+1) nodes behind the last, i.e. at the predecessor of the nth-from-end node. So: advance fast (n+1) times from dummy, then move both until fast is null; slow is the predecessor.

Example 1: Remove Nth From End (One Pass)

Problem: Given the head and n, remove the nth node from the end and return the head. Assume n is valid.

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dummy = new ListNode(-1);
  dummy.next = head;
  let fast: ListNode | null = dummy;
  let slow: ListNode | null = dummy;
  for (let i = 0; i <= n && fast !== null; i++) {
    fast = fast.next;
  }
  while (fast !== null) {
    fast = fast.next;
    slow = slow!.next;
  }
  if (slow?.next != null) {
    slow.next = slow.next!.next;
  }
  return dummy.next;
}

Time: O(n), Space: O(1).

Example 2: Two Pass (Length First)

First pass: compute length L. Second pass: go (L - n) steps from head and remove the next node. Needs dummy for L === n (remove head).

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

Edge Cases

Remove the head — n = length; slow stays at dummy, so dummy.next is updated correctly.
Single node, n = 1 — After loop, slow is dummy, remove the only node; return null.
Two nodes, remove second — n = 1; slow at first node, remove second; fine.
Two nodes, remove first — n = 2; slow at dummy, remove head; return second node.

Common Mistakes

Off-by-one — Use n+1 steps for fast so slow ends at the predecessor of the nth-from-end node.
Not using dummy — When the node to remove is the head, you need a predecessor; dummy provides it.
Assuming n is valid — Problem often states n is valid; if not, add a check that fast doesn't go past the end before the main loop.

Time and Space Complexity

Time: O(n) one pass (or O(n) two pass).
Space: O(1).

Summary

Remove nth from end: dummy + two pointers; advance fast (n+1) steps, then move both until fast is null; delete slow.next; return dummy.next.
See Dummy Head for why we use a dummy and Fast and Slow Pointers for the two-pointer pattern.