Solution: Remove nth Node from End of List

Let's solve the Remove nth Node from End of List problem using the Two Pointers pattern.

We'll cover the following

Statement#

Given a singly linked list, remove the nthn^{th} node from the end of the list and return its head.

Constraints:

  • The number of nodes in the list is k.
  • 1≤1 \leq k ≤103\leq 10^3
  • −103≤-10^3 \le Node.value ≤103\le 10^3
  • 1≤1 \le n ≤\le k

Solution#

So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.

Naive approach#

The naive approach calculates the length of the linked list by traversing the complete list. Then, we set a pointer, say ptr, at the start of the list and move it through the list till it reaches the (k−n−1)th(k-n-1)^{th} node. The ptr pointer now points to the node before the target node, i.e., the nthn^{th} last node. Save the next node of the ptr in a temporary pointer. Relink the ptr node to the node following ptr ’s next node. Delete the node pointed by the temporary pointer. By doing so, the nthn^{th} last node will be removed. However, this approach traverses the linked list twice. Let’s see if we can use the two pointers pattern to implement our solution in a single pass.

Optimized approach using two pointers#

Two pointers, left and right, are set at the head node. Move the right pointer n steps forward. After doing that, both pointers are exactly separated by n nodes apart. Start moving both pointers forward until the right pointer reaches the last node. At this point, the left pointer will be pointing to the node before the target node, i.e., the nthn^{th} last node. We relink the left node to the node following the left’s next node.

If the right pointer reaches NULL while moving it n steps forward, it means that the head node should be removed. We return the head's next node.

Let’s look at the following illustration to get a better understanding of the solution:

Created with Fabric.js 3.6.6 right = 1left = 1 n = 3 Initially, both right and left pointers point to the head node of the linked list.

1 of 7

Created with Fabric.js 3.6.6 n = 3 right = 4left = 1 Move the right pointer n steps forward from the beginning.

2 of 7

Created with Fabric.js 3.6.6 n = 3 right = 5left = 2 Move the right and left pointers one step forward.

3 of 7

Created with Fabric.js 3.6.6 n = 3 right = 6left = 3 Move the right and left pointers one step forward.

4 of 7

Created with Fabric.js 3.6.6 n = 3 right = 7left = 4 Move the right and the left pointers one step forward. The right pointer has reached the lastnode. The left pointer has reached one node before the nth last node.

5 of 7

Created with Fabric.js 3.6.6 n = 3 right = 7left = 4 Relink the left node to the node next toleft's next node.

6 of 7

Created with Fabric.js 3.6.6 n = 3 right = 7left = 4 The 3rd last node (5) has been removed from the linked list.

7 of 7

Let’s have a look at the code for the algorithm we just discussed.

main.py
linked_list.py
linked_list_node.py
print_list.py
Remove Nth Node from End of List

Solution summary#

  1. Two pointers, right and left, are set at the head node.
  2. Move the right pointer n steps forward.
  3. If right reaches NULL, return head's next node.
  4. Move both right and left pointers forward till right reaches the last node.
  5. Relink the left node to the node at left's next to the next node.
  6. Return head.

Time complexity#

The time complexity is O(n)O(n), where nn is the number of nodes in the linked list.

Space complexity#

The space complexity is O(1)O(1) because we use constant space to store two pointers.

Remove nth Node from End of List

Fast and Slow Pointers: Introduction