Delete Nth node from the end of the given linked list
Given a linked list and an integer N, the task is to delete the Nth node from the end of the given linked list.
Examples:
Input: 2 -> 3 -> 1 -> 7 -> NULL, N = 1
Output:
The created linked list is:
2 3 1 7
The linked list after deletion is:
2 3 1
Input: 1 -> 2 -> 3 -> 4 -> NULL, N = 4
Output:
The created linked list is:
1 2 3 4
The linked list after deletion is:
2 3 4
Intuition:
Lets K be the total nodes in the linked list.
Observation : The Nth node from the end is (K-N+1)th node from the beginning.
So the problem simplifies down to that we have to find (K-N+1)th node from the beginning.
- One way of doing it is to find the length (K) of the linked list in one pass and then in the second pass move (K-N+1) step from the beginning to reach the Nth node from the end.
- To do it in one pass. Let’s take the first pointer and move N step from the beginning. Now the first pointer is (K-N+1) steps away from the last node, which is the same number of steps the second pointer require to move from the beginning to reach the Nth node from the end.
// C++ code for the deleting a node from end
// in two traversal
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
Node(int value)
{
this->data = value;
this->next = NULL;
}
};
int length(Node* head)
{
Node* temp = head;
int count = 0;
while (temp != NULL) {
count++;
temp = temp->next;
}
return count;
}
void printList(Node* head)
{
Node* ptr = head;
while (ptr != NULL) {
cout << ptr->data << " ";
ptr = ptr->next;
}
cout << endl;
}
Node* deleteNthNodeFromEnd(Node* head, int n)
{
int Length = length(head);
int nodeFromBeginning = Length - n + 1;
Node* prev = NULL;
Node* temp = head;
for (int i = 1; i < nodeFromBeginning; i++) {
prev = temp;
temp = temp->next;
}
if (prev == NULL) {
head = head->next;
return head;
}
else {
prev->next = prev->next->next;
return head;
}
}
int main()
{
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
head->next->next->next->next = new Node(5);
cout<<"Linked List before Deletion:"<<endl;
printList(head);
head = deleteNthNodeFromEnd(head, 4);
cout<<"Linked List after Deletion: "<<endl;
printList(head);
return 0;
}
// This code is contributed by Yash Agarwal(yashagarwal2852002)
class Node {
int data;
Node next;
Node(int value)
{
this.data = value;
this.next = null;
}
}
class Main {
static int length(Node head)
{
Node temp = head;
int count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
static void printList(Node head)
{
Node ptr = head;
while (ptr != null) {
System.out.print(ptr.data + " ");
ptr = ptr.next;
}
System.out.println();
}
static Node deleteNthNodeFromEnd(Node head, int n)
{
int Length = length(head);
int nodeFromBeginning = Length - n + 1;
Node prev = null;
Node temp = head;
for (int i = 1; i < nodeFromBeginning; i++) {
prev = temp;
temp = temp.next;
}
if (prev == null) {
head = head.next;
return head;
}
else {
prev.next = prev.next.next;
return head;
}
}
public static void main(String[] args)
{
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
System.out.println("Linked List before Deletion:");
printList(head);
head = deleteNthNodeFromEnd(head, 4);
System.out.println("Linked List after Deletion:");
printList(head);
}
}
// This code is contributed by user_dtewbxkn77n
# Python code for the deleting a node from end
# in two traversal
class Node:
def __init__(self, value):
self.data = value
self.next = None
def length(head):
temp = head
count = 0
while(temp != None):
count += 1
temp = temp.next
return count
def printList(head):
ptr = head
while(ptr != None):
print (ptr.data, end =" ")
ptr = ptr.next
print()
def deleteNthNodeFromEnd(head, n):
Length = length(head)
nodeFromBeginning = Length - n + 1
prev = None
temp = head
for i in range(1, nodeFromBeginning):
prev = temp
temp = temp.next
if(prev == None):
head = head.next
return head
else:
prev.next = prev.next.next
return head
if __name__ == '__main__':
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
print("Linked List before Deletion:")
printList(head)
head = deleteNthNodeFromEnd(head, 4)
print("Linked List after Deletion:")
printList(head)
// This C# code defines a class Node which represents a node
// in a linked list. Each node has an integer value 'data'
// and a reference to the next node in the list 'next'. The
// class also defines a static method 'Length' that takes
// the head of a linked list as input and returns the number
// of nodes in the list. Another static method 'PrintList'
// is defined to print the elements of a linked list.
using System;
public class Node {
public int data; // data stored in the node
public Node next; // reference to the next node
// constructor to create a new node with the given data
public Node(int value)
{
this.data = value;
this.next = null;
}
}
public class Program {
// static method to find the length of a linked list
// given its head node
public static int Length(Node head)
{
Node temp = head;
int count = 0;
while (temp != null) // loop until the end of the
// list is reached
{
count++; // increment count for each node
// visited
temp = temp.next; // move to the next node
}
return count;
}
// static method to print the elements of a linked list
public static void PrintList(Node head)
{
Node ptr = head;
while (ptr != null) // loop until the end of the
// list is reached
{
Console.Write(ptr.data
+ " "); // print the data of the
// current node
ptr = ptr.next; // move to the next node
}
Console.WriteLine(); // move to the next line after
// printing the list
}
// static method to delete the nth node from the end of
// a linked list
public static Node DeleteNthNodeFromEnd(Node head,
int n)
{
int Length = Program.Length(
head); // find the length of the list
int nodeFromBeginning
= Length - n
+ 1; // find the index of the node to be
// deleted from the beginning
Node prev = null;
Node temp = head;
for (int i = 1; i < nodeFromBeginning;
i++) // loop until the node before the one to
// be deleted is reached
{
prev = temp;
temp = temp.next;
}
if (prev
== null) // if the first node is to be deleted
{
head = head.next; // update the head node to the
// next node
return head; // return the updated head node
}
else // if any other node is to be deleted
{
prev.next
= prev.next
.next; // skip the node to be deleted
// by updating the reference of
// the previous node
return head; // return the head node
}
}
public static void Main()
{
// create a linked list with 5 nodes
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
// print the linked list before deletion
Console.WriteLine("Linked List before Deletion:");
Program.PrintList(head);
// delete the 4th node from the end of the linked
// list
head = Program.DeleteNthNodeFromEnd(head, 4);
// print the linked list after deletion
Console.WriteLine("Linked List after Deletion:");
Program.PrintList(head);
}
}
class Node {
constructor(value) {
this.data = value;
this.next = null;
}
}
function length(head) {
let temp = head;
let count = 0;
while (temp != null) {
count++;
temp = temp.next;
}
return count;
}
function printList(head) {
let ptr = head;
while (ptr != null) {
process.stdout.write(ptr.data + " ");
ptr = ptr.next;
}
console.log();
}
function deleteNthNodeFromEnd(head, n) {
let Length = length(head);
let nodeFromBeginning = Length - n + 1;
let prev = null;
let temp = head;
for (let i = 1; i < nodeFromBeginning; i++) {
prev = temp;
temp = temp.next;
}
if (prev == null) {
head = head.next;
return head;
} else {
prev.next = prev.next.next;
return head;
}
}
let head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);
console.log("Linked List before Deletion:");
printList(head);
head = deleteNthNodeFromEnd(head, 4);
console.log("Linked List after Deletion:");
printList(head);
Output
Linked List before Deletion: 1 2 3 4 5 Linked List after Deletion: 1 3 4 5
Two Pointer Approach – Slow and Fast Pointers
This problem can be solved by using two pointer approach as below:
- Take two pointers – fast and slow. And initialize their values as head node
- Iterate fast pointer till the value of n.
- Now, start iteration of fast pointer till the None value of the linked list. Also, iterate slow pointer.
- Hence, once the fast pointer will reach to the end the slow pointer will reach the node which you want to delete.
- Replace the next node of the slow pointer with the next to next node of the slow pointer.
// C++ code for the deleting a node from end using two
// pointer approach
#include <iostream>
using namespace std;
class LinkedList {
public:
// structure of a node
class Node {
public:
int data;
Node* next;
Node(int d)
{
data = d;
next = NULL;
}
};
// Head node
Node* head;
// Function for inserting a node at the beginning
void push(int data)
{
Node* new_node = new Node(data);
new_node->next = head;
head = new_node;
}
// Function to display the nodes in the list.
void display()
{
Node* temp = head;
while (temp != NULL) {
cout << temp->data << endl;
temp = temp->next;
}
}
// Function to delete the nth node from the end.
Node* deleteNthNodeFromEnd(Node* head, int n)
{
if(head==NULL) {
cout<<"Err : List is empty"<<endl;
return head;
}
if(n<=0) {
cout<<"Err : Number should be positive"<<endl;
return head;
}
Node* fast = head;
Node* slow = head;
for (int i = 1; i <=n; i++) {
if(fast == NULL && i!=n-1) {
cout<<"Err : Number is greater than length of List"<<endl;
return head;
}
fast = fast->next;
}
if (fast == NULL) {
return head->next;
}
while (fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
};
int main()
{
LinkedList* l = new LinkedList();
// Create a list 1->2->3->4->5->NULL
l->push(5);
l->push(4);
l->push(3);
l->push(2);
l->push(1);
cout << "***** Linked List Before deletion *****"
<< endl;
l->display();
cout << "************** Delete nth Node from the End "
"*****"
<< endl;
l->head = l->deleteNthNodeFromEnd(l->head, 1);
cout << "*********** Linked List after Deletion *****"
<< endl;
l->display();
return 0;
}
// This code is contributed by lokesh (lokeshmvs21).
// Java code for deleting a node from the end using two
// Pointer Approach
class GFG {
class Node {
int data;
Node next;
Node(int data)
{
this.data = data;
this.next = null;
}
}
Node head;
// Function to insert node at the beginning of the list.
public void push(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
// Function to print the nodes in the linked list.
public void display()
{
Node temp = head;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
public void deleteNthNodeFromEnd(Node head, int n)
{
Node fast = head;
Node slow = head;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
if (fast == null) {
head = head.next;
return;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return;
}
public static void main(String[] args)
{
GFG l = new GFG();
// Create a list 1->2->3->4->5->NULL
l.push(5);
l.push(4);
l.push(3);
l.push(2);
l.push(1);
System.out.println(
"***** Linked List Before deletion *****");
l.display();
System.out.println(
"************** Delete nth Node from the End *****");
l.deleteNthNodeFromEnd(l.head, 2);
System.out.println(
"*********** Linked List after Deletion *****");
l.display();
}
}
// This code is contributed by lokesh (lokeshmvs21).
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def display(self):
temp = self.head
while temp != None:
print(temp.data)
temp = temp.next
def deleteNthNodeFromEnd(self, head, n):
fast = head
slow = head
for _ in range(n):
fast = fast.next
if not fast:
return head.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
if __name__ == '__main__':
l = LinkedList()
l.push(5)
l.push(4)
l.push(3)
l.push(2)
l.push(1)
print('***** Linked List Before deletion *****')
l.display()
print('************** Delete nth Node from the End *****')
l.deleteNthNodeFromEnd(l.head, 2)
print('*********** Linked List after Deletion *****')
l.display()
// C# code for deleting a node from the end using two
// Pointer Approach
using System;
public class GFG {
public class Node {
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
Node head;
void push(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
void display()
{
Node temp = head;
while (temp != null) {
Console.WriteLine(temp.data);
temp = temp.next;
}
}
public void deleteNthNodeFromEnd(Node head, int n)
{
Node fast = head;
Node slow = head;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
if (fast == null) {
head = head.next;
return;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return;
}
static public void Main()
{
// Code
GFG l = new GFG();
// Create a list 1->2->3->4->5->NULL
l.push(5);
l.push(4);
l.push(3);
l.push(2);
l.push(1);
Console.WriteLine(
"***** Linked List Before deletion *****");
l.display();
Console.WriteLine(
"************** Delete nth Node from the End *****");
l.deleteNthNodeFromEnd(l.head, 2);
Console.WriteLine(
"*********** Linked List after Deletion *****");
l.display();
}
}
// This code is contributed by lokesh(lokeshmvs21).
<script>
class Node{
constructor(data){
this.data = data
this.next = null
}
}
class LinkedList{
constructor(){
this.head = null
}
push(data){
let new_node = new Node(data)
new_node.next =this.head
this.head = new_node
}
display(){
let temp =this.head
while(temp != null){
document.write(temp.data,"</br>")
temp = temp.next
}
}
deleteNthNodeFromEnd(head, n){
let fast = head
let slow = head
for(let i=0;i<n;i++){
fast = fast.next
}
if(!fast)
return head.next
while(fast.next){
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return head
}
}
// driver code
let l = new LinkedList()
l.push(5)
l.push(4)
l.push(3)
l.push(2)
l.push(1)
document.write('***** Linked List Before deletion *****',"</br>")
l.display()
document.write('************** Delete nth Node from the End *****',"</br>")
l.deleteNthNodeFromEnd(l.head, 2)
document.write('*********** Linked List after Deletion *****',"</br>")
l.display()
// This code is contributed by shinjanpatra
</script>
Output
***** Linked List Before deletion ***** 1 2 3 4 5 ************** Delete nth Node from the End ***** *********** Linked List after Deletion ***** 1 2 3 4
Time complexity: O(n)
Space complexity: O(1) using constant space
Contact Us