19. Remove Nth Node From End of List

解題思路

不用 reverse 就能刪倒數第  n 個節點，只要用 two pointer。left pointer 跟 right pointer 不是平常的差一個，而是差 n 個節點。如此一來，當 right pointer 指向 null 時，left pointer 指到的恰好就是我們想要刪掉的節點。

但真正方便的是指向要刪掉的前一個節點，這樣才能進行刪除。為了達成此目標，選擇 left node 一開始指向 dummy node。

程式碼

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummy = new ListNode();
        ListNode *left = dummy, *right = head;
        dummy->next = head;

        for(int i=0; i<n; i++)
            right = right->next;
        
        while(right != nullptr)
        {
            left = left->next;
            right = right->next;
        }
        left->next = left->next->next;
        return dummy->next;
    }
};