Remove Nth node from end of the Linked List

Last Updated : 04 Sep, 2024

Given a linked list. The task is to remove the N^th node from the end of the linked list.

Examples:

Input : LinkedList = 1 ->2 ->3 ->4 ->5 , N = 2
Output : 1 ->2 ->3 ->5
Explanation: Linked list after deleting the 2nd node from last which is 4, is 1 ->2 ->3 ->5

Input : LinkedList = 7 ->8 ->4 ->3 ->2 , N = 1
Output : 7 ->8 ->4 ->3
Explanation: Linked list after deleting the 1st node from last which is 2, is 7 ->8 ->4 ->3

Table of Content

[Expected Approach – 1] Find Equivalent node from Front – O(n) Time and O(1) Space
[Expected Approach – 2] Using Fast and Slow Pointer – O(n) Time and O(1) Space

[Expected Approach – 1] Find Equivalent node from Front – O(n) Time and O(1) Space:

To remove the Nth node from the end, first determine the length of the linked list. Then, delete the (length – N + 1)th node from the front.

Follow the steps below to solve the problem:

Traverse the linked list to calculate its length.
Compute the position to delete from the front : nodeToDelete = (length – N + 1).
If nodeToDelete is 1, update the head to the next of head node.
Traverse to the (target – 1)th node and update its next pointer to skip the target node.
Return the modified linked list.

Below is the implementation of the above approach:

C++

// C++ program to delete nth node from last
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int new_data) {
        data = new_data;
        next = nullptr;
    }
};

// Function to remove the Nth node from the end
Node* removeNthFromEnd(Node* head, int N) {
  
    // Calculate the length of the linked list
    int length = 0;
    Node* curr = head;
    while (curr != nullptr) {
        length++;
        curr = curr->next;
    }

    // Calculate the position to remove from front
    int target = length - N + 1;

    // If target is 1, remove the head node
    if (target == 1) {
        Node* newHead = head->next;
      
        // Free memory of the removed node
        delete head; 
        return newHead;
    }

    // Traverse to the node just before the target
    curr = head;
    for (int i = 1; i < target - 1; i++) {
        curr = curr->next;
    }

    // Remove the target node
    Node* nodeToDelete = curr->next;
    curr->next = curr->next->next;
    delete nodeToDelete;  

    return head;
}

void printList(Node* node) {
    Node* curr = node;
    while (curr != nullptr) {
        cout << " " << curr->data;
        curr = curr->next;
    }
}

int main() {
  
    // Create a hard-coded linked list: 
    // 1 -> 2 -> 3 -> 4 -> 5
    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);

    int N = 2;
    head = removeNthFromEnd(head, N);

    printList(head);  

    return 0;
}

// C program to delete nth node from last
#include <stdio.h>
#include <stdlib.h>

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

// Function to remove the Nth node from the end
struct Node* removeNthFromEnd(struct Node* head, int N) {
  
    // Calculate the length of the linked list
    int length = 0;
    struct Node* curr = head;
    while (curr != NULL) {
        length++;
        curr = curr->next;
    }

    // Calculate the position to remove from front
    int target = length - N + 1;

    // If target is 1, remove the head node
    if (target == 1) {
        struct Node* newHead = head->next;
      
        // Free memory of the removed node
        free(head);  
        return newHead;
    }

    // Traverse to the node just before the target
    curr = head;
    for (int i = 1; i < target - 1; i++) {
        curr = curr->next;
    }

    // Remove the target node
    struct Node* nodeToDelete = curr->next;
    curr->next = curr->next->next;
  
    // Free memory of the removed node
    free(nodeToDelete);  

    return head;
}

void printList(struct Node* node) {
    struct Node* curr = node;
    while (curr != NULL) {
        printf(" %d", curr->data);
        curr = curr->next;
    }
}

struct Node* createNode(int new_data) {
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = NULL;
    return new_node;
}

int main() {
  
    // Create a hard-coded linked list:
    // 1 -> 2 -> 3 -> 4 -> 5
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    int N = 2;  
    head = removeNthFromEnd(head, N);

    printList(head); 

    return 0;
}

Java

