C++如何實現移除鏈表倒數第N個節點

C++如何實現移除鏈表倒數第N個節點

在C++中，鏈表是一種常見的數據結構，它由一系列節點組成，每個節點包含數據和指向下一個節點的指針。鏈表的一個常見操作是移除鏈表中的某個節點。本文將詳細介紹如何在C++中實現移除鏈表倒數第N個節點的操作。

1. 鏈表的基本結構

首先，我們需要定義鏈表節點的結構。在C++中，鏈表節點通常定義為一個結構體或類，包含數據成員和指向下一個節點的指針。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

在這個定義中，ListNode結構體包含一個整數val和一個指向下一個節點的指針next。構造函數用于初始化節點的值和指針。

2. 移除鏈表倒數第N個節點的思路

要移除鏈表倒數第N個節點，我們需要找到該節點的前一個節點，然后將其next指針指向該節點的下一個節點。具體步驟如下：

1. 計算鏈表的長度：首先遍歷鏈表，計算鏈表的長度len。
2. 確定要移除的節點的位置：倒數第N個節點相當于正數第len - N + 1個節點。
3. 找到要移除的節點的前一個節點：遍歷鏈表，找到第len - N個節點。
4. 移除節點：將第len - N個節點的next指針指向第len - N + 2個節點，從而跳過第len - N + 1個節點。

3. 實現代碼

下面是一個完整的C++實現代碼：

#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* first = dummy;
        ListNode* second = dummy;
        
        // 讓first指針先走n+1步
        for (int i = 1; i <= n + 1; i++) {
            first = first->next;
        }
        
        // 同時移動first和second指針，直到first到達鏈表末尾
        while (first != nullptr) {
            first = first->next;
            second = second->next;
        }
        
        // 移除倒數第n個節點
        ListNode* temp = second->next;
        second->next = second->next->next;
        delete temp;
        
        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};

// 輔助函數：打印鏈表
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

int main() {
    // 創建鏈表 1->2->3->4->5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    std::cout << "原始鏈表: ";
    printList(head);
    
    Solution solution;
    int n = 2;
    head = solution.removeNthFromEnd(head, n);
    
    std::cout << "移除倒數第" << n << "個節點后的鏈表: ";
    printList(head);
    
    // 釋放鏈表內存
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    
    return 0;
}

4. 代碼解析

4.1 創建虛擬頭節點

在removeNthFromEnd函數中，我們創建了一個虛擬頭節點dummy，并將其next指針指向鏈表的頭節點head。這樣做的好處是可以簡化邊界條件的處理，例如當需要移除的節點是頭節點時。

ListNode* dummy = new ListNode(0);
dummy->next = head;

4.2 使用雙指針找到要移除的節點

我們使用兩個指針first和second，初始時都指向虛擬頭節點dummy。首先讓first指針向前移動n+1步，然后同時移動first和second指針，直到first指針到達鏈表末尾。此時，second指針指向倒數第n+1個節點，即要移除的節點的前一個節點。

for (int i = 1; i <= n + 1; i++) {
    first = first->next;
}

while (first != nullptr) {
    first = first->next;
    second = second->next;
}

4.3 移除節點

找到要移除的節點的前一個節點后，我們將其next指針指向要移除節點的下一個節點，從而跳過要移除的節點。然后釋放要移除的節點的內存。

ListNode* temp = second->next;
second->next = second->next->next;
delete temp;

4.4 返回結果

最后，我們返回虛擬頭節點的next指針，即移除節點后的鏈表頭節點。同時，釋放虛擬頭節點的內存。

ListNode* result = dummy->next;
delete dummy;
return result;

5. 測試代碼

在main函數中，我們創建了一個鏈表1->2->3->4->5，并調用removeNthFromEnd函數移除倒數第2個節點。然后打印移除節點后的鏈表。

int main() {
    // 創建鏈表 1->2->3->4->5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    std::cout << "原始鏈表: ";
    printList(head);
    
    Solution solution;
    int n = 2;
    head = solution.removeNthFromEnd(head, n);
    
    std::cout << "移除倒數第" << n << "個節點后的鏈表: ";
    printList(head);
    
    // 釋放鏈表內存
    while (head != nullptr) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    
    return 0;
}

6. 總結

本文詳細介紹了如何在C++中實現移除鏈表倒數第N個節點的操作。通過使用雙指針技巧，我們可以在一次遍歷中找到要移除的節點，并高效地完成移除操作。這種方法的時間復雜度為O(L)，其中L是鏈表的長度，空間復雜度為O(1)。