C++怎么移除链表倒数第N个节点

在C++中，链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的操作包括插入、删除、查找等。本文将详细介绍如何在C++中移除链表的倒数第N个节点。

1. 链表的基本概念

链表是一种线性数据结构，它由节点组成，每个节点包含两部分：数据域和指针域。数据域用于存储数据，指针域用于指向下一个节点。链表的第一个节点称为头节点，最后一个节点称为尾节点，尾节点的指针域通常指向nullptr。

链表可以分为单链表、双链表和循环链表等。单链表的每个节点只有一个指针域，指向下一个节点；双链表的每个节点有两个指针域，分别指向前一个节点和后一个节点；循环链表的尾节点指向头节点，形成一个环。

2. 移除链表倒数第N个节点的思路

要移除链表的倒数第N个节点，我们需要找到该节点的前一个节点，然后将其指针域指向该节点的下一个节点。具体步骤如下：

1. 计算链表的长度：首先遍历链表，计算链表的长度len。
2. 找到要删除的节点的前一个节点：倒数第N个节点的位置是len - N，我们需要找到第len - N - 1个节点。
3. 删除节点：将第len - N - 1个节点的指针域指向第len - N + 1个节点，从而跳过第len - N个节点。

需要注意的是，如果要删除的节点是头节点，我们需要特殊处理。

3. 实现代码

下面是一个完整的C++代码示例，展示了如何移除链表的倒数第N个节点。

#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* toDelete = second->next;
        second->next = second->next->next;
        delete toDelete;

        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 创建链表

在main函数中，我们创建了一个包含5个节点的链表，节点的值分别为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);

4.2 移除倒数第N个节点

removeNthFromEnd函数是核心部分，它使用双指针技巧来找到倒数第N个节点的前一个节点，并删除该节点。

1. 创建虚拟头节点：为了避免处理头节点的特殊情况，我们创建一个虚拟头节点dummy，并将其next指针指向链表的头节点。

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

2. 初始化双指针：first和second指针都指向虚拟头节点。

   ListNode* first = dummy;
   ListNode* second = dummy;
   

3. 移动first指针：让first指针先走n+1步，这样first和second指针之间就相隔n个节点。

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

4. 同时移动first和second指针：当first指针到达链表末尾时，second指针正好指向倒数第n+1个节点。

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

5. 删除节点：将second指针的next指向second->next->next，从而跳过倒数第n个节点。

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

6. 返回结果：返回虚拟头节点的next指针，即新的链表头节点。

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

4.3 打印链表

printList函数用于打印链表的所有节点值，方便我们查看链表的内容。

void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        std::cout << current->val << " ";
        current = current->next;
    }
    std::cout << std::endl;
}

4.4 释放链表内存

在main函数的最后，我们释放链表的内存，避免内存泄漏。

while (head != nullptr) {
    ListNode* temp = head;
    head = head->next;
    delete temp;
}

5. 总结

本文详细介绍了如何在C++中移除链表的倒数第N个节点。通过使用双指针技巧，我们可以在一次遍历中找到要删除的节点，并高效地完成删除操作。这种方法的时间复杂度为O(L)，其中L是链表的长度，空间复杂度为O(1)。希望本文对你理解链表的操作有所帮助。