// Java program to delete nth node from last
class Node {
    int data;
    Node next;

    Node(int new_data) {
        data = new_data;
        next = null;
    }
}

// Class containing the function to remove Nth node from end
public class GfG {
  
    // Function to remove the Nth node from the end
    static Node removeNthFromEnd(Node head, int N) {
      
        // Calculate the length of the linked list
        int length = 0;
        Node curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        // Calculate the position to remove from front
        int target = length - N + 1;

        // If target is 1, remove the head node
        if (target == 1) {
            return head.next;
        }

        // Traverse to the node just before the target
        curr = head;
        for (int i = 1; i < target - 1; i++) {
            curr = curr.next;
        }

        // Remove the target node
        curr.next = curr.next.next;

        return head;
    }

    // This function prints the contents of the linked list
    static void printList(Node node) {
        Node curr = node;  
        while (curr != null) {
            System.out.print(" " + curr.data);
            curr = curr.next;
        }
    }

    public static void main(String[] args) {
      
        // Create a hard-coded linked list:
        // 1 -> 2 -> 3 -> 4 -> 5
        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);

        int N = 2; 
        head = removeNthFromEnd(head, N);

        printList(head);  
    }
}

Python

# Python3 program to delete nth node from last
class Node:
    def __init__(self, new_data):
        self.data = new_data
        self.next = None

# Given the head of a list, remove the Nth node from the end
def remove_nth_from_end(head, N):
  
    # Calculate the length of the linked list
    length = 0
    curr = head
    while curr is not None:
        length += 1
        curr = curr.next

    # Calculate the position to remove from the front
    target = length - N + 1

    # If target is 1, remove the head node
    if target == 1:
        return head.next

    # Traverse to the node just before the target node
    curr = head
    for _ in range(target - 2):
        curr = curr.next

    # Remove the target node
    curr.next = curr.next.next

    return head

def print_list(node):
    curr = node;
    while curr is not None:
        print(f" {curr.data}", end="")
        curr = curr.next
    print()

if __name__ == "__main__":
  
    # Create a hard-coded linked list:
    # 1 -> 2 -> 3 -> 4 -> 5
    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)

    N = 2  
    head = remove_nth_from_end(head, N)

    print_list(head)

// C# program to delete nth node from last
using System;

class Node {
    public int Data;
    public Node next;

    public Node(int newData) {
        Data = newData;
        next = null;
    }
}

// Class containing the function to remove the Nth node from
// end
class GfG {
    static Node RemoveNthFromEnd(Node head, int N) {

        // Calculate the length of the linked list
        int length = 0;
        Node curr = head;
        while (curr != null) {
            length++;
            curr = curr.next;
        }

        // Calculate the position to remove from the front
        int target = length - N + 1;

        // If target is 1, remove the head node
        if (target == 1) {
            return head.next;
        }

        // Traverse to the node just before the target node
        curr = head;
        for (int i = 1; i < target - 1; i++) {
            curr = curr.next;
        }

        // Remove the target node
        curr.next = curr.next.next;

        return head;
    }

    static void PrintList(Node node) {
        Node curr = node;
        while (curr != null) {
            Console.Write(" " + curr.Data);
            curr = curr.next;
        }
        Console.WriteLine();
    }

    static void Main() {

        // Create a hard-coded linked list:
        // 1 -> 2 -> 3 -> 4 -> 5
        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);

        int N = 2;
        head = RemoveNthFromEnd(head, N);

        PrintList(head);
    }
}

JavaScript

// Javascript program to delete nth node from last    
class Node {
    constructor(newData) {
        this.data = newData;
        this.next = null;
    }
}

// Given the head of a list, remove the Nth node from the end
function removeNthFromEnd(head, N) {
    
    // Calculate the length of the linked list
    let length = 0;
    let curr = head;
    while (curr !== null) {
        length++;
        curr = curr.next;
    }

    // Calculate the position to remove from the front
    let target = length - N + 1;

    // If target is 1, remove the head node
    if (target === 1) {
        return head.next;
    }

    // Traverse to the node just before the target node
    curr = head;
    for (let i = 1; i < target - 1; i++) {
        curr = curr.next;
    }

    // Remove the target node
    curr.next = curr.next.next;

    return head;
}

