Remove nth to Last Element in a Linked List (Javascript)

One thing I’ve noticed the more I’ve been doing practice algorithms is the power of pointers. This is especially true in linked list algorithms.

In this post I’ll be sharing a really intuitive approach to a common linked list problem, Remove Nth Node from End of List (this is problem #19 on Leetcode and can also be found at the end of chapter 2 of Cracking the Coding Interview).

The problem statement reads:

Given the head of a linked list, remove the nth node from the end of the list and return its head.

image from leetcode

With the follow up question: Could you do this in one pass?

You’ll see with a 2 pointer approach this is actually quite simple to do.

A linked list consists of nodes where each node contains a data field and a reference to the next node in the list. This can be seen in the above picture with the references represented by arrows connecting each node. In this case the value/ data in each node is the number shown.

For this problem, we’re given the following definition for the nodes of the list:

function ListNode(val, next) {
   this.val = (val===undefined ? 0 : val)
   this.next = (next===undefined ? null : next)
}

So for the head node of the linked list pictured above, this.val would be 1 and this.next would be the node with the value 2.

As inputs for the problem we’re given the head of the linked list, and the number n telling us the nth node from the end of the list we want to remove (for example if n = 2, we want to remove the second to the last node in the list).

Here are steps to solve this problem using 2 pointers, followed by the code in Javascript. This method allows us to solve the problem in 1 pass:

• First assign your first pointer to the head of the linked list (I’ll be calling the first pointer p1 and the second pointer p2). As an initial check you can see if head.next is null. If this is the case, you can simply return head.next, or in other words, an empty result, since there is only one node to be removed.
• Next, assign your second pointer p2 to be n nodes ahead of p1. In the code below I use a helper function called offsetPointer to do this.
• After that, we will simply advance both our nodes forward using a while loop where the condition is while p2 is not null and p2.next is not null advance p1 and p2 by 1 node each iteration of the loop. To advance the nodes we call p1.next and p2.next within the loop. The reason we use these conditions is that we will know we have reached the end of our linked list when the value after p2 is null.
• Once we find our last node with p2, we know that the next node after p1 is the one we want to remove. Since we initially started our p2 pointer n nodes away from our head node, we know that when p2 reaches the node before the last node in the list, p1 has reached the node before the nth to last element.
• As a result, once our while loop is ended, we know that we want to remove p1.next. So how do we do this? Simply by hopping over it (or that’s how I visualize it anyway). After the while loop is done, simply set p1.next to equal p1.next.next. This will effectively skip over p1.next, thus connecting p1 to the node after p1.next.
• After that, we simply return the head of our linked list with the now removed nth to last element!

Code below:

The above code beats the runtime of 98–99% of Javascript submissions on Leetcode. You can see in the above that with a linked list especially, pointers can be a really handy and intuitive way to approach a problem.

Similar logic can be applied to many linked list problems. For example, for removing the middle node of a linked list you can use a slow pointer advancing by 1 node per loop and fast pointer advancing by 2 nodes per loop, and when the fast pointer gets to the end of the list, you know the middle pointer has found the middle of the list.

Hope this helps!