Delete Nth node from the end of the given linked list

Last Updated : 28 Oct, 2023

Given a linked list and an integer N, the task is to delete the N^th 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 N^thnode 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 N^th 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 N^th node from the end.

C++

// 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)

Java

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

Python3

# 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)

C#

// 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);
    }
}

Javascript

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

Approach:

Take two pointers; the first will point to the head of the linked list and the second will point to the N^th node from the beginning.
Now keep incrementing both the pointers by one at the same time until the second is pointing to the last node of the linked list.
After the operations from the previous step, the first pointer should point to the N^th node from the end now. So, delete the node the first pointer is pointing to.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
class LinkedList {
public:
    // Linked list Node
    class Node {
    public:
        int data;
        Node* next;
        Node(int d)
        {
            data = d;
            next = NULL;
        }
    };
 
    // Head of list
    Node* head;
 
    // Function to delete the nth node from the end of the
    // given linked list
    Node* deleteNode(int key)
    {
        // We will be using this pointer for holding address
        // temporarily while we delete the node
        Node* temp;
 
        // First pointer will point to the head of the
        // linked list
        Node* first = head;
 
        // Second pointer will point to the Nth node from
        // the beginning
        Node* second = head;
        for (int i = 0; i < key; i++) {
            // If count of nodes in the given linked list is <= N
            if (second->next == NULL) {
                // If count = N i.e. delete the head node
                if (i == key - 1) {
                    temp = head;
                    head = head->next;
                    free(temp);
                }
                return head;
            }
            second = second->next;
        }
 
        // Increment both the pointers by one until second
        // pointer reaches the end
        while (second->next != NULL) {
            first = first->next;
            second = second->next;
        }
        // First must be pointing to the Nth node from the
        // end by now So, delete the node first is pointing to
        temp = first->next;
        first->next = first->next->next;
        free(temp);
        return head;
    }
 
    // Function to insert a new Node at front of the list
    Node* push(int new_data)
    {
        Node* new_node = new Node(new_data);
        new_node->next = head;
        head = new_node;
        return head;
    }
 
    // Function to print the linked list
    void printList()
    {
        Node* tnode = head;
        while (tnode != NULL) {
            cout << (tnode->data) << (" ");
            tnode = tnode->next;
        }
    }
};
 
// Driver code
int main()
{
    LinkedList* llist = new LinkedList();
 
    llist->head = llist->push(7);
    llist->head = llist->push(1);
    llist->head = llist->push(3);
    llist->head = llist->push(2);
 
    cout << ("Created Linked list is:\n");
    llist->printList();
 
    int N = 1;
    llist->head = llist->deleteNode(N);
 
    cout << ("\nLinked List after Deletion is:\n");
    llist->printList();
}
 
// This code is contributed by Sania Kumari Gupta

C

/* C program to merge two sorted linked lists */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
 
/* Link list node */
typedef struct Node {
    int data;
    struct Node* next;
} Node;
 
Node* deleteNode(Node* head, int key)
{
   
    // We will be using this pointer for holding address
    // temporarily while we delete the node
    Node* temp;
 
    // First pointer will point to the head of the linked
    // list
    Node* first = head;
 
    // Second pointer will point to the Nth node from the
    // beginning
    Node* second = head;
    for (int i = 0; i < key; i++) {
 
        // If count of nodes in the given linked list is <=N
        if (second->next == NULL) {
 
            // If count = N i.e. delete the head node
            if (i == key - 1) {
                temp = head;
                head = head->next;
                free(temp);
            }
            return head;
        }
        second = second->next;
    }
 
    // Increment both the pointers by one until
    // second pointer reaches the end
    while (second->next != NULL) {
        first = first->next;
        second = second->next;
    }
 
    // First must be pointing to the Nth node from the end
    // by now So, delete the node first is pointing to
    temp = first->next;
    first->next = first->next->next;
    free(temp);
    return head;
}
 
