C++ 鏈表節點刪除與鏈表反轉完整實現指南

前言

鏈表是數據結構中的基礎，掌握節點刪除與鏈表反轉是 C++ 程式設計的必修課。本文將從節點定義出發，詳細講解「刪除第 n 個節點」與「原地反轉鏈表」的正確實現，並指出常見錯誤與修正方案。

1. 節點結構定義

由於 C++ 標準庫無內建節點類型，需自行定義：

struct Node {
    int data;
    Node* next;
    Node(int val, Node* nxt = nullptr) : data(val), next(nxt) {}
    ~Node() { /* 可選：釋放資源 */ }
};

2. 刪除第 n 個節點 (1-based 索引)

常見錯誤：頭節點刪除導致外部指針失效

若函數參數為 Node* first (值傳遞)，函數內修改 first 不會影響調用端的頭指針。解決方法：傳遞 指針的引用 Node*& first 或 二級指針 Node** first。

正確實現 (引用傳遞版)

bool eraseNth(Node*& head, int n) { // n 從 1 開始
    if (!head || n < 1) return false;
    if (n == 1) {
        Node* del = head;
        head = head->next;
        delete del;
        return true;
    }
    Node* cur = head;
    for (int i = 1; i < n - 1 && cur; ++i) cur = cur->next;
    if (!cur || !cur->next) return false; // 越界
    Node* del = cur->next;
    cur->next = del->next;
    delete del;
    return true;
}

3. 原地反轉單鏈表

要求：不創建新節點，僅重設指針方向，使原尾節點成為新頭節點。

迭代法 (推薦，O(1) 空間)

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* curr = head;
    while (curr) {
        Node* nxt = curr->next; // 暫存下一節點
        curr->next = prev;        // 反轉指針
        prev = curr;              // 前移 prev
        curr = nxt;               // 前移 curr
    }
    return prev; // 新頭節點
}

遞歸法 (簡潔但 O(n) 棧空間)

Node* reverseRec(Node* head) {
    if (!head || !head->next) return head;
    Node* newHead = reverseRec(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

4. 完整可運行示例

#include <iostream>
using namespace std;

struct Node { int data; Node* next; Node(int v, Node* n=nullptr):data(v),next(n){} };

void print(Node* h) { while(h){cout<<h->data<<' ';h=h->next;} cout<<'\n'; }

int main() {
    // 建立 3->2->1
    Node* head = new Node(3, new Node(2, new Node(1)));
    cout << "原鏈表: "; print(head); // 3 2 1

    eraseNth(head, 2); // 刪除第 2 個 (值為 2)
    cout << "刪除後: "; print(head); // 3 1

    head = reverseList(head); // 反轉
    cout << "反轉後: "; print(head); // 1 3

    // 釋放記憶體 (略)
    return 0;
}

關鍵點總結

• 刪除頭節點必須用 Node*& 或 Node** 修改外部頭指針。
• 反轉時 三指針法 (prev, curr, next) 最穩健，避免斷鏈。
• 記得在適當時機 delete 被移除節點，防止記憶體洩漏。