function printList(node) {
    let curr = node;
    while (curr !== null) {
        process.stdout.write(" " + curr.data);
        curr = curr.next;
    }
    console.log();
}

// Create a hard-coded linked list:
// 1 -> 2 -> 3 -> 4 -> 5
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);

let N = 2; 
head = removeNthFromEnd(head, N);

printList(head);

Output

 1 2 3 5

Time Complexity: O(2n), due to traversing the list twice (once for length calculation and once for node removal).
Auxiliary Space: O(1).

[Expected Approach – 2] Using Fast and Slow Pointer – O(n) Time and O(1) Space:

The idea is to first move the fast pointer N steps ahead, then move both fast and slow pointers together until fast reaches the end. The slow pointer will then be just before the node to be removed, allowing to update the next pointer to skip the target node.

Below is the implementation of the above approach:

C++

// C++ program to delete nth node from last
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;

    Node(int new_data) {
        data = new_data;
        next = nullptr;
    }
};

// Function to remove the Nth node from the end
Node* removeNthFromEnd(Node* head, int N) {
  
    // Initialize two pointers, fast and slow
    Node* fast = head;
    Node* slow = head;

    // Move fast pointer N steps ahead
    for (int i = 0; i < N; i++) {
        if (fast == nullptr) return head; 
        fast = fast->next;
    }

    // If fast is null, remove the head node
    if (fast == nullptr) {
        Node* newHead = head->next;
        delete head;
        return newHead;
    }

    // Move both pointers until fast reaches the end
    while (fast->next != nullptr) {
        fast = fast->next;
        slow = slow->next;
    }

    // Remove the Nth node from the end
    Node* nodeToDelete = slow->next;
    slow->next = slow->next->next;
    delete nodeToDelete;

    return head;
}


void printList(Node* node) {
    Node* curr = node;
    while (curr != nullptr) {
        cout << " " << curr->data;
        curr = curr->next;
    }
}

int main() {
  
    // Create a hard-coded linked list: 
    // 1 -> 2 -> 3 -> 4 -> 5
    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);

    int N = 2;
    head = removeNthFromEnd(head, N);

    printList(head);  

    return 0;
}

// C program to delete nth node from last
#include <stdio.h>
#include <stdlib.h>

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

// Function to remove the Nth node from the end
struct Node* removeNthFromEnd(struct Node* head, int N) {
  
    // Initialize two pointers, fast and slow
    struct Node* fast = head;
    struct Node* slow = head;

    // Move fast pointer N steps ahead
    for (int i = 0; i < N; i++) {
        if (fast == NULL) return head; 
        fast = fast->next;
    }

    // If fast is NULL, remove the head node
    if (fast == NULL) {
        struct Node* newHead = head->next;
        free(head);
        return newHead;
    }

    // Move both pointers until fast reaches the end
    while (fast->next != NULL) {
        fast = fast->next;
        slow = slow->next;
    }

    // Remove the Nth node from the end
    struct Node* nodeToDelete = slow->next;
    slow->next = slow->next->next;
    free(nodeToDelete);

    return head;
}

void printList(struct Node* node) {
    struct Node* curr = node;
    while (curr != NULL) {
        printf(" %d", curr->data);
        curr = curr->next;
    }
}

struct Node* createNode(int new_data) {
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = NULL;
    return new_node;
}

int main() {
  
    // Create a hard-coded linked list:
    // 1 -> 2 -> 3 -> 4 -> 5
    struct Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    int N = 2;  
    head = removeNthFromEnd(head, N);

    printList(head); 

    return 0;
}

Java

// Java program to delete nth node from last
class Node {
    int data;
    Node next;

    Node(int new_data) {
        data = new_data;
        next = null;
    }
}

// Class containing the function to remove Nth node from end
public class GfG {

