題目網址：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/

題意：給一 linked list, 請刪除倒數第 n 個 node, 並返回 linked list 的 head。

進階：試著用一次掃描就完成。

Solution：

想法：利用 slow & fast pointers, 用 dummy 是因為有可能第一個 node 被刪, 所以需要有 ptr 指著第一個 node 的前一個 node。首先 fast 先從 head 走 n 步（讓 fast 領先）, 然後 slow 才從 dummy 開始往前走, 直到 fast 變成 NULL

  • 為什麼 fast 是初始化為 head, 而 slow 初始化為 dummy ?
    因為若 fast 和 slow 都初始化為 head, 則當 fast 為 NULL 時, slow 恰好在倒數第 n 個 node(因為 fast 領先 n 步), 但是我們是要刪除倒數第 n 個 node, 要取得的是倒數第 n 個 node 的前一個節點(倒數第 n + 1 的 node), 故讓 slow 在初始化時就慢 fast 一步, 讓 fast 領先 n + 1 步, 這樣 slow 最後才會是倒數第 n + 1 的 node
class Solution{
public:
    ListNode* removeNthFromEnd(ListNode* head, int n){
        ListNode *dummy = new ListNode(0, head);
        ListNode *slow = dummy, *fast = head;

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

        while (fast) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return dummy->next;
    }
};
  • time：$O(L)$ ➔ 遍歷 linked list, 其中 L 為 linked list 的長度
  • space：$O(1)$ ➔ 只需常數空間