Remove nth node from end of list

Difficulty: Medium, Asked-in: Amazon

Key takeaway: An excellent problem for beginners to learn problem-solving with linked lists. This blog will guide you to work efficiently with linked lists and deal with pointers.

Let’s understand the problem

Write a program to remove the Nth node from the end of the linked list, i.e., when the node is traversed from the end, delete the Nth node from there.

Example 1

Input: 1->2->3->4->5, N = 2, Output: 1->2->3->5

Example 2

Input: 7->8->4->5->3, N = 1, Output: 7->8->4->5

Discussed solution approaches

An iterative approach using double scan
An iterative approach using two pointers

Iterative approach using double scan

Solution idea

If M is the length of the linked list, then the Nth node from the end is the (M - N + 1)th node from the beginning. So we can modify the problem to remove the (M − N + 1)th node from the beginning of the list.

Solution steps

Traverse the linked list and find the length M.
Traverse the linked list again from the start until we reach the (M − N)th node.
Now, we delete the (M - N + 1)th node and return the head pointer. Before deleting the node, we need to relink the next pointer of the (M - N)th node to the (M − N + 2)th node.

Solution code C++

struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int data)
    {
        val = data;
        next = NULL;
    }
};

ListNode* removeNthNodeListEnd(ListNode* head, int N) 
{
    if (head == NULL)
        return NULL;

    int length = 0;
    ListNode* temp = head;
    while (temp != NULL) 
    {
        length = length + 1;
        temp = temp->next;
    }
    
    length = length - N;
    if (length == 0) 
    {
        temp = head->next;
        head->next = NULL;
        delete(head);
        return temp;
    }
    
    ListNode* curr = head;
    ListNode* prev = NULL;
    
    while (length > 0) 
    {
        prev = curr;
        curr = curr->next;
        length = length - 1;
    }
    
    prev->next = curr->next;
    curr->next = NULL;
    delete(curr);
    return head;
}

Solution code Python

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

def removeNthNodeListEnd(head, N):
    if head is None:
        return None

    length = 0
    temp = head
    while temp is not None:
        length = length + 1
        temp = temp.next

    length = length - N
    if length == 0:
        temp = head.next
        head.next = None
        del head
        return temp

    curr = head
    prev = None
    while length > 0:
        prev = curr
        curr = curr.next
        length = length - 1

    prev.next = curr.next
    curr.next = None
    del curr
    return head

Solution code Java

class ListNode 
{
    int val;
    ListNode next;
    ListNode(int val) 
    {
        this.val = val;
        this.next = null;
    }
}

class Solution 
{
    public ListNode removeNthNodeListEnd(ListNode head, int N) 
    {
        if (head == null)
            return null;

        int length = 0;
        ListNode temp = head;
        while (temp != null) 
        {
            length = length + 1;
            temp = temp.next;
        }

        length = length - N;
        if (length == 0) 
        {
            temp = head.next;
            head.next = null;
            head = null;
            return temp;
        }

        ListNode curr = head;
        ListNode prev = null;
        while (length > 0) 
        {
            prev = curr;
            curr = curr.next;
            length = length - 1;
        }

        prev.next = curr.next;
        curr.next = null;
        curr = null;
        return head;
    }
}

Time and space complexity analysis

We are performing two traversals of the linked list: first, to calculate the length M of the list, and second, to find the (M − N)th node. There are 2M − N operations, so the time complexity in the worst case is O(M). Space complexity is O(1), as we are using constant space here.

An iterative approach using two pointers

Solution idea

The idea here is to use two pointers to find the (N + 1)th node from the end. In the beginning, the first pointer is at the (N + 1)th node from the start, and the second pointer is at the head of the linked list. By moving both pointers one step at a time until the first pointer reaches the end, the second pointer will point to the (N + 1)th node from the end, and we can easily remove the next node, which is the Nth node from the list end.

Solution steps

We initialize two pointers: firstPointer and secondPointer. Here, the secondPointer is at the first node of the linked list, and the firstPointer is at the (N + 1)th node from the beginning.
Now, both pointers are separated by N nodes. We maintain this constant gap and advance both pointers together until the firstPointer reaches the last node.
The secondPointer will now point to the (N + 1)th node from the end. We can remove the Nth node from the list end by relinking the next pointer of the secondPointer to the next pointer of the next node.

