題目 19：「移除鏈結串列的倒數第 N 個節點 (Remove Nth Node From End of List)」是一道鏈結串列操作問題，主要目標是從單向鏈結串列中移除倒數第 N 個節點，並回傳修改後的鏈結串列。

題目：

給定一個鏈結串列，移除鏈結串列的倒數第 n 個節點，並回傳該鏈結串列的頭節點。

範例：

1. 輸入：head = [1,2,3,4,5], n = 2

   • 輸出：[1,2,3,5]

2. 輸入：head = [1], n = 1

   • 輸出：[]

3. 輸入：head = [1,2], n = 1

   • 輸出：[1]

解題思路

最直覺就是迴圈掃一遍計算有幾個，然後第二次迴圈掃到第k-n個，再移除它，
假設掃到k=5,要移除倒數n=1個,那麼就是移除第k-n=4個，但有沒有更好的方式掃一遍就完成了呢?

那就是使用雙指標法，也就是快慢指標，一開始讓快指標先走 n 步，然後快慢指標在一起走，直到快指標走到最後一個節點，那慢指標的下一個即倒數第 n 個節點。

邊界處理？使用虛擬節點來解決 head 節點只有一個且 n = 1 要刪除 head 節點問題。刪除節點記得要delete釋放記憶體。

實作：

/**
 * 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(0); // 虛擬頭節點，避免刪除頭節點的特殊情況
        dummy.next = head;

        ListNode* slow = &dummy;
        ListNode* fast = &dummy;

        // 快指標先走 n 步
        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }

        // 快慢指標一起走，直到快指標走到最後一個節點，
        // 那慢指標的下個節點即倒數第 n 個節點
        while (fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }

        // 刪除倒數第 n 個節點
        ListNode* tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp; // 釋放被刪除節點的記憶體

        return dummy.next;
    }
};

小提醒：

• 迭代到 fast nullptr 時，那樣 slow 就剛好在倒數 n 節點上，那這樣就不好刪除 slow 這個節點，所以要在前一個節點就停下來。
• 寫成 ListNode* dummy = new ListNode(); 的話就要記得釋放記憶體，否則寫成區域變數讓它自己回收。

參考：
#19. Remove Nth Node From End of List