Articles by FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
FavTutor
  • AI News
  • Data Structures
  • Web Developement
  • AI Code GeneratorNEW
  • Student Help
  • Main Website
No Result
View All Result
Articles by FavTutor
No Result
View All Result
Home Data Structures and Algorithms

Remove Nth Node From End of List (C++, Java, Python)

Jatin Chanana by Jatin Chanana
December 8, 2023
Reading Time: 9 mins read
Remove Nth Node From End of List
Follow us on Google News   Subscribe to our newsletter

A linked list operates as a chain of connected elements, with each element aware of the next one in line. In this article, we will explore different approaches to remove the nth node from the end of a linked list with implementation in C++, Java, and Python.

Removing the nth Node from the End of the List

When we discuss removing the nth element from the end of the linked list, we’re essentially targeting the element positioned at the nth spot when counting backward from the end of the list. In simpler terms, it’s like removing the element that holds the nth position from the list’s tail.

In this problem, we are given a linked list and a value of n and we have to remove a node that holds the nth position from the list’s tail.

Let us understand it better with an example:

List nodes = [1,2,3,4,5,6]
n = 2
Output = [1,2,3,4,6]

The second node from the end has a value of 5, we will remove that node. So our output list becomes [1,2,3,4,6].

Example of Remove Nth Node From End of List

Brute Force Approach

In the brute force approach to solve this problem, we have to first count the length of the linked list for this we have to traverse a linked list once to count the length and traverse again to delete the nth node, nth node from the last is the length – nth node from starting.

Steps to solve this problem:

  • In the first step, we will initialize a variable length to 0 and use a while loop to traverse the linked list and count the number of nodes. After this loop, the length will contain the total number of nodes in the linked list.
  • In the second step, we will create a dummy node with a value of 0 and set its next pointer to the head of the original linked list. This dummy node is used to simplify handling edge cases where the head of the list needs to be removed. 
create a dummy node
  • In this step, we will use a  loop to move the current pointer to the node just before the one to be removed. The loop runs for length – n iterations.
move the current pointer
  • Finally, we will adjust the next pointer of the current node to skip over the nth node, effectively removing it from the linked list. 
adjust the next pointer of the current node

The time complexity of the brute force approach is O(n), where n is the number of nodes in the linked list. The space complexity is O(1) as we haven’t used any additional space.

Two Pointer Approach

We can avoid the hassle of counting the length of the list by using the two-pointers. Two-Pointers are a good approach to removing the nth node from the end of a linked list. Let’s see the steps of how we can solve this problem:

  • We will create a new ListNode named ‘dummy’ with an empty value. Set the next ‘dummy’ to the head of the linked list.
create a dummy node
  • Now we will create two pointers, ‘fast’ and ‘slow’, both initially pointing to ‘dummy’.
create two pointers, 'fast' and 'slow'
  • Now we will Move the ‘fast’ pointer n steps ahead in the linked list.
Move the 'fast' pointer n steps
  • Now we will Move both ‘slow’ and ‘fast’ pointers until the fast’s next is not NULL
Move both 'slow' and 'fast' pointers
  • Now we will Remove the nth node from the end by adjusting pointers.
Remove the nth node from the end by adjusting pointers

C++ Code

Below is the C++ program to remove the nth node from end of a list:

#include <iostream>

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* removeNthFromEnd(ListNode* head, int n) {
    // Step 1: Create a new ListNode named 'start' with an empty value.
    ListNode* start = new ListNode(0);

    // Set the next 'start' to the head of the linked list.
    start->next = head;

    // Step 2: Create two pointers, 'fast' and 'slow', both initially pointing to 'start'.
    ListNode* fast = start;
    ListNode* slow = start;

    // Step 3: Move the 'fast' pointer n steps ahead in the linked list.
    for (int i = 0; i < n; i++) {
        fast = fast->next;
    }

    // Step 4: Move both 'slow' and 'fast' pointers until 'fast' reaches the end.
    while (fast->next != nullptr) {
        slow = slow->next;
        fast = fast->next;
    }

    // Step 5: Remove the nth node from the end by adjusting pointers.
    slow->next = slow->next->next;

    // Step 6: Return the modified linked list starting from 'start->next'.
    return start->next;
}

// Function to print the linked list
void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    // Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    head->next->next->next->next->next = new ListNode(6);

    std::cout << "Original Linked List: ";
    printList(head);

    int n = 2; // Example: Remove the 2nd node from the end

    // Remove the nth node from the end
    head = removeNthFromEnd(head, n);

    std::cout << "Modified Linked List: ";
    printList(head);

    return 0;
}

