Trusted answers to developer questions

Harsh Jain

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

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

Example linked list

Also, you are given the value of

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^{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.

Traversing the first node

#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

**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

CONTRIBUTOR

Harsh Jain

RELATED COURSES

View all Courses

Keep Exploring

Related Courses