C++程序 在链表中删除节点

链表是一种常见的数据结构，它由一个个节点组成，每个节点存储了数据和指向下一个节点的指针。链表具有插入和删除节点比较灵活的特点，因此被广泛应用于各种算法和应用中。本文将介绍如何使用C++编写在链表中删除节点的程序。

1. 链表概述

在编写程序之前，我们需要了解一些基本的链表概念。一个链表可以由一个指针指向它的头节点来表示。每个节点包含数据和指向下一个节点的指针。如果一个节点的指针指向空值，则表示该节点为链表的末尾。

链表的遍历通常使用一个循环来完成，循环变量为指向当前节点的指针。在遍历过程中，我们可以通过“指针所指向的节点的指针”来改变链表的结构，以实现插入和删除操作。

2. 链表节点的定义

在开始编写程序之前，我们需要先定义一个链表节点的结构体。该结构体包含一个数据成员和一个指向下一个节点的指针成员。我们在这里定义了一个整型链表节点结构体，代码如下：

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

代码分析：

• struct ListNode：定义了一个链表节点的结构体。
• int val：链表节点中的数据成员，值为整型。
• ListNode* next：链表节点中的指向下一个节点的指针成员，类型为指向 ListNode 结构体的指针。
• ListNode(int x) : val(x), next(nullptr) {}：构造函数，用来初始化链表节点。其中 x 为传入的值，指定了链表节点的值；next 的值初始化为 nullptr，表示该节点没有下一个节点。

3. 删除链表中的节点

删除链表中的节点是一种常见的链表操作。假设我们要从链表中删除一个节点 node，则需要将其前驱节点 prev 的 next 指针修改为 node 的 next 指针。这样，node 就从链表中删除了。

在代码中，我们可以定义一个删除链表中的指定节点的函数。该函数需要两个参数：链表头指针 head 和需要删除的节点 node。具体实现代码如下：

class Solution {
public:
    void deleteNode(ListNode* head, ListNode* node) {
        if (!head || !node) return;

        if (node->next) {
            ListNode* next = node->next;
            node->val = next->val;
            node->next = next->next;
            delete next;
        } else if (head == node) {
            delete head;
            head = nullptr;
        } else {
            ListNode* cur = head;
            while (cur->next != node) {
                cur = cur->next;
            }
            cur->next = nullptr;
            delete node;
        }
    }
};

代码分析：

• Solution：定义了一个 C++ 类，包含了链表中删除节点的函数。
• ListNode* head：链表头指针。
• ListNode* node：需要删除的节点。
• if (!head || !node) return;：判断链表头和需要删除的节点是否为空。如果其中有空指针，则直接返回。
• if (node->next)：判断需要删除的节点是否为末尾节点。如果不是，则将当前节点的值覆盖为后继节点的值，然后将当前节点的 next 指针指向后继节点的后继节点，最后删除后继节点。
• else if (head == node)：判断需要删除的节点是否为头节点。如果是，则直接删除该节点并将头指针赋值为 nullptr。
• else：需要删除的节点为末尾节点且不是头节点。此时，我们需要遍历整个链表找到当前节点的前驱节点，然后将其 next 指针指向 nullptr，最后删除当前节点。

4. 示例代码

现在，我们将编写一个用于测试的示例代码，并演示如何使用上述的 deleteNode 函数来删除链表中的节点。我们先创建一个包含十个节点的链表，然后调用 deleteNode 函数删除其中的一个节点。

#include <iostream>

using namespace std;

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

class Solution {
public:
    void deleteNode(ListNode* head, ListNode* node) {
        if (!head || !node) return;

        if (node->next) {
            ListNode* next = node->next;
            node->val = next->val;
            node->next = next->next;
            delete next;
        } else if (head == node) {
            delete head;
            head = nullptr;
        } else {
            ListNode* cur = head;
            while (cur->next != node) {
                cur = cur->next;
            }
            cur->next = nullptr;
            delete node;
        }
    }
};

int main() {
    ListNode* head = new ListNode(1);
    ListNode* cur = head;
    for (int i = 2; i <= 10; i++) {
        cur->next = new ListNode(i);
        cur = cur->next;
    }
    cout << "Before deletion: ";
    cur = head;
    while (cur) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;

    Solution solution;
    ListNode* nodeToDelete = head->next->next; // 删除第三个节点
    solution.deleteNode(head, nodeToDelete);

    cout << "After deletion: ";
    cur = head;
    while (cur) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;

    return 0;
}

代码分析：

• main 函数：创建一个包含十个节点的链表，并调用 deleteNode 函数删除其中的一个节点。最后，输出删除节点之前和之后的链表节点值。
• cout：输出流对象，用于在终端输出信息。
• ListNode* head = new ListNode(1);：创建头结点。
• for (int i = 2; i <= 10; i++)：用循环创建包含十个节点的链表。
• cout << "Before deletion: ";：输出删除之前的链表节点值。
• ListNode* nodeToDelete = head->next->next;：指定需要删除的节点为第三个节点。
• solution.deleteNode(head, nodeToDelete);：调用 deleteNode 函数删除指定节点。
• cout << "After deletion: ";：输出删除之后的链表节点值。

运行上述代码，输出为：

Before deletion: 1 2 3 4 5 6 7 8 9 10 
After deletion: 1 2 4 5 6 7 8 9 10 

我们可以看到，在删除链表中的指定节点之后，链表中的节点已经发生了变化。

结论

通过本文的介绍，我们了解了如何用 C++ 编写一个在链表中删除指定节点的程序。在编写程序之前，我们需要了解链表的基本概念，然后定义链表节点的结构体。接着，我们可以编写一个删除节点的函数，通过修改链表节点的指针来实现删除操作。

在编写程序时，我们需要注意链表中节点的指针以及空指针的情况。同时，我们需要在删除节点后及时释放内存，以避免内存泄漏的问题。