# 19 Remove Nth Node From End of List

19 Remove Nth Node From End of List
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
Note:
• Given n will always be valid.
• Try to do this in one pass.
• This is a two pass algorithm O(2n) - as I have use the first pass to find the size of the linked list. Since n is reletive to the end, I the front of the linked list n is not known for me.
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *prev = nullptr;
// iterate to find size of LL
int size = 0;
int count = 0;
while (current != nullptr) {
size++;
current = current->next;
}
// size is one
if (size == 1) {
return nullptr;
}
// n is end
else if (n == 1) {
// iterate to end
while (current->next != nullptr) {
prev = current;
current = current->next;
}
prev->next = nullptr;
delete current;
}
// n is front
else if (n == size) {
delete current;
}
// n is front or in the middle
else {
// iterate to n
while (current != nullptr && count < size - n) {
prev = current;
current = current->next;
count++;
}
prev->next = current->next;
delete current;
}