19. Remove Nth Node From End of List

# Medium

Key idea: Two methods.

1. Two pass method: get the legnth of the linklist, then remove (l-n)th from beginning. Time = $O(l+l-n)=O(l).$

2. One pass method: two pointers, the first ptr is n ahead of the second ptr, once first ptr reach the end, remove second ptr->next. Time = $O(l)$ .

C++(method 1)

/**
 * 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 l = 0;
        while(node) {
            node = node->next;
            l ++;
        }
        
        // edge case
        if(l == n) {
            head = head->next;
            return head;
        }
        node = head;
        for(int i = 0; i < l-n-1; i ++) {
            node = node->next;
        }
        node->next = node->next->next;
        return head;
    }
};

C++(method 2)

/**
 * 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 *dump = new ListNode(-1), *first, *second;
        dump->next = head;
        first = dump;
        second = dump;
        while(n) {
            first = first->next;
            n --;
        }
        
        while(first->next) {
            first = first->next;
            second = second->next;
        }
        
        second->next = second->next->next;
        return dump->next;
    }
};

In method 2, must set dump node to avoid the mistake when deleting the head node.

In these two methods, pay attention to the case of deleting the head node.