medium

Remove Nth Node From End of List

Remove the nth node from the end of a linked list in one pass using two pointers.

1. Define the problem

Remove Nth Node From End of List

Given the values of a singly linked list, remove the nth node from the end of the list and return its values, in order. Use two pointers with a gap of n between them: advance a lead pointer n steps ahead first , then move both pointers together until the lead pointer reaches the end — the trailing pointer then sits just before the node to remove.

Constraints

  • The number of nodes in the list is sz.
  • 1 ≤ sz ≤ 30
  • 0 ≤ valuesi ≤ 100
  • 1 ≤ n ≤ sz

Example

Inputvalues = [1, 2, 3, 4, 5], n = 2
Output[1, 2, 3, 5]

Explanation The 2nd node from the end (value 4) is removed, leaving [1, 2, 3, 5].

2. Know the words first

In plain terms

Linked list
A chain of nodes where each node just points to the next one, unlike an array where all the values sit together in one contiguous block.
3. Visualize the solution

Two pointers keep a fixed gap of n

Two pointers keep a fixed gap of n
Statusinit

Start trail at index 0, lead at index 2 — a fixed gap of n=2 nodes apart.

What happens in this step

trail = 0, lead = n = 2
  values = [1, 2, 3, 4, 5]

lead is advanced n steps ahead FIRST, before trail moves at all. That
fixed gap of n is what makes trail land exactly n nodes back from
wherever lead ends up.
Step 1 of 5

Steps to visualize

  1. Advance the lead pointer n steps ahead of the trailing pointer before either one starts moving together.
  2. Move both pointers one step at a time until the lead pointer reaches the last node.
  3. The trailing pointer is now just before the node that needs to be removed.
  4. Unlink that node by pointing the trailing node past it.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Two pointers keep a fixed gap of n
Statusinit

Start trail at index 0, lead at index 2 — a fixed gap of n=2 nodes apart.

What happens in this step

trail = 0, lead = n = 2
  values = [1, 2, 3, 4, 5]

lead is advanced n steps ahead FIRST, before trail moves at all. That
fixed gap of n is what makes trail land exactly n nodes back from
wherever lead ends up.
Step 1 of 5
5. Solution

Solution

solution.tsTypeScript
function removeNthFromEnd(values, n) {
  const dummy = { val: 0, next: null };
  let node = dummy;
  for (const val of values) {
    node.next = { val, next: null };
    node = node.next;
  }

  let lead = dummy;
  for (let i = 0; i < n; i++) {
    lead = lead.next;
  }

  let trail = dummy;
  while (lead.next !== null) {
    lead = lead.next;
    trail = trail.next;
  }

  trail.next = trail.next.next;

  const result = [];
  let current = dummy.next;
  while (current !== null) {
    result.push(current.val);
    current = current.next;
  }

  return result;
}
Time
O(n)
Space
O(1) (excluding the constructed list and result array)
6. Test cases

Test cases

InputExpectedCovers
values = [1, 2, 3, 4, 5], n = 2[1, 2, 3, 5]example from the docstring
values = [1, 2, 3], n = 3[2, 3]n equals the list length, removing the head
values = [1], n = 1[]a single-element list, result is empty
values = [1, 2, 3, 4, 5], n = 1[1, 2, 3, 4]removing the tail node
values = [1, 2], n = 2[2]smallest list where the head is removed
values = [7, 7, 7, 7], n = 3[7, 7, 7]every node holding the same value

Keep reading