單向鏈表倒數第 M 個節點：一次遍歷雙指標法

題目

給定單向鏈表，找出倒數第 m 個節點（m >= 1）。要求：變數命名清晰、註解完整、時間/空間複雜度最優、可編譯執行。

直觀但低效的做法

先遍歷一次求長度 n，再遍歷找第 n-m+1 個節點。需兩次遍歷，且依賴「求長度」這獨立操作，內聚性不足。

最佳解：雙指標單次遍歷

1. 指標 p 先走 m 步，指向第 m 個節點。
2. 指標 pR 指向頭節點。
3. 兩指標同步前進，直到 p 走到尾端（NULL）。
4. 此時 pR 即為倒數第 m 個節點。
5. 若 m 超過鏈表長度，pR 仍為 NULL，表示不存在。

時間複雜度 O(n)，空間複雜度 O(1)，只需一次遍歷，高內聚。

C++ 範本實作

template <typename T>
struct Node {
    T data;
    Node* next;
};

template <typename T>
Node<T>* ReverseFind(Node<T>* head, size_t m) {
    size_t n = 0;
    Node<T> *p = head, *pR = nullptr;

    for (; p; p = p->next) {
        if (++n == m) {
            pR = head;
            continue;
        }
        if (pR) pR = pR->next;
    }
    return pR; // 若 m 超界，回傳 nullptr
}

關鍵細節

• 使用 size_t 避免負數邏輯錯誤。
• pR 初始為 nullptr，僅當 p 走完 m 步後才啟動，巧妙處理邊界。
• 回傳原始指標，呼叫端需自行判斷 nullptr。