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) {
    // head is null
    if (!head) return head;

    ListNode *current = head;
    ListNode *prev = nullptr;

    // iterate to find size of LL
    int size = 0;
    int count = 0;

    while (current != nullptr) {
        size++;
        current = current->next;
    }    

    current = head;

    // size is one 
    if (size == 1) {
        delete head;
        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;
        return head;
    }

    // n is front 
    else if (n == size) {
        head = current->next;
        delete current;
        return head;
    }
    // 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;
    }

    return head;
}