單向鏈表找倒數第 N 節點：雙指針法與長度法完整解析

問題描述

給定單向鏈表頭節點 head 與整數 n，找出倒數第 n 個節點 (即正數第 size - n + 1 個)。要求單次遍歷、O(1) 空間。

方法一：雙指針 (快慢指針) —— 推薦

核心思想： 讓快指針 q 先走 n 步，再與慢指針 p 同步前進。當 q 抵達尾部，p 恰好位於倒數第 n 節點。

C/C++ 實作

struct Node { int val; Node* next; };

Node* findNthToLast(Node* head, int n) {
    if (!head || n < 1) return nullptr;

    Node *p = head, *q = head;
    // q 先走 n 步
    for (int i = 0; i < n; ++i) {
        if (!q) return nullptr; // 鏈表長度 < n
        q = q->next;
    }
    // 同步前進
    while (q) {
        p = p->next;
        q = q->next;
    }
    return p;
}

Java 實作

class ListNode { int val; ListNode next; }

public ListNode nthToLast(ListNode head, int n) {
    if (head == null || n < 1) return null;

    ListNode p1 = head, p2 = head;
    // p2 先走 n-1 步 (或 n 步，視邊界定義)
    for (int i = 0; i < n - 1; ++i) {
        if (p2 == null) return null;
        p2 = p2.next;
    }
    // 同步直到 p2 到達最後一個節點
    while (p2.next != null) {
        p1 = p1.next;
        p2 = p2.next;
    }
    return p1;
}

方法二：先算長度再定位

思想： 先遍歷一次得長度 len，倒數第 n 即正數第 len - n + 1 個，再走一次。

// 概略碼
int len = 0;
for (Node* cur = head; cur; cur = cur->next) len++;
if (n > len) return null;
int target = len - n + 1;
Node* cur = head;
for (int i = 1; i < target; ++i) cur = cur->next;
return cur;