/* Function to insert a node at the beginning of the
linked list */
void push(Node** head_ref, int new_data)
{
    /* allocate node */
    Node* new_node = (Node*)malloc(sizeof(Node));
    /* put in the data */
    new_node->data = new_data;
    /* link the old list off the new node */
    new_node->next = (*head_ref);
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
/* Function to print nodes in a given linked list */
void printList(struct Node* node)
{
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
}
 
// Driver program
int main()
{
    struct Node* head = NULL;
    push(&head, 7);
    push(&head, 1);
    push(&head, 3);
    push(&head, 2);
    printf("Created Linked list is:\n");
    printList(head);
    int n = 1;
    deleteNode(head, n);
    printf("\nLinked List after Deletion is:\n");
    printList(head);
    return 0;
}
 
// This code is contributed by Sania Kumari Gupta

Java

// Java implementation of the approach
class LinkedList {
 
    // Head of list
    Node head;
 
    // Linked list Node
    class Node {
        int data;
        Node next;
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    // Function to delete the nth node from
    // the end of the given linked list
    void deleteNode(int key)
    {
 
        // First pointer will point to
        // the head of the linked list
        Node first = head;
 
        // Second pointer will point to the
        // Nth node from the beginning
        Node second = head;
        for (int i = 0; i < key; i++) {
 
            // If count of nodes in the given
            // linked list is <= N
            if (second.next == null) {
 
                // If count = N i.e. delete the head node
                if (i == key - 1)
                    head = head.next;
                return;
            }
            second = second.next;
        }
 
        // Increment both the pointers by one until
        // second pointer reaches the end
        while (second.next != null) {
            first = first.next;
            second = second.next;
        }
 
        // First must be pointing to the
        // Nth node from the end by now
        // So, delete the node first is pointing to
        first.next = first.next.next;
    }
 
    // Function to insert a new Node at front of the list
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
 
    // Function to print the linked list
    public void printList()
    {
        Node tnode = head;
        while (tnode != null) {
            System.out.print(tnode.data + " ");
            tnode = tnode.next;
        }
    }
 
    // Driver code
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();
 
        llist.push(7);
        llist.push(1);
        llist.push(3);
        llist.push(2);
 
        System.out.println("\nCreated Linked list is:");
        llist.printList();
 
        int N = 1;
        llist.deleteNode(N);
 
        System.out.println("\nLinked List after Deletion is:");
        llist.printList();
    }
}

Python3

# Python3 implementation of the approach
class Node: 
    def __init__(self, new_data): 
        self.data = new_data 
        self.next = None
class LinkedList:
    def __init__(self):
        self.head = None
 
    # createNode and make linked list 
    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 count of nodes in the 
            # given list is less than 'n'
            if(second.next == None):
                 
                # If index = n then 
                # delete the head node
                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
         
# Driver Code
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 code is contributed by RaviParkash

C#

// C# implementation of the approach
using System;
     
public class LinkedList
{
 
    // Head of list
    public Node head;
 
    // Linked list Node
    public class Node 
    {
        public int data;
        public Node next;
        public Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    // Function to delete the nth node from
    // the end of the given linked list
    void deleteNode(int key)
    {
 
        // First pointer will point to
        // the head of the linked list
        Node first = head;
 
        // Second pointer will point to the
        // Nth node from the beginning
        Node second = head;
        for (int i = 0; i < key; i++) 
        {
 
            // If count of nodes in the given
            // linked list is <= N
            if (second.next == null) 
            {
 
                // If count = N i.e. delete the head node
                if (i == key - 1)
                    head = head.next;
                return;
            }
            second = second.next;
        }
 
        // Increment both the pointers by one until
        // second pointer reaches the end
        while (second.next != null) 
        {
            first = first.next;
            second = second.next;
        }
 
        // First must be pointing to the
        // Nth node from the end by now
        // So, delete the node first is pointing to
        first.next = first.next.next;
    }
 
    // Function to insert a new Node at front of the list
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
 
    // Function to print the linked list
    public void printList()
    {
        Node tnode = head;
        while (tnode != null)
        {
            Console.Write(tnode.data + " ");
            tnode = tnode.next;
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        LinkedList llist = new LinkedList();
 
        llist.push(7);
        llist.push(1);
        llist.push(3);
        llist.push(2);
 
        Console.WriteLine("\nCreated Linked list is:");
        llist.printList();
 
        int N = 1;
        llist.deleteNode(N);
 
        Console.WriteLine("\nLinked List after Deletion is:");
        llist.printList();
    }
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// javascript implementation of the approach
 
    // Head of list
    var head;
 
    // Linked list Node
    class Node {
        constructor(val) {
            this.data = val;
            this.next = null;
        }
    }
 
    // Function to delete the nth node from
    // the end of the given linked list
    function deleteNode(key) {
 
        // First pointer will point to
        // the head of the linked list
        var first = head;
 
        // Second pointer will point to the
        // Nth node from the beginning
        var second = head;
        for (i = 0; i < key; i++) {
 
            // If count of nodes in the given
            // linked list is <= N
            if (second.next == null) {
 
                // If count = N i.e. delete the head node
                if (i == key - 1)
                    head = head.next;
                return;
            }
            second = second.next;
        }
 
        // Increment both the pointers by one until
        // second pointer reaches the end
        while (second.next != null) {
            first = first.next;
            second = second.next;
        }
 
        // First must be pointing to the
        // Nth node from the end by now
        // So, delete the node first is pointing to
        first.next = first.next.next;
    }
 
    // Function to insert a new Node at front of the list
     function push(new_data) {
        var new_node = new Node(new_data);
        new_node.next = head;
        head = new_node;
    }
 
    // Function to print the linked list
    function printList() {
        var tnode = head;
        while (tnode != null) {
            document.write(tnode.data + " ");
            tnode = tnode.next;
        }
    }
 
    // Driver code
     
        push(7);
        push(1);
        push(3);
        push(2);
 
        document.write("\nCreated Linked list is:<br/>");
        printList();
 
        var N = 1;
        deleteNode(N);
 
        document.write("<br/>Linked List after Deletion is:<br/>");
        printList();
 
// This code is contributed by todaysgaurav 
</script>

Output

Created Linked list is:
2 3 1 7 
Linked List after Deletion is:
2 3 1

Time Complexity: O(N) where N is the number of nodes in the given Linked List.
Auxiliary Space: O(1)

we already covered the iterative version above,
Now let us see its recursive approach as well,

Recursive Approach :
1) Create a dummy node and create a link from dummy node to head node. i.e, dummy->next = head
2) Then we will use the recursion stack to keep track of elements that are being pushed in recursion calls.
3) While popping the elements from recursion stack, we will decrement the N(position of target node from the end of linked list) i.e, N = N-1.
4) When we reach (N==0) that means we have reached at the target node,
5) But here is the catch, to delete the target node we require its previous node,
6) So we will now stop when (N==-1) i.e, we reached the previous node.
7) Now it is very simple to delete the node by using previousNode->next = previousNode->next->next.

