Posted on Jun 11, 2020

Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List

#javascript #codenewbie #leetcode #algorithms

Today's algorithm is Remove Nth Node From End of List:

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

For example, if the linked list were 1 > 2 > 3 > 4 > 5, and n = 2, you should return a list with the second node from the end removed, so 1 > 2 > 3 > 5.

In this post, I'll be discussing my approach to this problem, which is to have two pointers running at the same time. I'll then go over how to code the solution using JavaScript, followed by an example.

Two Pointers to the Rescue

In linked list problems, two pointers are often a great way to approach the algorithm. The idea behind two pointers is that when one reaches the end of a linked list, the other will be at an important point in the list (you can see another example of using two pointers in a linked list in this algorithm).

In this problem, the way to use two pointers is to have them be n steps apart from each other. That way, when the first pointer gets to the end of the linked list, the second pointer will be on the node that is to be removed from the list.

The important thing to remember about singly linked lists is that you can only move in one direction--from the head to the tail. That's why two pointers are so useful: you can keep track of two different points in the list at once.

For this algorithm, I'll create two pointers. Once the first pointer is n steps ahead from the head of the list, the second pointer will start. Then, the pointers will continue incrementing, one node at a time, until the first pointer reaches the end of the list (as in, when its value is null). When that happens, the second pointer will skip over the next node, because that one is n steps from the end of the list.

Coding the Solution

The first thing to do will be to create a new list, which will essentially be a copy of the inputted list, but won't include the node to be removed. Since the algorithm provides a definition for a singly linked list, in this function we can create a new list with new ListNode(0), and set it equal to the head of the inputted list.

function removeNthFromEnd(head, n) {
  let copy = new ListNode(0);
  copy.next = head;
  //...
}

Then, we'll want to create two pointers, firstPointer and secondPointer. We'll initialize them at the start of the list copy.

function removeNthFromEnd(head, n) {
  let copy = new ListNode(0);
  copy.next = head;
  let firstPointer = copy;
  let secondPointer = copy;
  //...
}

Now, we want to keep moving the first pointer through 'copy' until it reaches n + 1. To do this, we could use either a for loop or a while loop--just for fun, we'll use a while loop! So, we can create a counter, set it equal to 0, and until the counter reaches n + 1, we'll move firstPointer on to each next node.

function removeNthFromEnd(head, n) {
  let copy = new ListNode(0);
  copy.next = head;
  let firstPointer = copy;
  let secondPointer = copy;
  let counter = 0;
  while (counter < n + 1) {
     firstPointer = firstPointer.next;
     counter++;
  }
  //...
}

At this point, we'll want to increment both the first pointer and the second pointer, one node at a time, until the first pointer reaches the end of the list. We know firstPointer is at the end of the list when its value is equal to null, so we can create a while loop that keeps going as long as the value is not null.

function removeNthFromEnd(head, n) {
  let copy = new ListNode(0);
  copy.next = head;
  let firstPointer = copy;
  let secondPointer = copy;
  let counter = 0;
  while (counter < n + 1) {
     firstPointer = firstPointer.next;
     counter++;
  }
  while (firstPointer !== null) {
    secondPointer = secondPointer.next;
    firstPointer = firstPointer.next;
  }
  //...
}

When the while loop stops executing, we know the first pointer is at the end of the list, which means the second pointer is on the node that's n from the end, so we should skip over it. To skip over it, we can set secondPointer.next equal to secondPointer.next.next.

Finally, we'll want to return the list copy, and in order to do so we'll return copy.next.

function removeNthFromEnd(head, n) {
  let copy = new ListNode(0);
  copy.next = head;
  let firstPointer = copy;
  let secondPointer = copy;
  let counter = 0;
  while (counter < n + 1) {
     firstPointer = firstPointer.next;
     counter++;
  }
  while (firstPointer !== null) {
    secondPointer = secondPointer.next;
    firstPointer = firstPointer.next;
  }
  secondPointer.next = secondPointer.next.next;
  return copy.next;
}

Going Through an Example

Let's use the same example of the list being 1 > 2 > 3 > 4 > 5, and n = 2. That means that in the end, we'll want to return the list 1 > 2 > 3 > 5.

We'll start with both firstPointer and secondPointer pointing at the node 0. When we start, the counter will be 0, and n+1 is 3, so we'll keep moving the firstPointer onto the next node (without moving the secondPointer) until n = 3. So, after the first time in the while loop, firstPointer is at 1. Then firstPointer is at 2. Then firstPointer is at 3, which is the last time that firstPointer will move without secondPointer.

At this point, counter is no longer less than n + 1, so we'll start moving secondPointer as well as firstPointer, and we'll keep doing this until firstPointer is null. So firstPointer is now on 4 and secondPointer is on 1. Then, firstPointer is on 5 and secondPointer is on 2. Finally, firstPointer is null, and secondPointer is on 3.

Because firstPointer is null, the next node for the secondPointer is the node we're skipping over. That means that after 3, second pointer will go straight to 5.