LeetCode 19. Remove Nth Node From End of List [Medium] [C++] 解題筆記

Given a linked list, remove the n-th node from the end of list and return its head.

EX:

        Given linked list: 1->2->3->4->5, and n = 2.

    After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
想法:
    這題很簡單，直接找到倒數第 n 個 node 移除就好了。比較困難的點在於 follow up，follow up 要求我們
只遍歷一次 list 就完成刪除工作，因此就不得不用些比較巧妙的方式拉，首先假設 list 長度為 l 移除倒數第 n 個 node
等價於移除第 l - n + 1 個 node，因此我們可以使用 Two Pointer 的技巧，定義兩個 pointers first 和 second，
先讓 first 遍歷 n - 1 個 node，之後在讓 second 與 first 同時遍歷直到 first 遍歷到 list 結尾，此時因為 first
已經遍歷了 n - 1 個 node，因此到結尾會在經過 l - (n - 1) = l - n + 1 個 node，有沒有注意到？ 這樣的話我們的 second
在 first 走到結尾的時候不就剛好走到第 l - n + 1 個 node 嗎？！！，這樣就可能在一次遍歷中完成了，最後還需要考慮一些 edge case，
首先因為我們若要刪除 node 必須知道該 node 的前一個 node，因此為了方便起見我們可以直接要刪除的 node 的前一個 node，
直接把他的 next 指標指向下下一個 node 就可完成刪除，因此我們實際上可以找第 l - n 個 node，而又因為被刪除的 node 有可能是
head 所以我們必須要額外多加一個 dummy node 在 head 之前，為了考慮到 head 被刪除的情況，我們可以從 dummy head 開始遍歷，
因此我們實際上 first 在一開始的時候必須先遍歷 n + 1 個 node，(n-1, +1 為了讓 second 停在 target 前一個, +1 因為從 dummy head
開始遍歷所以offset一個位置要多走一個node)，就可以同時考慮到 head 被刪除的情況了。

Complexity: O(n) time, O(1) space.
完整程式碼:
/* O(n) time
 * The idea is that the problem remove nth node from end is equivalent to remove L - n + 1 th 
 * (L is length of list) node from begin, for example we have one list 1->2->3->4->5 and n = 2, 
 * so we use two pointers and move first pointer to n - 1 th node from begin, 
 * then move two pointers together util first pointer reach end of list (second pointer from begin while first pointer from n - 1 th node), 
 * obviously first pointer need move L - n + 1 round to reach end of list, meanwhile seoncd will reach the L - n + 1 th which we exactly want to remove!
 */

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        auto prev = new ListNode(0);
        prev->next = head;
        auto second = prev;
        auto first = prev;
        for (int i = 1; i <= n + 1; i++) {
            first = first->next;
        }
        while (first != NULL) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        
        return prev->next;
    }
};