Remove Nth Node from End of List

Prompt

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

Example 1

Input: head = [1, 2, 3, 4, 5], n = 2

Output: [1, 2, 3, 5]

Example 2

Input: head = [1], n = 1

Output: []

Example 3

Input: head = [1, 2], n = 1

Output: [1]

Stating the Problem in My Own Words

For this problem we'll be given the Linked List with access to the list's head, and a value n. n is the place from the end of the list that we will find the node that we want to remove. If n is 1, then we are removing the tail, or the last item in the list. If n is 2, then we're removing the item right before the tail. If n is 3, we're removing the third item from the end of the list.

It's worth noting a major difference between this Linked List implementation, and the one I implemented a couple of blog posts back, which is that this Linked List does not track its tail, length, or provide any way to access by index. Basically, we can access the list starting at its head, and we need to write a way to iterate up to the item we want to remove, as well as write its removal.

Approach: Two Pointers

If you've followed my Linked List posts up to this point, iterating up through a Linked List using a while loop or a for Loop should be familiar. The difficulty with this problem is figuring out how to iterate up to n items from the end of the list.

To do that we're going to use two pointers that move through the Linked List. The first pointer, called fast, will move n places up in the list. Then the second pointer, called slow, will start moving up the list. They will move at the same rate, with slow being n places behind fast, until fast reaches the last item in the list. At this point, iteration stops, and slow will be n + 1 places from the end of the list, meaning it has found the node where we reassign its next pointer reference, and can delete the node that comes after it from the list.

I'll show you how this works. Let's say that this is our list:

[1, 2, 3, 4, 5]

Or, shown with its pointers:

1 -> 2 -> 3 -> 4 -> 5

Let's also say that n is 2, so we're looking to remove the second item from the end.

The first thing we want to do is create a variable called fast, initially set to equal the head, which will loop n times through the list.

function removeNthFromEnd(head, n) {  let fast = head;
  for (let i = 0; i < n; i += 1) {    fast = fast.next;  }}

The code above iterates fast up to the nth item in the list. Let's visualize this:

The f will represent the fast node.

First for Loop Iteration:

i = 0n = 21 -> 2 -> 3 -> 4 -> 5f

Second for Loop Iteration:

i = 1n = 21 -> 2 -> 3 -> 4 -> 5     f

Third for Loop Iteration:

i = 2n = 21 -> 2 -> 3 -> 4 -> 5          f

This is where our for Loop ends. Now we'll also introduce a variable called slow, which we will also have set as the head.

With fast at the third item in the list, we're now going to start a while loop that runs as long as there is a fast.next. Each time that condition is met, we'll reassign fast to be fast.next and slow to be slow.next. This loop stops running when there's no longer a fast.next, meaning fast stops on the tail, and slow, which is n items behind fast, is at the item right before the nth item from the end of the list.

function removeNthFromEnd(head, n) {  let fast = head;  let slow = head;
  for (let i = 0; i < n; i += 1) {    fast = fast.next;  }
  while (fast.next) {    fast = fast.next;    slow = slow.next;  }}

Once again let's visualize what's going on. We can get rid of i since we're no longer working with the for Loop. We still have f to represent the fast node, and now our slow node is represented by s.

Here is where we left off before our our while Loop started iterating:

n = 21 -> 2 -> 3 -> 4 -> 5s         f

First while Loop Iteration:

n = 21 -> 2 -> 3 -> 4 -> 5     s         f

Second while Loop Iteration:

n = 21 -> 2 -> 3 -> 4 -> 5          s         f

At this point, there is no fast.next, so the while Loop stops running. fast is on the last node of the list, and slow is on the third-to-last node of the list.

This is exactly where we want to be. In order to delete the nth node from the end, we need to reassign slow.next to equal slow.next.next. In essence, we are telling 3 to point to 5, removing 4 from the list:

1 -> 2 -> 3 -> 5

With the slow node's next reassigned, our list is basically where it needs to be, so all we need to do is return head, which gives us the adjusted list.

function removeNthFromEnd(head, n) {  let fast = head;  let slow = head;
  for (let i = 0; i < n; i += 1) {    fast = fast.next;  }
  while (fast.next) {    fast = fast.next;    slow = slow.next;  }
  slow.next = slow.next.next;  return head;}

Edge Case: Removing the head

So we're well on our way to a good solution, but we need to account for an edge case that we run into in Example 2, in which n is the same length as the list. Basically this means that we're deleting the head. As it currently stands, the for Loop will iterate through the entire list, leaving fast as the last item in the list. When the while Loop starts, there is no fast.next, so the while Loop throws an error.

To address this, we need to just put in a little check after our for Loop. After the first loop runs, if fast has been reassigned to a null value, then all we need to do is return head.next, giving us the list with its head removed, which is what we're looking for.

Here is the full solution with comments for each section:

function removeNthFromEnd(head, n) {  // initialize our fast and slow variables to equal the head  let fast = head;  let slow = head;
  // Loop fast up to the nth item in the list  for (let i = 0; i < n; i += 1) {    fast = fast.next;  }
  // Check whether fast is currently at the end of the list  // If so, we are just removing the head,  // so return the list without its head  if (!fast) {    return head.next;  }
  // Loop both fast and slow up, with fast being n items ahead of slow  // until fast is at the end of the list  // and slow is n + 1 items from the end of the list  while (fast.next) {    fast = fast.next;    slow = slow.next;  }
  // Reassign slow.next to be slow.next.next,  // in essence removing the nth-from-the-end item  slow.next = slow.next.next;
  // Return the list with the item removed  return head;}

Solution

function removeNthFromEnd(head, n) {  let fast = head;  let slow = head;
  for (let i = 0; i < n; i += 1) {    fast = fast.next;  }
  if (!fast) {    return head.next;  }
  while (fast.next) {    fast = fast.next;    slow = slow.next;  }
  slow.next = slow.next.next;  return head;}

Big O of this Solution and Further Optimization

Since we're only iterating once through the list (though with two pointers), our time complexity is O(n), where n is the length of the Linked List. Since we're not creating a new Linked List or anything other than two pointers, this solution will always be in constant space, O(1).

One last thing I might look into to optimize is making sure that the removed node doesn't present a false head for the Linked List. As it currently stands, the 4 node may still have a next pointer that refers to the 5 node. To eliminate this, I might store it in a variable named temp or removedNode or something, then after reassigning slow.next, assign removedNode.next to equal null.

let removedNode = slow.next;slow.next = slow.next.next;removedNode.next = null;return head;

This way, even if someone accessed the removed node with the value 4, that node would not point back into the list itself.

I'll admit this isn't my favorite solution, and it's mostly written to account for the oddities of the way that LeetCode does its Linked Lists. Again, with my own Linked List implementation I would go about this an entirely different way.