{"id":3859,"date":"2021-08-16T12:50:24","date_gmt":"2021-08-16T12:50:24","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3859"},"modified":"2022-03-08T12:37:15","modified_gmt":"2022-03-08T12:37:15","slug":"remove-nth-node-from-end-of-the-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/remove-nth-node-from-end-of-the-linked-list\/","title":{"rendered":"Remove Nth Node From End Of The Linked List"},"content":{"rendered":"

\"\"<\/p>\n

Problem Statement<\/h3>\n

Given a singly linked list along with a positive integer N. Write a function to delete the Nth<\/sup> node from the end of the given linked list.<\/p>\n<\/p>\n

Problem Statement Understanding<\/h3>\n

Let’s understand the given problem with the help of some examples:<\/p>\n

If our initial linked list:<\/p>\n

\"\"<\/p>\n

It means that here we had to remove the N = 3rd<\/sup> node from the end which is 3, so we will remove it.<\/p>\n

After removing the 3rd<\/sup> node from the end of the linked list, our output resultant linked list is <\/p>\n

\"\"<\/p>\n

If our initial linked list:<\/p>\n

\"\"<\/p>\n

It means that here we had to remove the N=1st<\/sup> node from the end which is 6, so we will remove it.<\/p>\n

After removing the 1st<\/sup> node from the end of the linked list, our output resultant linked list is:<\/p>\n

\"\"<\/p>\n

I hope that now you have understood this problem. Now, think of how we can approach this problem?<\/p>\n

One simple approach will be to first find the length of linked list and then using it find the Nth node from the end. Let\u2019s see how we will do this.<\/p>\n

If length of our linked list is P, it means that we have to find (P-N)th<\/sup> node from the beginning of the linked list and this node will be the Nth<\/sup> node from the end of the linked list.<\/p>\n

So to delete Nth<\/sup> node using the above approach we will have to first traverse the linked list and find the length P of the linked list. Then we will have to again traverse the linked list (P-N+1) steps to reach the Nth<\/sup> node from the end. <\/p>\n

This will work fine, but it is taking 2 traversals of linked list to find the Nth<\/sup> node from the end. Now try to think, do we actually require the length of linked list to find the Nth<\/sup> node from the end of the linked list?<\/p>\n

So in approach we will see how we can do it in single traversal of linked list.<\/p>\n

Approach<\/h3>\n

Our approach would be simple.
\nTo remove the Nth<\/sup> node from the end, we need two things, which are:
\n1) the Nth<\/sup> node from the end and
\n2) the node just before it.<\/p>\n

First, we need to find the Nth<\/sup> node from the end of the linked list. There are many ways to do so. We will use the most efficient one, i.e., using 2 pointers.<\/p>\n

We start with 2 pointers from the head. <\/p>\n