    // remove the Nth node from last
    static Node removeNthFromEnd(Node head, int N) {
      
        // Initialize two pointers, fast and slow
        Node fast = head;
        Node slow = head;

        // Move fast pointer N steps ahead
        for (int i = 0; i < N; i++) {
            if (fast == null)
                return head; 
            fast = fast.next;
        }

        // If fast is null, remove the head node
        if (fast == null) {
            return head.next;
        }

        // Move both pointers until fast reaches the end
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // Remove the Nth node from the end
        slow.next = slow.next.next;

        return head;
    }

    // This function prints the contents of the linked list
    static void printList(Node node) {
        Node curr = node;
        while (curr != null) {
            System.out.print(" " + curr.data);
            curr = curr.next;
        }
    }

    public static void main(String[] args) {

        // Create a hard-coded linked list:
        // 1 -> 2 -> 3 -> 4 -> 5
        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);

        int N = 2;
        head = removeNthFromEnd(head, N);

        printList(head);
    }
}

Python

# Python3 program to delete nth node from last
class Node:
    def __init__(self, new_data):
        self.data = new_data
        self.next = None

# Given the head of a list, remove the Nth node from the end
def remove_nth_from_end(head, N):
  
    # Initialize two pointers, fast and slow
    fast = head
    slow = head

    # Move fast pointer N steps ahead
    for _ in range(N):
        if fast is None:
            return head  
        fast = fast.next

    # If fast is None, remove the head node
    if fast is None:
        return head.next

    # Move both pointers until fast reaches the end
    while fast.next is not None:
        fast = fast.next
        slow = slow.next

    # Remove the Nth node from the end
    slow.next = slow.next.next

    return head

def print_list(node):
    curr = node;
    while curr is not None:
        print(f" {curr.data}", end="")
        curr = curr.next
    print()

if __name__ == "__main__":
  
    # Create a hard-coded linked list:
    # 1 -> 2 -> 3 -> 4 -> 5
    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)

    N = 2  
    head = remove_nth_from_end(head, N)

    print_list(head)

// C# program to delete nth node from last
using System;

class Node {
    public int Data;
    public Node next;

    public Node(int newData) {
        Data = newData;
        next = null;
    }
}

// Class containing the function to 
// remove the Nth node from end
class GfG {
    static Node RemoveNthFromEnd(Node head, int N) {
      
        // Initialize two pointers, fast and slow
        Node fast = head;
        Node slow = head;

        // Move fast pointer N steps ahead
        for (int i = 0; i < N; i++) {
            if (fast == null) return head; 
            fast = fast.next;
        }

        // If fast is null, remove the head node
        if (fast == null) {
            return head.next;
        }

        // Move both pointers until fast reaches the end
        while (fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // Remove the Nth node from the end
        slow.next = slow.next.next;

        return head;
    }

    static void PrintList(Node node) {
        Node curr = node;
        while (curr != null) {
            Console.Write(" " + curr.Data);
            curr = curr.next;
        }
        Console.WriteLine();
    }

    static void Main() {
      
        // Create a hard-coded linked list:
        // 1 -> 2 -> 3 -> 4 -> 5
        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);

        int N = 2;
        head = RemoveNthFromEnd(head, N);

        PrintList(head);
    }
}

JavaScript

// JavaScript program to delete nth node from last    
class Node {
    constructor(newData) {
        this.data = newData;
        this.next = null;
    }
}

// Given the head of a list, remove the 
// Nth node from the end
function removeNthFromEnd(head, N) {
    
    // Initialize two pointers, fast and slow
    let fast = head;
    let slow = head;

    // Move fast pointer N steps ahead
    for (let i = 0; i < N; i++) {
        if (fast === null) return head; 
        fast = fast.next;
    }

    // If fast is null, remove the head node
    if (fast === null) {
        return head.next;
    }

    // Move both pointers until fast reaches the end
    while (fast.next !== null) {
        fast = fast.next;
        slow = slow.next;
    }

    // Remove the Nth node from the end
    slow.next = slow.next.next;

    return head;
}

function printList(node) {
    let curr = node;
    while (curr !== null) {
        process.stdout.write(" " + curr.data);
        curr = curr.next;
    }
    console.log();
}

// Create a hard-coded linked list:
// 1 -> 2 -> 3 -> 4 -> 5
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);

let N = 2; 
head = removeNthFromEnd(head, N);

printList(head);