LeetCode problem #19–Remove nth node from end of list (JavaScript)

In this LeetCode challenge, we’re given a LinkedList, and asked to remove the nth-from-last node (where n is supplied, alongside the LinkedList, to our function).

The biggest issue here is that we don’t know the length of the LinkedList, so finding length — n is currently impossible. This means our first course of action is to find the length, so that we can find length-n, and then remove that node.

Note #1: With the provided implementation, you cannot delete a ListNode as such. What you must do instead is to point the ListNode that comes before it, to the ListNode that comes after it (or to null if there is no ListNode after it). This effectively deletes the target node.

Note #2: Both of the below solutions create a dummy ListNode entry at the start of the LinkedList. This is because it allows us to easily skip over the first node in the list with the same logic as we use elsewhere. Otherwise, we would have to use eparate logic to handle cases where the first node in the LinkedList is the one being removed, which would complicate and expand the code.

Solution #1: Double loop

This solution does what probably came to your mind first. To begin with, we traverse the LinkedList until we reach its end, which gives us the length of the LinkedList. Then, we traverse it once more, this time stopping when we get to the node right before our target node. Finally, we point the next value of the node before our target one, to the node after our target one, effectively removing our target node from the list.

Solution #2: Single loop

One of the potential complexities listed on the page for this problem is to find a way to do this with one loop, so here’s how.

We start by initialising two pointers; a fast and a slow. We then move the fast into the LinkedList n times. Next, we move both pointers forwards into the list until the fast pointer reaches the end. By doing this, we have effectively moved the slow pointer to length-n without ever knowing what the length of the LinkedList actually was, and by using only a single full loop (split into 2 partial loops).

From here we can apply the same logic as before, by pointing the element preceding our target one to the one that follows it, effectively deleting our target element out of the LinkedList.