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\le k ≤103\le 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

The essence of this algorithm is its efficient use of two pointers to locate and remove the nthn^{th} node from the end of a linked list in just one pass. Initially pointing both pointers at the head and advancing one of them to nn steps ahead. Next, we simultaneously move both pointers until the pointer ahead reaches the end, ensuring they maintain a constant gap between them. The first pointer will be pointing to the nth−1n^{th}-1 node from the end, setting its next pointer to the nth+1n^{th}+1 node will effectively remove nthn^{th} node from the list. In this one-pass algorithm, we don’t need an initial pass to determine the length of the list.

Now, let’s look at the workflow of the implementation:

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 point 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, 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:

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

RemoveNthLastNode.java
LinkedList.java
LinkedListNode.java
PrintList.java
import java.util.*;
class RemoveNthNode {
  public static LinkedListNode removeNthLastNode(LinkedListNode head, int n) {
    LinkedListNode right = head;
    LinkedListNode left = head;
    for (int i = 0; i < n; i++) {
      right = right.next;
    }
    if (right == null) {
      return head.next;
    }
    while (right.next != null) {
      right = right.next;
      left = left.next;
    }
    left.next = left.next.next;
    return head;
  }
  // Driver Code
  public static void main(String[] args) {
    int[][] inputs = {
      {23, 89, 10, 5, 67, 39, 70,28},
      {34, 53, 6, 95, 38, 28, 17, 63, 16, 76},
      {288, 224, 275, 390, 4, 383, 330, 60, 193},
      {1, 2, 3, 4, 5, 6, 7, 8, 9},
      {69, 8, 49, 106, 116, 112, 104, 129, 39, 14, 27, 12}
    };
    int[] n = {4, 1, 6, 9, 11};
    for (int i = 0; i < inputs.length; i++) {
      LinkedList < Integer > inputLinkedList = new LinkedList < Integer > ();
      inputLinkedList.createLinkedList(inputs[i]);
      System.out.print((i + 1) + ".\tLinked List:\t\t");
      PrintList.printListWithForwardArrow(inputLinkedList.head);
      System.out.print("\n\tn = " + n[i]);
      System.out.print("\n\tUpdated Linked List:\t");
      PrintList.printListWithForwardArrow(removeNthLastNode(inputLinkedList.head, n[i]));
      System.out.println();
      System.out.println(new String(new char[100]).replace('\0', '-'));
    }
  }
}
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.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.