loading...
Cover image for Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List

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

alisabaj profile image Alisa Bajramovic ・5 min read

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

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.

Four images of the same linked list, `1 > 2 > 3 > 4 > 5`. In the first image, a blue `firstPointer` and a red `secondPointer` are both pointing the same space before the list starts. In the second image, `secondPointer` is in the same spot, but `firstPointer` is pointing at `1`. In the third image, `secondPointer` is at the same spot, and `firstPointer` is at `2`. In the final image, `firstPointer` is at `3`, and `secondPointer` is in the same spot.

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.

Three images of the same linked list as above. In the first image, `firstPointer` is on `4` and `secondPointer` is on `1`. In the second image, `firstPointer` is on `5`, and `secondPointer` is on `2`. In the third image `firstPointer` is on the empty space after the list (meaning 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.

The same linked list as above, except the node `4` has been removed. Now, a very long arrow stretches between `3` and `5`, and `secondPointer` is pointing at `5`.

What remains is 1 > 2 > 3 > 5, which is the given list with the 2nd node from the end removed.

--

Please let me know if you have any questions or other solutions to this problem!

Algorithm of the Day (40 Part Series)

1) The Happy Number Problem 2) Kadane's Algorithm & The Maximum Subarray Problem 3 ... 38 3) Finding the Only Single Number in an Array 4) Finding the Middle of a Linked List 5) Backspace String Comparisons: Two Ways To Approach a Common Algorithm 6) The Stock Span Problem: Using Stacks To Keep Track Of What's Been Seen 7) Finding the Kth Smallest Element: Walking Through How To Use Depth First Search on a Binary Search Tree 8) The Boyer-Moore Majority Vote Algorithm: Finding the Majority Element in an Array 9) Sorting Characters in a String By Their Frequency 10) Finding the Intersection of Two Arrays 11) Finding the Minimum Path Sum in a Grid with Dynamic Programming 12) Floyd's Tortoise and Hare Algorithm: Finding a Cycle in a Linked List 13) The Sieve of Eratosthenes: Counting the Number of Primes 14) Add Two Numbers Problems: How to Sum Two Linked Lists 15) The Longest Substring With No Repeating Characters 16) Merging Sorted Lists, Two Ways 17) Finding the Longest Common Prefix 18) Reversing a String in Place 19) The ZigZag Conversion Problem 20) The Longest Palindromic Substring: Solving the Problem Using Constant Space 21) Removing an Element in an Array In-Place 22) Solving the Best Time to Buy and Sell Stocks Problem in One Pass 23) Don't Underestimate the Two Pointers: Removing the N-th Node from the End of a Linked List 24) Not an "Easy" Algorithm: Rotating an Array, Three Ways 25) Sudoku Part I: Is the Board Valid? 26) Searching an Array, Two Ways 27) The Climbing Staircase Problem: How to Solve It, and Why the Fibonacci Numbers are Relevant 28) Transposing and Reversing: How to Rotate a 2D Matrix 90 Degrees 29) Turning 38 into 2: How to Solve the Add Digits Problem 30) The Gauss Sum, and Solving for the Missing Number 31) Is this Number the Sum of Two Square Integers? Solving The Sum of Squares Algorithm Two Ways 32) The Word Pattern Algorithm: How to Test if a String Follows a Pattern 33) Finding the Intersection of Two Arrays 34) Top Interview Question: Finding the First Unique Character in a String using Linear Time 35) Solving Pascal's Triangle in JavaScript 36) The Maximum Number of Events Problem 37) Solving Binary Tree Algorithms Using Recursion and Queues 38) From "hello world" to "world hello": Reversing the Words in a String 39) Finding the Most Frequent Elements in an Array 40) Finding the Angle Between the Hands of a Clock

Posted on by:

alisabaj profile

Alisa Bajramovic

@alisabaj

Hi! I'm a software engineer with a background in social history.

Discussion

markdown guide