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)。