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

Linked lists are a foundational topic in computer science, often appearing in technical interviews and real‑world applications. The problem of removing the Nth node from the end of a linked list is a common one; mastering it will not only help you perform well in interviews but also provide a deeper understanding of list manipulation techniques.

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 do the manipulation it in a single pass increases its complexity yet further.

In this article, I intend to discuss two approaches: a straightforward double‑pass method, which gets the job done, and a more advanced (complex), but efficient single‑pass strategy. As always, I'm a front‑end developer, so we'll be using front‑end code here...

The Problem

Given a linked list, remove the Nth node from the end of the list and return its head. It is given that n will be valid, so it will always be smaller than or equal to the length of the list.

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

Unlike the two‑pass method, the one‑pass method solves the problem with a single traversal of the linked list (using two pointers), which in turn makes it more time‑efficient.

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 = new ListNode(0);  dummy.next = head;  let first = 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 head of the list.
2. The first pointer is advanced n+1 steps ahead, whilst the second pointer stays at the head.
3. Then, both pointers are moved one step at a time until the first pointer reaches the end of the list (null).
4. Because there's a gap of n nodes between the first and second pointers, the second pointer will be positioned just before the node that needs to be removed when the first pointer reaches the end.
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

Removing the Nth node from the end of a linked list is a useful exercise for understanding list manipulation and pointer use. Using one or two‑pass solutions provide different trade‑offs between simplicity and efficiency.