C++ 單鏈表節點刪除完整實現與詳解

問題描述

在單鏈表中刪除指定值的節點是基礎操作。本文提供完整的 C++ 實現，包含節點定義、鏈表創建、遍歷輸出、查找節點與刪除節點四大核心功能。

數據結構定義

struct Node {
    int pos;           // 數據域
    Node *pNext;       // 指針域
    Node(int position = -1, Node *next = nullptr)
        : pos(position), pNext(next) {}
};

核心操作實現

1. 創建單鏈表（尾插法）

Node* CreateSingleList(int arr[], int n) {
    Node *head = new Node;        // 頭節點（不存數據）
    Node *temp = head;
    for (int i = 0; i < n; ++i) {
        Node *createNode = new Node(arr[i]);
        temp->pNext = createNode;
        temp = createNode;
    }
    return head;  // 返回頭節點
}

2. 遍歷輸出鏈表

void Print(Node *head) {
    while (head->pNext != nullptr) {
        cout << head->pNext->pos << " ";
        head = head->pNext;
    }
    cout << endl;
}

3. 查找指定值的節點

Node* FindNode(Node *head, int target) {
    while (head->pNext != nullptr) {
        if (head->pNext->pos == target) {
            return head->pNext;  // 返回目標節點指針
        }
        head = head->pNext;
    }
    return nullptr;  // 未找到
}

4. 刪除指定值的節點（核心邏輯）

void RemoveNode(Node *&head, int target) {
    Node *pre = head;          // 前驅節點
    Node *curr = head->pNext;  // 當前檢查節點

    // 尋找目標節點及其前驅
    while (curr != nullptr) {
        if (curr->pos == target) break;
        pre = curr;
        curr = curr->pNext;
    }

    // 若找到，進行刪除鏈接
    if (curr != nullptr) {
        pre->pNext = curr->pNext;  // 前驅跳過目標節點
        curr->pNext = nullptr;     // 斷開目標節點連接
        delete curr;               // 釋放內存（重要！）
    }
}

完整測試程序

int main() {
    const int N = 10;
    int arr[N];
    for (int i = 0; i < N; ++i) arr[i] = i + 1;  // 1~10

    Node *head = CreateSingleList(arr, N);

    Node *res = FindNode(head, 5);
    cout << "Find node: " << res->pos << endl;

    cout << "原鏈表: ";
    Print(head);

    RemoveNode(head, 1);  // 刪除頭部節點
    cout << "刪除 1 後: ";
    Print(head);

    // 記憶體釋放（簡略，實際應遍歷釋放所有節點）
    return 0;
}

關鍵點總結

• 頭節點設計：引入不存數據的頭節點，統一處理「刪除第一個節點」等邊界情況。
• 雙指針遍歷：pre 與 curr 同步前進，找到目標時 pre 即為前驅。
• 引用傳頭指針：Node *&head 允許修改主調函數的頭指針（雖本例不涉及頭節點刪除，但屬良好習慣）。
• 內存管理：刪除節點後務必 delete，避免內存洩漏。