Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

interview
c++
linked list
communitycreator

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

Harsh Jain

Introduction

In this shot, we'll solve a commonly asked interview question on linked list. The problem statement is as follows:

You are given the head of a linked list and an integer nn. Your task is to remove the nthn^{th} node from the end of the linked list.

Let's first understand the problem statement. Suppose that you have the following linked list:

%0 node_1 1 node_2 2 node_1->node_2 node_3 3 node_2->node_3 node_1646195978777 4 node_3->node_1646195978777 node_1646196033040 5 node_1646195978777->node_1646196033040
Example linked list

Also, you are given the value of nn 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 nn 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 4th 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.
Traversing the first node
1 of 6

Code example

#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;
}
Delete the Nth node from the end of a linked list

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++.

RELATED TAGS

interview
c++
linked list
communitycreator
RELATED COURSES

View all Courses

Keep Exploring