鏈表倒數第 N 節點查找：雙指針與計數法詳解

前言

在單向鏈表中尋找倒數第 N 個節點是經典面試題，主要有兩種解法：雙指針法與先計算長度再定位法。本文將詳細解析兩種思路的原理、代碼實現與複雜度比較。

方法一：雙指針法（一次遍歷）

核心思想

使用兩個指針 p 和 q，先讓 q 向前移動 n 步，然後 p 和 q 同步後移。當 q 到達鏈表尾部時，p 恰好指向倒數第 n 個節點。

C/C++ 實現

node* find_nth_to_last(node* head, int n) {
    if (head == NULL || n < 1) return NULL;
    node *p = head, *q = head;
    // q 先走 n 步
    while (q != NULL && n--) {
        q = q->next;
    }
    // 若 n >= 0 說明鏈表長度不足 n
    if (n >= 0) return NULL;
    // 同步移動
    while (p != NULL && q != NULL) {
        p = p->next;
        q = q->next;
    }
    return p;
}

Java 實現

public static LinkedListNode nthToLast(LinkedListNode head, int n) {
    if (head == null || n < 1) return null;
    LinkedListNode p1 = head, p2 = head;
    // p2 先走 n-1 步（因為包含頭節點）
    for (int i = 0; i < n - 1; i++) {
        if (p2 == null) return null; // 長度不足
        p2 = p2.next;
    }
    while (p2.next != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

複雜度分析

• 時間複雜度：O(L)，L 為鏈表長度，只需一次遍歷。
• 空間複雜度：O(1)，僅使用常數級額外空間。

方法二：計算長度法（兩次遍歷）

核心思想

先完整遍歷鏈表得到節點總數 m，倒數第 n 個節點即為正向第 m - n + 1 個節點，再從頭遍歷到該位置。

優缺點比較

總結

實際開發中推薦使用雙指針法，因其單次遍歷效率更高，且能體現指針操作技巧。掌握邊界條件處理（如 n 超過長度、鏈表為空）是關鍵。