Python Code

Here is the Python program for our problem:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def removeNthFromEnd(head, n):
    # Step 1: Create a new ListNode named 'start' with an empty value.
    start = ListNode(0)
    # Set the next of 'start' to the head of the linked list.
    start.next = head

    # Step 2: Create two pointers, 'fast' and 'slow', both initially pointing to 'start'.
    fast = start
    slow = start

    # Step 3: Move the 'fast' pointer n steps ahead in the linked list.
    for _ in range(n):
        fast = fast.next

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

    # Step 5: Remove the nth node from the end by adjusting pointers.
    slow.next = slow.next.next

    # Step 6: Return the modified linked list starting from 'start.next'.
    return start.next

# Function to print the linked list
def printList(head):
    while head is not None:
        print(head.val, end=" ")
        head = head.next
    print()

# Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
head.next.next.next.next.next = ListNode(6)

print("Original Linked List:", end=" ")
printList(head)

n = 2  # Example: Remove the 2nd node from the end

# Remove the nth node from the end
head = removeNthFromEnd(head, n)

print("Modified Linked List:", end=" ")
printList(head)

Java Code

You can implement it in Java too:

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class RemoveNthFromEnd {

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        // Step 1: Create a new ListNode named 'start' with an empty value.
        ListNode start = new ListNode(0);
        // Set the next of 'start' to the head of the linked list.
        start.next = head;

        // Step 2: Create two pointers, 'fast' and 'slow', both initially pointing to 'start'.
        ListNode fast = start;
        ListNode slow = start;

        // Step 3: Move the 'fast' pointer n steps ahead in the linked list.
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

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

        // Step 5: Remove the nth node from the end by adjusting pointers.
        slow.next = slow.next.next;

        // Step 6: Return the modified linked list starting from 'start.next'.
        return start.next;
    }

    // Function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Creating a sample linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 6
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);

        System.out.print("Original Linked List: ");
        printList(head);

        int n = 2; // Example: Remove the 2nd node from the end

        // Remove the nth node from the end
        head = removeNthFromEnd(head, n);

        System.out.print("Modified Linked List: ");
        printList(head);
    }
}

Output:

Original Linked List: 1 2 3 4 5 6 
Modified Linked List: 1 2 3 4 6

The time complexity of this approach is O(n) as the code traverses the list once using two pointers (fast and slow) until the fast reaches the end. Here n is the number of nodes in the linked list.

The space complexity is O(1) as we haven’t used any extra space.

Here is a small comparative analysis of both approaches:

ApproachTime ComplexityDetails
Brute ForceO(n)First count the length of the linked list and delete the nth node from last, i.e., length – nth node from starting.
Two PointesO(n)Create a dummy node, and use two pointers, fast and slow to traverse the list and delete the nth node from last.

Conclusion

In conclusion, the article provides an overview of the “Remove Nth Node from End of List” leetcode problem in the context of a linked list. You can now easily implement both a naive brute-force approach and an optimized two-pointer approach.

ShareTweetShareSendSend
Jatin Chanana

Jatin Chanana

I am Jatin, a final-year undergraduate student with a keen interest in the field of software development. I possess a strong academic background and a deep passion for Data Structures, Algorithms, and Web Development.

RelatedPosts

validate ip address

Validate IP Address Problem ( C++, JAVA, Python)

April 3, 2025
Shortest Palindrome Problem

Shortest Palindrome Problem ( C++, JAVA, Python)

April 4, 2025
Zigzag Conversion Problem

Zigzag Conversion Problem (C++, Java, Python)

April 4, 2025
Next Right Pointers In Each Node

Populating Next Right Pointers In Each Node (with code)

March 27, 2024
Coin Change II

Coin Change II Problem (C++, Java, Python)

April 7, 2025

About FavTutor

FavTutor is a trusted online tutoring service to connects students with expert tutors to provide guidance on Computer Science subjects like Java, Python, C, C++, SQL, Data Science, Statistics, etc.

Categories

  • AI News, Research & Latest Updates
  • Trending
  • Data Structures
  • Web Developement
  • Data Science

Important Subjects

  • Python Assignment Help
  • C++ Help
  • R Programming Help
  • Java Homework Help
  • Programming Help

Resources

  • About Us
  • Contact Us
  • Editorial Policy
  • Privacy Policy
  • Terms and Conditions

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.

No Result
View All Result
  • AI News
  • Data Structures
  • Web Developement
  • AI Code Generator
  • Student Help
  • Main Website

Website listed on Ecomswap. © Copyright 2025 All Rights Reserved.