# 19. Remove Nth Node From End of List

## 程式碼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 *dummy = new ListNode;
        dummy -> next = head;
        vector <ListNode*> v;
        ListNode *current = dummy;
        while (current != nullptr) {
            v.push_back(current);
            current = current -> next;
        }
        v.push_back(nullptr);
        int idx = v.size() - 2 - n + 1;
        v[idx - 1] -> next = v[idx + 1];
        delete v[idx];
        head = dummy -> next;
        delete dummy;
        return head;
    }
};

## 演算法(快慢指標)

1. 定義dummy指標，dummy->next指向head
2. 定義兩個指標ptr1與ptr2，先讓ptr1往前到索引為n的節點(設dummy節點索引為0)，ptr2指向dummy，prev
3. 當ptr1 != nullptr:
    3.1. prev = ptr2
    3.2. ptr2 = ptr2->next
    3.3. ptr1 = ptr1->next
4. prev->next指向ptr2->next
5. 刪除ptr2
6. head指向dummy->next
7. 刪除dummy
8. 回傳head

## 演算法正確性證明
以下說的索引都是概念上的，實際上鏈結串列不會有索引
循環不變式(第3行)：在每次迴圈開始前：
1. ptr1在ptr2以後n個節點，也就是說，ptr1的索引-ptr2的索引=n。
2. prev都在ptr2的上一個節點，除了第一次以外。

1. 在第2行時，ptr1與ptr2的距離是n，所以1成立。
2. prev是空指標(第一次不算)，所以2成立。

1. 根據循環不變式，ptr1的索引-ptr2的索引=n，此時執行3.2、3.3後，會讓ptr1與ptr2各往前一步，所以仍然1成立。
2. 第一次執行迴圈會讓2成立，而根據循環不變式，往後的prev在ptr2的上一個節點，所以執行3.1、3.2後，2仍然成立。

當迴圈終止時，ptr1會是nullptr(索引視為size+1)，根據循環不變式，ptr1的索引-ptr2的索引=n，此時的ptr2索引會是size+1-n，也就是倒數第n個節點，也就是我們要刪除的節點，此時因為迴圈至少會執行一次(下面有證明)，所以prev不為空，根據循環不變式的第2點，是倒數第n+1個節點，也就是ptr2的上一個節點。

再來只要執行4,5,6,7,8，就會刪除倒數第n個節點

---

proof：使用矛盾證法，假設迴圈什麼都沒做就跳出來，代表一開始ptr1=nullptr，而nullptr索引可以視為size+1，所以n=size+1，其中size是節點數量，要刪除倒數第n個節點，但根據題意，n最大到size而已(假如有5個節點，題目不可能說要刪除倒數第6個節點)，所以假設錯誤，這代表迴圈至少會執行一次，完成證明。

## 程式碼

/**
 * 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 *ptr1 = dummy, *ptr2 = dummy, *prev;
        int idx = 0;
        while (idx < n) {
            ptr1 = ptr1 -> next;
            idx++;
        }
        while (ptr1 != nullptr) {
            prev = ptr2;
            ptr2 = ptr2 -> next;
            ptr1 = ptr1 -> next;
        }
        prev -> next = ptr2 -> next;
        delete ptr2;
        head = dummy -> next;
        delete dummy;
        return head;
    }
};