Leetcode – Remove Nth Node From End

Name: Remove Nth Node From End of List
Difficulty: Medium
Description: Remove the nth node from the end of the list, return the list

Example:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Input: head = [1], n = 1
Output: []

Input: head = [1,2], n = 1
Output: [1]

Tried to do this in one pass. Essentially push the items into a vector, delete the nth node, make sure n-1->next = nth->next. Guard against the edge cases. The list is mutated in place. If a nullptr is returned, the list will have been deleted, otherwise the client assumes ownership.

ListNode* removeNthFromEnd(ListNode* head, int n) {
    if (n == 1 && head->next == nullptr) {
        delete head;
        return nullptr;
    }

    auto node{head};

    vector<ListNode*> nodes;

    while (node != nullptr) {
        nodes.push_back(node);
        node = node->next;
    }

    int size = (int)nodes.size();
    int i = size - n;

    if (i == 0) {
        if (size == 1) {
            delete head;
            return nullptr;
        }

        head = nodes[0]->next;
        delete nodes[0];
        return head;
    }

    nodes[i - 1]->next = nodes[i]->next;
    delete nodes[i];

    return head;
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s