19. Remove Nth Node From End of List

📘 題目敘述

給定一個 linked list 的頭節點 head，請刪掉倒數第 n 個節點，並回傳刪除後的 linked list 頭節點。

條件限制

linked list 的節點數量為 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

🧠 解題思路

我這份寫法是先把 linked list 長度算出來，然後把問題轉成「刪掉正數第幾個節點」。

因為如果整條 linked list 長度是 len，那倒數第 n 個節點，其實就是正數第 len - n + 1 個節點。所以我先掃一次 linked list，算出總長度，再用 len - n 找到「要刪除節點的前一個位置」。

接著分兩種情況：

如果要刪的是第一個節點，就直接回傳 head->next
否則就走到目標節點前一個位置，把指標接過去，跳過那個節點

所有變數

len：linked list 的長度，後面也會拿來轉成刪除位置前一格還要走幾步
p：第一次走訪 linked list 時計算長度用的指標
q：第二次走訪 linked list 時，用來走到要刪除節點前一個位置的指標

🪜 主要流程步驟

1. 先掃一次 linked list，算出總長度

我先用一個指標 p 從 head 開始往後走，順便把長度 len 累加起來：

int len = 0;
ListNode* p = head;
while (p) {
    p = p->next;
    len++;
}

這一步做完之後，我就知道整條 linked list 一共有幾個節點。

2. 把倒數第 `n` 個轉成前面要走幾步

接著我做：

len = len - n;

這裡的意思不是直接得到「第幾個節點要刪」，而是得到：

在刪除目標之前，前面還有幾個節點

也就是等等我要走到「目標節點前一個位置」時，還需要往後走多少步。

3. 如果 `len == 0`，代表要刪掉第一個節點

如果總長減掉 n 之後變成 0，就表示倒數第 n 個節點其實就是整條 linked list 的第一個節點。

例如：

長度是 5
n = 5

那倒數第 5 個就是正數第一個。

所以這時候不用再往後找，直接把頭節點刪掉就好：

if (len == 0) {
    return head->next;
}

也就是回傳原本第二個節點，讓它變成新的 head。

4. 否則就走到目標節點的前一個位置

如果不是刪第一個節點，我就用另一個指標 q 從 head 開始走：

ListNode* q = head;
while (len > 1) {
    q = q->next;
    len--;
}

這段的目的是把 q 停在「要刪掉的那個節點的前一個位置」。

因為等等真正要做刪除時，我不是直接操作目標節點本身，而是要改前一個節點的 next。

5. 把目標節點跳過去

當 q 已經停在目標前一個位置後，我就做：

q->next = q->next->next;

這一行的意思是：

原本 q->next 指向要刪掉的節點
現在改成直接指向那個節點的下一個節點

這樣中間那個節點就會被跳過，相當於從 linked list 中移除了。

6. 最後回傳原本的 head

如果刪的不是第一個節點，那整條 linked list 的頭都沒有改變，所以最後直接回傳原本的 head 就可以。

⏱️ 複雜度

設 linked list 長度為 n。

時間複雜度：O(n) 我先掃一次算長度，再掃一次找到刪除位置，整體仍然是線性時間。
空間複雜度：O(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) {
        int len = 0; // link list長度
        ListNode* p = head;
        while (p) {
            p = p->next;
            len++;
        }

        len = len - n;
        if (len == 0) {  //刪除第一個
            return head->next;
        }
        ListNode* q = head;
        while (len > 1) {
            q = q->next;
            len--;
        }
        q->next = q->next->next;
        return head;
    }
};

🔗 題目連結

https://leetcode.com/problems/remove-nth-node-from-end-of-list/