Solution code C++

struct ListNode
{
    int val;
    ListNode* next;
    ListNode(int data)
    {
        val = data;
        next = NULL;
    }
};

ListNode* removeNthNodeListEnd(ListNode* head, int N) 
{
    if (head == NULL)
        return NULL;
    
    ListNode* firstPointer = head;
    ListNode* secondPointer = head;
    for (int i = 1; i <= N; i = i + 1)
        firstPointer = firstPointer->next;
    
    if (firstPointer == NULL) 
    {
        ListNode* temp = head->next;
        head->next = NULL;
        delete(head);
        return temp;
    }
    
    while (firstPointer->next) 
    {
        firstPointer = firstPointer->next;
        secondPointer = secondPointer->next;
    }
    
    ListNode* temp = secondPointer->next;
    secondPointer->next = temp->next;
    delete(temp);
    return head;
}

Solution code Python

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

def removeNthNodeListEnd(head, N):
    if head is None:
        return None
    
    firstPointer = head
    secondPointer = head
    
    for i in range(1, N + 1):
        firstPointer = firstPointer.next
    
    if firstPointer is None:
        temp = head.next
        head.next = None
        del head
        return temp
    
    while firstPointer.next:
        firstPointer = firstPointer.next
        secondPointer = secondPointer.next
    
    temp = secondPointer.next
    secondPointer.next = temp.next
    del temp
    return head

Solution code Java

class ListNode 
{
    int val;
    ListNode next;
    ListNode(int val) 
    {
        this.val = val;
        this.next = null;
    }
}

class Solution 
{
    public ListNode removeNthNodeListEnd(ListNode head, int N) 
    {
        if (head == null)
            return null;
    
        ListNode firstPointer = head;
        ListNode secondPointer = head;
        for (int i = 1; i <= N; i = i + 1)
            firstPointer = firstPointer.next;
    
        if (firstPointer == null) 
        {
            ListNode temp = head.next;
            head.next = null;
            head = null;
            return temp;
        }
        
        while (firstPointer.next != null) 
        {
            firstPointer = firstPointer.next;
            secondPointer = secondPointer.next;
        }
        
        ListNode temp = secondPointer.next;
        secondPointer.next = temp.next;
        temp = null;
        return head;
    }
}

Time and space complexity analysis

If the length of the linked list is M, then the firstPointer will move M steps, and the secondPointer will move M - N steps. So, pointer movement = 2M - N, and time complexity = O(M). Space complexity = O(1) as we are using constant space.

Critical ideas to think!

What would be the best and worst-case scenarios for both approaches?
Both algorithms take O(M) time, but which one performs fewer operations in the worst-case scenario?
Sometimes, a "dummy" node is used to simplify some corner cases, such as a list with only one node or removing the head of the list. In other words, having dummy nodes in any kind of linked list, singly, double or circular, makes the corner cases vanish. Thus, programming becomes a lot easier. Now the critical question is: how do we use the idea of a dummy node in the above approaches to handle the corner cases?
In the 2nd approach, we use two loops: one for taking the firstPointer to the (N + 1)th node and the other for finding the (N+1)th node from the end. Can we merge these two processes and implement them using a single loop?
Can we try to solve this problem using recursion?
Can we implement the two-pointer solution differently?

Comparison of time and space complexities

Iterative approach using double scan: Time = O(M), Space = O(1)
Iterative approach using two pointers: Time = O(M), Space = O(1)

Remove nth node from end of list

Let’s understand the problem

Example 1

Example 2

Discussed solution approaches

Iterative approach using double scan

Solution idea

Solution steps

Solution code C++

Solution code Python

Solution code Java

Time and space complexity analysis

An iterative approach using two pointers

Solution idea

Solution steps

Solution code C++

Solution code Python

Solution code Java

Time and space complexity analysis

Critical ideas to think!

Comparison of time and space complexities

Suggested problems to practice

Share Your Insights

More from EnjoyAlgorithms

Self-paced Courses and Blogs

Coding Interview

Machine Learning

System Design

OOP Concepts

Our Newsletter