# 19 - Remove Nth Node From End of List

Concept

解法一 - 走兩次，O(1) 記憶體空間

可以先走過一次 list 看總長度 len 是多少，接下來就再走一次，直到走到 len-n 的地方就可以把 node 刪掉。

缺點是要走過兩次才能完成。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head) return NULL;

        int len = 0;
        ListNode* ptr = head;

        while(ptr != NULL) {
            len++;
            ptr = ptr->next;
        }

        ListNode dummy = ListNode(0);
        dummy.next = head;
        ptr = &dummy;

        for(int i=0; i<len-n; i++){
            ptr = ptr->next;
        }

        ptr->next = ptr->next->next;
        return dummy.next;
    }
};

在寫這個解法的程式碼時，一開始很容易遇到

[1]
1

這個 case 過不了的情況，在這種情況下我們可以用 dummy 來解決，附上過不了的程式碼：

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        int len = 0;
        ListNode* ptr = head;

        while(ptr != NULL) {
            len++;
            ptr = ptr->next;
        }

        ptr = head;

        for(int i=0; i<len-n-1; i++){
            ptr = ptr->next;
        }

        ptr->next = ptr->next->next; //ptr->next->next 是 NULL->next
        return head;
    }
};

結果如下：

解法二 - 走一次，O(n) 記憶體空間

可以先走過一次，把所有 node 都存到一個 vector 裡面，然後把 vector.size()-n 這個 node 移除掉。（方法就是把 size-n-1 的 next 指到 size-n+1 的 node）

缺點是要額外花 O(n) 的記憶體空間。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head) return NULL;

        vector<ListNode*> nodes;
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        nodes.push_back(dummy);

        ListNode* ptr = head;
        while(ptr) {
            nodes.push_back(ptr);
            ptr = ptr->next;
        }

        nodes[nodes.size()-1-n]->next = nodes[nodes.size()-1-n]->next->next;
        return dummy->next;
    }
};

解法三 - 走一次，且只需 O(1) 記憶體空間

我們可以用兩個 pointer，讓兩個 pointer 之間差 n 個 nodes，這樣當走較多的那個 pointer 走到底時，就可以把走較慢的那個 pointer 刪掉。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* slow = dummy;
        ListNode* fast = dummy;

        // Let fast go n+1 step forward 
        // (when fast reach NULL, slow will be the node before the len-n th one)
        for(int i=0; i<n+1; i++) {
            fast = fast->next;
        }

        // Move slow and fast together until fast is at the tail
        while(fast) {
            fast = fast->next;
            slow = slow->next;
        }

        slow->next = slow->next->next;
        return dummy->next;
    }
};