C++程序删除链表

链表是一种常用的数据结构，它可以动态地添加或删除元素。在链表上进行删除操作是比较常见的操作之一。本文将介绍如何写一个C++程序来删除链表。

链表的定义

链表由节点组成，每个节点包含数据和指向下一个节点的指针。通常用一个指向第一个节点的指针来表示整个链表。

下面是链表节点的定义：

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

删除链表节点

删除链表节点有两种情况：删除链表中的某个节点和删除链表中所有值为特定值的节点。下面将分别介绍如何实现这两个操作。

删除链表中的某个节点

要删除链表中的某个节点，需要首先找到该节点，然后修改该节点的前一个节点的指针，使其指向该节点的下一个节点。最后将该节点删除即可。

下面是删除链表中某个节点的代码：

void deleteNode(ListNode* node) {
    node->val = node->next->val;    //将要删除节点的下一个节点的值覆盖到要删除的节点上
    node->next = node->next->next;  //将下一个节点删除
}

在该函数中，我们先将要删除节点的下一个节点的值覆盖到要删除的节点上，然后将下一个节点删除。这样做的原因是我们无法直接修改要删除节点的前一个节点的指针，因此我们需要将要删除节点的下一个节点的值覆盖到要删除的节点上，并将下一个节点删除。

删除链表中所有值为特定值的节点

要删除链表中所有值为特定值的节点，需要遍历整个链表，找到值为给定值的节点，并删除它们。

下面是删除链表中所有值为特定值的节点的代码：

ListNode* removeElements(ListNode* head, int val) {
    ListNode dummy(INT_MAX);
    dummy.next = head;
    ListNode* prev = &dummy;
    ListNode* cur = head;
    while (cur != NULL) {
        if (cur->val == val) {
            prev->next = cur->next;
            delete cur;
            cur = prev->next;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return dummy.next;
}

在该函数中，我们创建了一个虚拟头节点dummy，然后遍历整个链表，找到值为给定值的所有节点，并将它们删除。要删除节点，我们需要修改其前一个节点的指针，并将其删除。

完整代码

#include <iostream>
using namespace std;

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

void deleteNode(ListNode* node) {
    node->val = node->next->val;    //将要删除节点的下一个节点的值覆盖到要删除的节点上
    node->next = node->next->next;  //将下一个节点删除
}

ListNode* removeElements(ListNode* head, int val) {
    ListNode dummy(INT_MAX);
    dummy.next = head;
    ListNode* prev = &dummy;
    ListNode* cur = head;
    while (cur != NULL) {
        if (cur->val == val) {
            prev->next = cur->next;
            delete cur;
            cur = prev->next;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
    return dummy.next;
}

int main() {
    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);
    head->next->next->next->next->next = new ListNode(6);

    cout << "Before removing node:";
    ListNode* cur = head;
    while (cur != NULL) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;

    deleteNode(head->next->next);
    cout << "After removing node: ";
    cur = head;
    while (cur != NULL) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;

    ListNode* newHead = removeElements(head, 2);
    cout << "After removing all nodes with value 2: ";
    cur = newHead;
    while (cur != NULL) {
        cout << cur->val << " ";
        cur = cur->next;
    }
    cout << endl;

    return 0;
}

在主函数中，我们创建了一个包含6个节点的链表。然后我们通过调用deleteNode函数删除了链表中的一个节点，并通过调用removeElements函数删除了所有值为2的节点。最后，我们输出了去除节点后的链表。