C++

// C++ implementation of the approach
// Code is contributed by Paras Saini
#include <bits/stdc++.h>
using namespace std;
class LinkedList {
public:
    int val;
    LinkedList* next;
 
    LinkedList()
    {
        this->next = NULL;
        this->val = 0;
    }
    LinkedList(int val)
    {
        this->next = NULL;
        this->val = val;
    }
 
    LinkedList* addNode(int val)
    {
        if (this == NULL) {
            return new LinkedList(val);
        }
        else {
            LinkedList* ptr = this;
            while (ptr->next) {
                ptr = ptr->next;
            }
            ptr->next = new LinkedList(val);
            return this;
        }
    }
 
    void removeNthNodeFromEndHelper(LinkedList* head,
                                    int& n)
    {
        if (!head)
            return;
        // Adding the elements in the recursion
        // stack
        removeNthNodeFromEndHelper(head->next, n);
        // Popping the elements from recursion stack
        n -= 1;
        // If we reach the previous of target node
        if (n == -1){
            LinkedList* temp = head->next;
            head->next = head->next->next;
            free (temp);
        }
    }
 
    LinkedList* removeNthNodeFromEnd(int n)
    {
        // return NULL if we have NULL head or only
        // one node.
        if (!this or !this->next)
            return NULL;
 
        // Create a dummy node and point its next to
        // head.
        LinkedList* dummy = new LinkedList();
        dummy->next = this;
 
        // Call function to remove Nth node from end
        removeNthNodeFromEndHelper(dummy, n);
 
        // Return new head i.e, dummy->next
        return dummy->next;
    }
 
    void printLinkedList()
    {
        if (!this) {
            cout << "Empty List\n";
            return;
        }
        LinkedList* ptr = this;
        while (ptr) {
            cout << ptr->val << " ";
            ptr = ptr->next;
        }
        cout << endl;
    }
};
 
class TestCase {
private:
    void printOutput(LinkedList* head)
    {
        // Output:
        if (!head)
            cout << "Empty Linked List\n";
        else
            head->printLinkedList();
    }
    void testCase1()
    {
        LinkedList* head = new LinkedList(1);
        head = head->addNode(2);
        head = head->addNode(3);
        head = head->addNode(4);
        head = head->addNode(5);
        head->printLinkedList(); // Print: 1 2 3 4 5
        head = head->removeNthNodeFromEnd(2);
        printOutput(head); // Output: 1 2 3 5
    }
 
    void testCase2()
    {
        // Important Edge Case, where linkedList [1]
        // and n=1,
        LinkedList* head = new LinkedList(1);
        head->printLinkedList(); // Print: 1
        head = head->removeNthNodeFromEnd(2);
        printOutput(head); // Output: Empty Linked List
    }
 
