Last Updated on November 11, 2022 by Prepbytes
This blog will give the detailed description to Delete Nth node from the end of the linked list. Deleting the Nth node from the end of the linked list will help in better understanding of data structures like linked lists. Deep diving into the linked list will move one step ahead towards your goals.
How To Delete Nth Node From The End Of The Linked List:
You are given a singly-linked list, delete the kth node from the end of the list and then print Linked list after deletion of the kthnode.
Note: Given k will always be valid.
Example:-
Given: 1->2->3->4->5->6
K=3
After Deletion:
1->2->3->5->6
4 is the third last node from the end of the linked list.You are encouraged to try the problem on your own before looking at the solution.
See original problem statement here
Approaches To Delete Nth Node From The End Of The Linked List
Brute force To Delete Nth Node From The End Of The Linked List:
Start with the first node and count the number of nodes present after that node.If the number of nodes are
If the number of nodes are > K-1 then go to the next node.
Continue this until the number of nodes after the current node are K-1.Time complexity: O(n*n) ,for scanning the remaining list (from the current node) for each list. Space complexity: O(1).Can we make this any better?
Approach 2 To Delete Nth Node From The End Of The Linked List:
If L is the length of the linked list,(L−k+1) th node from the beginning is the Kth node from the end of the linked list.
Look at the example:
K=4;
You can see that the 4th node from the end is the same node which is 2nd from the beginning (L-K+1=5-4+1).
So the problem could be simply reduced to another one : Remove the (L−k+1) th node from the beginning in the list , where L is the list length. This problem becomes easy if we find the length of the list .
Time Complexity To Delete Nth Node From The End Of The Linked List: O(n). Space complexity To Delete Nth Node From The End Of The Linked List: O(1).Note: This algorithm needs two traversals(one to find L). The below algorithm is one pass algorithm.
Approach 3 To Delete Nth Node From The End Of The Linked List:
Use two pointers Kth Node and Temp.Initially, both point to the head node of the list. Kth Node starts moving only after Temp makes K moves.
From there both move forward until lTemp reaches the end of the list. As a result lKthTemp points to the kth node from the end of the linked list.
Time Complexity To Delete Nth Node From The End Of The Linked List: O(n). Space complexity To Delete Nth Node From The End Of The Linked List: O(1).
SOLUTION To Delete Nth Node From The End Of The Linked List:
#include <stdio.h>
#include<stdlib.h>
struct node{
int data;
struct node* next;
};
struct node* newnode(int x)
{
//struct node* temp=new node();
struct node* temp;
temp= (struct node *)malloc(sizeof(struct node));
temp->data=x;
temp->next=NULL;
return temp;
}
int main()
{
int t;scanf("%d",&t);
while(t--)
{
int n,k;scanf("%d%d",&n,&k);
int x;scanf("%d",&x);
struct node* head=newnode(x);
struct node* headlist=head;
for(int i=1;i<n;i++)
{
int y;scanf("%d",&y);
head->next=newnode(y);
head=head->next;
}
struct node* prev=NULL,*current=headlist;
for(int i=1;i<k;i++)
{
prev=current;
current=current->next;
}
if(prev==NULL)
{
headlist=current->next;
// delete(current);
}
else
{
struct node* nxt=current->next;
prev->next=nxt;
//delete(current);
}
while(headlist!=NULL)
{
printf("%d ",headlist->data);
headlist=headlist->next;
}
printf("\n");
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
node* next;
};
node* newnode(int x)
{
node* temp=new node();
temp->data=x;
temp->next=NULL;
return temp;
}
int main()
{
int t;cin>>t;
while(t--)
{
int n,k;cin>>n>>k;
int x;cin>>x;
node* head=newnode(x);
node* headlist=head;
for(int i=1;i<n;i++)
{
int y;cin>>y;
head->next=newnode(y);
head=head->next;
}
node* prev=NULL,*current=headlist;
for(int i=1;i<k;i++)
{
prev=current;
current=current->next;
}
if(prev==NULL)
{
headlist=current->next;
delete(current);
}
else
{
node* nxt=current->next;
prev->next=nxt;
delete(current);
}
while(headlist!=NULL)
{
cout<<headlist->data<<" ";
headlist=headlist->next;
}
cout<<"\n";
}
return 0;
}
import java.util.*;
import java.io.*;
class LinkedList
{
Node head;
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
void deleteNode(int position)
{
if (head == null)
return;
Node temp = head;
if (position == 0)
{
head = temp.next;
return;
}
for (int i=0; temp!=null && i<position-1; i++)
temp = temp.next;
if (temp == null || temp.next == null)
return;
Node next = temp.next.next;
temp.next = next;
}
public void printList()
{
Node tnode = head;
while (tnode != null)
{
System.out.print(tnode.data+" ");
tnode = tnode.next;
}
}
public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
int t= sc.nextInt();
while(t-- >0 ){
int n = sc.nextInt();
int k = sc.nextInt();
LinkedList llist = new LinkedList();
int p[]=new int[n];
for(int i=0;i<n;i++)
{
p[i] = sc.nextInt();
}
for(int i=n-1;i>=0;i--)
{
llist.push(p[i]);
}
llist.deleteNode(k-1);
llist.printList(); }
}
}
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def deleteNode(self, n):
first = self.head
second = self.head
for i in range(n):
if(second.next == None):
if(i == n - 1):
self.head = self.head.next
return self.head
second = second.next
while(second.next != None):
second = second.next
first = first.next
first.next = first.next.next
def printList(self):
tmp_head = self.head
while(tmp_head != None):
print(tmp_head.data, end = ' ')
tmp_head = tmp_head.next
llist = LinkedList()
llist.push(7)
llist.push(1)
llist.push(3)
llist.push(2)
print("Created Linked list is:")
llist.printList()
llist.deleteNode(1)
print("\nLinked List after Deletion is:")
llist.printList()
This blog will discuss different approaches to Delete Nth node from the end of the linked list. Daily learning skills like data structures by practicing topics such as Linked List will help in daily life as well as in conquering dreams for working in Tech Companies like Amazon, Google, Microsoft and Facebook. Hope this blog helps you understand and solve the problem. To practice more problems on linked list you can check out MYCODE | Competitive Programming.
FAQs
1. How do you find the Kth last node of a linked list of length n?
A simple solution is to calculate the total number of nodes n in the linked list first. Then, the k’th node from the end will be (n-k+1)’th node from the beginning.
2. How do you find the end of a linked list?
The last node of a linked list has the reference pointer as NULL. i.e. node=>next = NULL. To find the last node, we have to iterate the linked list till the node=>next != NULL.
3. How do I find a previous node in a linked list?
You cannot simply go to the previous node in a singly‑linked list. You would have to create a doubly‑linked list, or an array list, or have your Iterator retain the pointer to the previous node.