LeetCode: Removing the nth Node from the End of a List

Removing the nth node from the end of a linked list is awkward because the list has no direct index and its length may not be known in advance. A two‑pointer gap turns that missing length into a position: when the leading pointer reaches the end, the other pointer is in the right place to remove the node.

At a glance, the problem might seem simple, but it has its complexities, not least because, unlike arrays, linked lists do not offer direct access to elements. This makes the seemingly straightforward task of removing an element based on its position from the end technically challenging. Moreover, optimising the algorithm to perform the manipulation in a single pass increases its complexity yet further.

I'll walk through two approaches: counting the nodes before removing one, and maintaining a gap between two pointers. Both take linear time and constant extra space. The second avoids a separate length‑counting pass, but is not automatically faster in every runtime.

The Problem

Given a non‑empty linked list, remove the nth node from the end and return its head. The problem guarantees an integer n from 1 to the list length, inclusive. The assertions in these examples rely on that valid‑input contract.

Examples

Input: 1 -> 2 -> 3 -> 4 -> 5, n = 2
Output: 1 -> 2 -> 3 -> 5

Input: 1, n = 1
Output: null

Input: 1 -> 2, n = 1
Output: 1

Simplest Solution: Two‑Pass Method

The easiest way to solve this is to make two passes through the entire list:

• The first pass is to find the length of the linked list.
• The second pass is to actually remove the node.

In TypeScript

Here's what that looks like in code:

type ListNode = {
  val: number;
  next: ListNode | null;
};

const removeNthFromEnd = (
  head: ListNode | null,
  n: number
): ListNode | null => {
  const dummy: ListNode = { val: 0, next: head };
  let length = 0;
  let first = head;

  while (first !== null) {
    length++;
    first = first.next;
  }

  length -= n;
  first = dummy;

  while (length > 0) {
    length--;
    first = first.next!;
  }

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

How It Works

1. ListNode, defines the type we'll be working with. It has a val field for the value and a next field for pointing to the next node in the list.
2. Our function removeNthFromEnd takes a head node and an integer n.
3. We create a dummy node which precedes the head node. This is useful for edge cases such as when there's only one node in the list.
4. We pass through the list to calculate its length.
5. We move the first pointer to just before the node to be removed.
6. Finally, we remove the node by updating the next pointer of the node preceding the one to be removed.

Solving the Problem in a Single Pass

The one‑pass method maintains a gap between two pointers instead of first calculating the length. Both approaches are O(L) time and O(1) auxiliary space for a list of length L; the gap is a different way to find the position, rather than a change in asymptotic complexity.

The Code

The code to solve this problem in a single pass looks a little like this:

const removeNthFromEndOnePass = (
  head: ListNode | null,
  n: number
): ListNode | null => {
  const dummy: ListNode = { val: 0, next: head };
  let first: ListNode | null = dummy;
  let second = dummy;

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

  while (first !== null) {
    first = first.next;
    second = second.next!;
  }

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

How It Works

1. Initially, both pointers (first and second) are set to the dummy node.
2. Advance first by n + 1 links whilst second stays at the dummy node.
3. Then, both pointers are moved one step at a time until the first pointer reaches the end of the list (null).
4. That n + 1‑link lead places second immediately before the target when first reaches null.
5. You can then change the next reference of the node preceding the target node to point to the node after the target node, effectively removing it.

Conclusion

Start first and second at the dummy node, advance first by n + 1 steps, then move both pointers until first is null. That leaves second immediately before the node to remove. When the original head is removed, including from a single‑node list, second remains at the dummy node and dummy.next is the correct new head.