    void testCase3()
    {
        LinkedList* head = new LinkedList(1);
        head = head->addNode(2);
        head->printLinkedList(); // Print: 1 2
        head = head->removeNthNodeFromEnd(1);
        printOutput(head); // Output: 1
    }
 
public:
    void executeTestCases()
    {
        testCase1();
        testCase2();
        testCase3();
    }
};
 
int main()
{
    TestCase testCase;
    testCase.executeTestCases();
    return 0;
}

Java

import java.util.*;
 
class LinkedList {
    public int val;
    public LinkedList next;
 
    // Constructor to create the first node
    public LinkedList(int val) {
        this.val = val;
        this.next = null;
    }
 
    // Method to add nodes to the linked list
    public LinkedList addNode(int val) {
        LinkedList node = new LinkedList(val);
        if (this.next == null) {
            this.next = node;
        } else {
            this.next.addNode(val);
        }
        return this;
    }
 
    // Method to print the linked list
    public void printLinkedList() {
        LinkedList node = this;
        while (node != null) {
            System.out.print(node.val + " ");
            node = node.next;
        }
        System.out.println();
    }
 
    // Method to remove the nth node from the end of the linked list
    public LinkedList removeNthNodeFromEnd(int n) {
        LinkedList dummy = new LinkedList(0);
        dummy.next = this;
        LinkedList first = dummy;
        LinkedList second = dummy;
 
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }
 
        while (first != null) {
            first = first.next;
            second = second.next;
        }
 
        second.next = second.next.next;
        return dummy.next;
    }
}
 
class Main {
    public static void main(String[] args) {
        LinkedList list = new LinkedList(1);
        list.addNode(2).addNode(3).addNode(4).addNode(5);
        list.printLinkedList(); // Print: 1 2 3 4 5
        list.removeNthNodeFromEnd(2);
        list.printLinkedList(); // Output: 1 2 3 5
 
        // Edge case where linked list has only one node
        LinkedList list2 = new LinkedList(1);
        list2.printLinkedList(); // Print: 1
        list2.removeNthNodeFromEnd(1);
        if (list2 == null || list2.next == null) {
            System.out.println("Empty Linked List");
        } else {
            list2.printLinkedList();
        }
 
        LinkedList list3 = new LinkedList(1);
        list3.addNode(2);
        list3.printLinkedList(); // Print: 1 2
        list3.removeNthNodeFromEnd(1);
        list3.printLinkedList(); // Output: 1
    }
}

Python3

# Python code addition
 
# class of linked list
class LinkedList:
    # Constructor to create the first node
    def __init__(self, val):
        self.val = val
        self.next = None
 
    # Method to add nodes to the linked list
    def addNode(self, val):
        node = LinkedList(val)
        if self.next is None:
            self.next = node
        else:
            self.next.addNode(val)
        return self
 
    # Method to print the linked list
    def printLinkedList(self):
        node = self
        while node is not None:
            print(node.val, end=" ")
            node = node.next
        print()
 
    # Method to remove the nth node from the end of the linked list
    def removeNthNodeFromEnd(self, n):
        dummy = LinkedList(0)
        dummy.next = self
        first = dummy
        second = dummy
 
        for i in range(n+1):
            first = first.next
 
        while first is not None:
            first = first.next
            second = second.next
 
        second.next = second.next.next
        return dummy.next
 
 
list = LinkedList(1)
list.addNode(2).addNode(3).addNode(4).addNode(5)
list.printLinkedList()  # Print: 1 2 3 4 5
list.removeNthNodeFromEnd(2)
list.printLinkedList()  # Output: 1 2 3 5
 
# Edge case where linked list has only one node
list2 = LinkedList(1)
list2.printLinkedList()  # Print: 1
list2.removeNthNodeFromEnd(1)
if list2 is None or list2.next is None:
    print("Empty Linked List")
else:
    list2.printLinkedList()
 
list3 = LinkedList(1)
list3.addNode(2)
list3.printLinkedList()  # Print: 1 2
list3.removeNthNodeFromEnd(1)
list3.printLinkedList()  # Output: 1
 
# The code is contributed by Nidhi goel. 

C#

using System;
 
// Class of linked list
public class LinkedList {
    // Constructor to create the first node
    public int Val
    {
        get;
        set;
    }
    public LinkedList Next
    {
        get;
        set;
    }
 
    public LinkedList(int val)
    {
        Val = val;
        Next = null;
    }
 
