Remove Nth Node From End of List

Try It Yourself

Use the editor below to remove a node counted from the end without first measuring the list. Create a gap of n nodes between two pointers.

Submit your implementation when it passes the examples. The removed node may be the head, the tail, or the only node.

Remove Nth Node From End of List

mediumLinked List · Two Pointers30 minLC 19

Problem

Given the head of a singly linked list and an integer n, remove the nth node counted from the end.

Return the list's head after the removal. Each node has the shape { val, next }.

Example 1:

Input: head = [1, 2, 3, 4, 5], n = 2

Output: [1, 2, 3, 5]

Example 2:

Input: head = [1], n = 1

Output: []

Constraints

1 ≤ n ≤ number of nodes ≤ 30
The list contains at least one node.

0 attempts

Solution

A dummy node before the head makes removing the first real node identical to every other removal. Advance fast n steps, then move fast and slow together until fast reaches the tail.

At that moment, slow.next is the node to remove. Skip it by connecting slow.next to the following node.

function removeNthFromEnd(head, n) {
  const dummy = { val: 0, next: head };
  let fast = dummy;
  let slow = dummy;

  for (let step = 0; step < n; step++) {
    fast = fast.next;
  }

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

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

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	The fast and slow pointers each move through the list at most once.
Auxiliary space	`O(1)`	The algorithm uses one dummy node and two pointers.