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)

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.