How to remove the nth node from the end of a linked list?

Also, you are given the value of $n$ to be 2. If you look closely, you can see that the node containing the value 4 is the node that needs to be deleted from the linked list because it's at the second position from the end of the linked list.

Solution approach

Now that the problem statement is clear, let's try to think about the solution.

We'll follow the steps mentioned below to build up an algorithm to solve the problem.

First, we'll calculate the number of nodes that are present in the given linked list. We'll store this value in a variable called num_nodes.
Second, we'll calculate the position of the node that needs to be deleted from the start by applying the formula position_start = num_nodes - n + 1.
We'll consider the same example that we discussed above. The value for $n$ is 2 so the position of the node to be deleted from start will be 5 ( the total number of nodes) – 2 + 1 which is 4. We need to delete the 4^th node from the start of the linked list.

We'll traverse the nodes and maintain the number of the nodes that are traversed at each step. Also, we'll store the address of the previous node at each step.
Once we arrive at the node where we need to delete the current node, we'll just replace the previous node's pointer with the current node's pointer. You can refer to the below slideshow to understand how the node is deleted.

#include<iostream>
using namespace std;
// Structure of a linked list node
struct ListNode {
  int val;
  ListNode *next;
};
// head pointer
ListNode *head = NULL;
// Function to create a linked list
ListNode* createLinkedList(){
  ListNode *temp;
  for(int i = 5; i >= 1; i--){
    ListNode* node = new ListNode();
    node->val = i;
    node->next = NULL;
    if(head == NULL){
      head = node;
      temp = node;
    }
    else{
      temp->next = node;
      temp = node;
    }
  }
  return head;
}
// Function to display the nodes present in the linked list
void displayLinkedList(ListNode* head){
  struct ListNode *current = head;  
      
    if(head == NULL) {  
      cout << "List is empty";  
      return;
    }  
    cout << "Nodes of singly linked list: \n";  
    while(current != NULL) {  
        cout << current->val << " ";  
        current = current->next;  
    }
}
// Count the total number of nodes present in the linked list
int countNodes(ListNode* head){
  ListNode* temp = head;
  int numNodes = 0;
  while(temp != NULL){
    numNodes++;
    temp = temp -> next;
  }
  return numNodes;
}
// Remove the Nth node from the end of the linked list
ListNode* removeNthFromEnd(ListNode* head, int n) {
  int numNodes = countNodes(head);
  int removePos = numNodes - n + 1;
        
  if (numNodes == 1 && removePos == 1)
    return NULL;
        
  ListNode *temp = head, *prev = NULL;
  numNodes = 0;
  while(temp != NULL){
    numNodes++;
    if (numNodes == removePos){
      if (prev == NULL)
        head = temp -> next;
      else
        prev->next = temp->next == NULL ? NULL: temp->next;
      break;
    }
    prev = temp;
    temp = temp->next;
  }
  return head;
}
// Main function
int main(){
  // Create a linked list and print it
  ListNode* head = createLinkedList();
  displayLinkedList(head);
  // Delete the Nth node and print the linked list
  cout << endl;
  head = removeNthFromEnd(head, 2);
  displayLinkedList(head);
  return 0;
}

Explanation:

Lines 5–8: We define the structure of a node in the linked list.
Lines 13–14: We create a function createLinkedList() to create a linked list of 5 nodes.
Lines 33–45: We created a function displayLinkedList() to display the nodes present in the linked list.
Lines 48–57: We create a function countNodes() to count the total number of nodes that are present in the linked list.
Lines 60–82: We created a function removeNthFromEnd() that will accept the head of the linked list and the position of the node n that needs to be deleted from the end.

Line 61: We calculate the total number of nodes present in the linked list.
Line 62: We calculate the position of the node that needs to be deleted from the start of the linked list.
Lines 64–65: We return NULL if there is a single node present in the linked list.
Line 69: We run a while loop to iterate over all the nodes until we come to the position at which the node needs to be deleted.
Lines 71–77: We start removing the node from the linked list by assigning the previous node's pointer to the current node's pointer. Hence, the node is removed from the linked list.
Lines 78–79: We update the previous node and the current node (if the current node is not the one to delete).
Line 81: We return the head of the linked list.

Lines 88–89: We create a linked list and print it.
Lines 93–94: We remove the second node from the end of the linked list and then print the new linked list. We can observe that the node is deleted.

Note: If you want to learn and solve more coding interview questions, you can check out the course Competitive Programming - Crack Your Coding Interview, C++.

Free Resources

License: Creative Commons-Attribution-ShareAlike 4.0 (CC-BY-SA 4.0)

How to remove the nth node from the end of a linked list?

Introduction

Solution approach

Code example

Explanation: