Removing Nth Node From End of List

Arunima Mandal

Problem Statement: Given the head, remove the N-th node from the end of the list and return the head.

Note: The idea is pretty intuitive. We must iterate through the list starting from the head to know the size of the linked list. Knowing the size, we can iterate up to the node before the nth node. That way we can easily point towards the next node of the previous node of the “to-be-removed” node.

The only exception case is if we have to remove the head node. We just have to assign the head node to the next node of the head node.

Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *node=head;
        int sz=0;
        while(node)
        {
          node=node->next;
          sz++;
        }
        if(sz==n) //head to be deleted
        {
            ListNode *temp=head;
            head=head->next;
            delete temp;
            return head;
        }
        int i=0;
        node=head;
        int target=sz-n-1;
        while(i<target)
        {
          node=node->next;
          i++; 
        }
        ListNode *temp=node->next;
        node->next=node->next->next;
        delete temp;
        return head;
    }
};

Leave a comment