Delete Nth node from the end of the given linked list

Problem Statement

The problem “Delete Nth node from the end of the given linked list”  states that you are given a linked list with some nodes. And now you need to remove nth node from the end of the linked list.

Example

2->3->4->5->6->7
delete 3rd node from last

2->3->4->6->7

Explanation: The 2nd node from the end is 6. so we will delete that. And after deleting the node we are left with the linked list shown in the output.

Approach

Linked List is a linear data structure that takes advantage of pointers. And this saves us great computation effort over an array of adding extra elements. Now the problem is to remove nth node from the linked list. Here I should tell you that you are not provided with the number of nodes in the linked list. So what approach should one pick to solve the problem? When we need to delete the nth node from the end of the linked list.

Naive Approach

A naive approach will be to first calculate or compute the length of the linked list. This way requires us to first run a loop until the end of the linked list. But how will calculation of the linked list will help in the removal of nth node from the end? To solve the problem we will first calculate the length of the linked list. Then we will subtract the given input from the length. Now we will simply delete the node at length-n distance from the head.

Optimized Approach

An optimized approach will be without calculating the size of the linked list. There is a trick to solve this problem. First, we traverse a node which has been initialized as the head until the nth node from the start. Now we are standing at a node that is at a distance equal to n from the start node (head). Then we initialize a new variable equal to head. Then start traversing both the nodes until the first node reaches the last node of linked list. At that time our second variable will be at the n+1th node from the end. Now you just need to remove the next node.

Code

C++ code to Delete Nth node from the end of the given linked list

#include <bits/stdc++.h>
using namespace std;

struct node{
  int data;
  node* next;
};

node* create(int data){
  node* tmp = new node();
  tmp->data = data;
  tmp->next = NULL;
  return tmp;
}

node* deleteNthNodeFromLast(node* head, int n){
    // first move ahead n nodes
    // then start traversing from the start until the end node
    // delete the temporary node
    node* cur = head;
    while(n--){
        cur = cur->next;
        if(!cur){
            cur = head;
            head = head->next;
            free(cur);
            return head;
        }
    }
    node* tmp = head;
    while(cur->next){
        tmp = tmp->next;
        cur = cur->next;
    }
    cur = tmp->next;
    tmp->next = tmp->next->next;
    return head;
}

int main(){
  // create a linked list
  node* head = new node();
  head = create(2);
  head->next = create(3);
  node* toBeDeleted = create(4);
  head->next->next = toBeDeleted;
  head->next->next->next = create(5);
  head->next->next->next->next = create(6);
  head->next->next->next->next->next = create(7);

  cout<<"Old Linked List: ";
  node* tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
  head = deleteNthNodeFromLast(head, 3);

  cout<<endl<<"New Linked List: ";
  tmp = head;
  while(tmp!=NULL){
    cout<<tmp->data<<" ";
    tmp = tmp->next;
  }
}

Old Linked List: 2 3 4 5 6 7
New Linked List: 2 3 4 6 7

Java code to Delete Nth node from the end of the given linked list

import java.util.*;
class node{
    int data;
    node next;
}

class Main{
    static node create(int data){
        node tmp = new node();
        tmp.data = data;
        tmp.next = null;
        return tmp;
    }

    static node deleteNthNodeFromLast(node head, int n){
        // first move ahead n nodes
        // then start traversing from the start until the end node
        // delete the temporary node
        node cur = head;
        while(n-- > 0){
            cur = cur.next;
            if(cur == null){
                cur = head;
                head = head.next;
                return head;
            }
        }
        node tmp = head;
        while(cur.next != null){
            tmp = tmp.next;
            cur = cur.next;
        }
        cur = tmp.next;
        tmp.next = tmp.next.next;
        return head;
    }

    public static void main(String[] args){
        // create a linked list
        node head = new node();
        head = create(2);
        head.next = create(3);
        head.next.next = create(4);
        head.next.next.next = create(5);
        head.next.next.next.next = create(6);
        head.next.next.next.next.next = create(7);

        System.out.print("Old Linked List: ");
        node tmp = head;
        while(tmp != null){
            System.out.print(tmp.data+" ");
            tmp = tmp.next;
        }
        head = deleteNthNodeFromLast(head, 3);

        System.out.print("\n"+"New Linked List: ");
        tmp = head;
        while(tmp!=null){
            System.out.print(tmp.data+" ");
            tmp = tmp.next;
        }
    }
}

Old Linked List: 2 3 4 5 6 7 
New Linked List: 2 3 4 6 7

Complexity Analysis

Time Complexity

O(N), because we have traversed through the whole of the linked list which will cost us linear time complexity.

Space Complexity

O(1), because we have just stored some constant variables the space complexity required is constant.