# 0019. Remove Nth Node From End of List
Link: https://leetcode.com/problems/remove-nth-node-from-end-of-list/
###### tags: `Leetcode` `Medium` `Linked List`
## 思路
### 思路一
首先遍历一次，得到整个linked list的长度，然后再遍历一次找到要删的node的前面那一个，将它的next赋值成它的next的next
为了避免a list with only one node, or removing the head of the list，在开头加了一个dummy node在head前面，因此return的时候只要return dummy.next就可以
### 思路二
Maintain two pointers and update one with a delay of n steps.
## Code in Java
### 思路二

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int num = 0;
        ListNode faster = head;
        ListNode slower = head;
        ListNode dummyNode = new ListNode(0, head);
        ListNode prev = dummyNode;
        while(faster!=null){
            if(num >= n){
                prev = slower;
                slower = slower.next;
            }
            faster = faster.next;
            num++;
        }
        prev.next = slower.next;
        return dummyNode.next;
    }
}

## Code in C++
### 思路一

/**
 * 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* dummy = new ListNode;
        dummy->next = head;
        ListNode* first = head;
        int length = 0;
        while(first != nullptr){
            length++;
            first = first->next;
        }
        length-=n;
        first = dummy;
        for(int i = 0;i < length;i++){
            first = first->next;
        }
        first->next = first->next->next;
        return dummy->next;
    }
};

### 思路二

/**
 * 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* dummy = new ListNode;
        dummy->next = head;
        ListNode* first = dummy;
        ListNode* second = dummy;
        for(int i = 0; i <= n; i++){
            first = first->next;
        }
        while(first != nullptr){
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        return dummy->next;
    }
};

## Result
### 思路一
Runtime: 4 ms, faster than **80.41%** of C++ online submissions for Remove Nth Node From End of List.
Memory Usage: 10.7 MB, less than **20.00%** of C++ online submissions for Remove Nth Node From End of List.
### 思路二
Runtime: 4 ms, faster than **80.41%** of C++ online submissions for Remove Nth Node From End of List.
Memory Usage: 10.5 MB, less than **94.40%** of C++ online submissions for Remove Nth Node From End of List.