Related Tags

interview
c++
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 $n$. Your task is to remove the $n^{th}$ node from the end of the linked list.

Let's first understand the problem statement. Suppose that you have the following 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 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;
};

// Function to create a linked list
ListNode *temp;
for(int i = 5; i >= 1; i--){
ListNode* node = new ListNode();
node->val = i;
node->next = NULL;
temp = node;
}
else{
temp->next = node;
temp = node;
}
}
}

// Function to display the nodes present in the linked list

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 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 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)
else
prev->next = temp->next == NULL ? NULL: temp->next;
break;
}
prev = temp;
temp = temp->next;
}
}

// Main function
int main(){

// Create a linked list and print it

// Delete the Nth node and print the linked list
cout << endl;
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++
communitycreator

CONTRIBUTOR

Harsh Jain
RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time