    // Method to add nodes to the linked list
    public LinkedList AddNode(int val)
    {
        LinkedList node = new LinkedList(val);
        if (Next == null) {
            Next = node;
        }
        else {
            Next.AddNode(val);
        }
        return this;
    }
 
    // Method to print the linked list
    public void PrintLinkedList()
    {
        LinkedList node = this;
        while (node != null) {
            Console.Write(node.Val + " ");
            node = node.Next;
        }
        Console.WriteLine();
    }
 
    // Method to remove the nth node from the end of the
    // linked list
    public LinkedList RemoveNthNodeFromEnd(int n)
    {
        LinkedList dummy = new LinkedList(0);
        dummy.Next = this;
        LinkedList first = dummy;
        LinkedList second = dummy;
 
        for (int i = 0; i <= n; i++) {
            first = first.Next;
        }
 
        while (first != null) {
            first = first.Next;
            second = second.Next;
        }
 
        second.Next = second.Next.Next;
        return dummy.Next;
    }
}
 
class Program {
    static void Main()
    {
        LinkedList list = new LinkedList(1);
        list.AddNode(2).AddNode(3).AddNode(4).AddNode(5);
        list.PrintLinkedList(); // Print: 1 2 3 4 5
        list.RemoveNthNodeFromEnd(2);
        list.PrintLinkedList(); // Output: 1 2 3 5
 
        // Edge case where linked list has only one node
        LinkedList list2 = new LinkedList(1);
        list2.PrintLinkedList(); // Print: 1
        LinkedList result = list2.RemoveNthNodeFromEnd(1);
        if (result == null || result.Next == null) {
            Console.WriteLine("Empty Linked List");
        }
        else {
            result.PrintLinkedList();
        }
 
        LinkedList list3 = new LinkedList(1);
        list3.AddNode(2);
        list3.PrintLinkedList(); // Print: 1 2
        list3.RemoveNthNodeFromEnd(1);
        list3.PrintLinkedList(); // Output: 1
    }
}

Javascript

// Javascript code addition
 
// class of linked list
class LinkedList {
  // Constructor to create the first node
  constructor(val) {
    this.val = val;
    this.next = null;
  }
 
  // Method to add nodes to the linked list
  addNode(val) {
    const node = new LinkedList(val);
    if (this.next === null) {
      this.next = node;
    } else {
      this.next.addNode(val);
    }
    return this;
  }
 
  // Method to print the linked list
  printLinkedList() {
    let node = this;
    while (node !== null) {
      process.stdout.write(node.val + " ");
      node = node.next;
    }
    console.log();
  }
 
  // Method to remove the nth node from the end of the linked list
  removeNthNodeFromEnd(n) {
    const dummy = new LinkedList(0);
    dummy.next = this;
    let first = dummy;
    let second = dummy;
 
    for (let i = 0; i <= n; i++) {
      first = first.next;
    }
 
    while (first !== null) {
      first = first.next;
      second = second.next;
    }
 
    second.next = second.next.next;
    return dummy.next;
  }
}
 
const list = new LinkedList(1);
list.addNode(2).addNode(3).addNode(4).addNode(5);
list.printLinkedList(); // Print: 1 2 3 4 5
list.removeNthNodeFromEnd(2);
list.printLinkedList(); // Output: 1 2 3 5
 
// Edge case where linked list has only one node
const list2 = new LinkedList(1);
list2.printLinkedList(); // Print: 1
list2.removeNthNodeFromEnd(1);
if (list2 === null || list2.next === null) {
  console.log("Empty Linked List");
} else {
  list2.printLinkedList();
}
 
const list3 = new LinkedList(1);
list3.addNode(2);
list3.printLinkedList(); // Print: 1 2
list3.removeNthNodeFromEnd(1);
list3.printLinkedList(); // Output: 1
 
// The code is contributed by Nidhi goel.

Output

1 2 3 4 5 
1 2 3 5 
1 
Empty Linked List
1 2 
1

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

// 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.
    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;
    }
};
 
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->deleteNthNodeFromEnd(l->head, 2);
 
    cout << "*********** Linked List after Deletion *****"
         << endl;
    l->display();
 
    return 0;
}
 
// This code is contributed by lokesh (lokeshmvs21).

Java

// 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).

Python

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#

// 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).

Javascript

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

Time complexity: O(n)

Space complexity: O(1) using constant space

Suggest improvement

Move last m elements to the front of a given Linked List

Split into K subarrays to minimize the maximum sum of all subarrays

Share your thoughts in the comments

Delete Nth node from the end of the given linked list

C++

Java

Python3

C#

Javascript

C++

C

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?