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;
}