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

让我们来制定一个问题陈述，以了解删除过程。 给定一个关键字，“删除”链表中第一个这个关键字的出现 。

迭代方法：

要从链表中删除一个节点，我们需要执行以下步骤。

1）找到要删除的节点的前一个节点。

2）更改前一个节点的下一个节点。

3）释放要删除的节点的内存。

// 一个完整的可运行的C++程序，
// 演示单链表中的删除
#include <iostream>
 
using namespace std;
 
struct node
{
    int data;
    node *next;
};
 
class linked_list
{
private:
    node *head,*tail;
public:
    linked_list()
    {
        head = NULL;
        tail = NULL;
    }
 
    void add_node(int n)
    {
        node *tmp = new node;
        tmp->data = n;
        tmp->next = NULL;
 
        if(head == NULL)
        {
            head = tmp;
            tail = tmp;
        }
        else
        {
            tail->next = tmp;
            tail = tail->next;
        }
    }
 
    node* gethead()
    {
        return head;
    }
 
    static void display(node *head)
    {
        if(head == NULL)
        {
            cout << "NULL" << endl;
        }
        else
        {
            cout << head->data << endl;
            display(head->next);
        }
    }
 
    static void concatenate(node *a,node *b)
    {
        if( a != NULL && b!= NULL )
        {
            if (a->next == NULL)
                a->next = b;
            else
                concatenate(a->next,b);
        }
        else
        {
            cout << "Either a or b is NULL\n";
        }
    }
 
    void front(int n)
    {
        node *tmp = new node;
        tmp -> data = n;
        tmp -> next = head;
        head = tmp;
    }
 
    void after(node *a, int value)
    {
        node* p = new node;
        p->data = value;
        p->next = a->next;
        a->next = p;
    }
 
    void del (node *before_del)
    {
        node* temp;
        temp = before_del->next;
        before_del->next = temp->next;
        delete temp;
    }
};
 
int main()
{
    linked_list a;
    a.add_node(1);
    a.add_node(2);
    a.front(3);
    a.add_node(5);
    a.add_node(15);
    a.after(a.gethead()->next->next->next, 10);
    a.del(a.gethead()->next);
    linked_list::display(a.gethead());
    return 0;
}

输出

3
1
5
10
15
NULL

时间复杂度： O(n)，其中n表示给定链表的长度。

辅助空间： O(1)，不需要额外空间，因此是一个常数。

递归方法:

为了递归地删除链表的一个节点，我们需要执行以下步骤。

1.我们将node*（节点指针）作为函数的引用传递（如node* &head）。

2.现在，由于当前节点指针是从前一个节点的next派生的（它通过引用传递），因此现在如果当前节点指针的值已更改，则前一个next节点的值也会发生更改，这是删除节点所需的操作（即使前一个节点的下一个指向当前节点，包含关键字的下一个指向）。

3.查找包含给定值的节点。

4.存储此节点以稍后使用free()函数进行解除分配。

5. 改变该节点指针，使其指向其下一个节点，并通过此操作将上一个节点的下一个节点正确链接。

以下是上述方法的实现。

// C++递归删除单链表中的节点程序
#include <iostream>
 
// 节点结构
struct node{
    int data;
    struct node* next;
    node(int val){
        data = val;
        next = NULL;
    }
};

/*删除单链表的函数。我们将通过引用方式将head作为参数传递到函数中，
因为我们想要在从递归返回后永久将head的值设置为NULL*/
void delete_a_linked_list(struct node*& head){
    if(head == NULL){ // 到达链表尾部，返回！！
        return;
    }
    delete_a_linked_list(head->next);// 调用递归，精确到尾递归（tail recursion）
    std::cout<<"删除节点"<<head->data<<"\n"; // 在删除之前打印节点值
    free(head); // 从内存中释放节点，然后返回
    head = NULL; // 将指针指向NULL。
}

int main() {
    // 创建一个测试链表
    // 2->4->6->9->NULL
     
    struct node* head = new node(2);
    head->next = new node(4);
    head->next->next = new node(6);
    head->next->next->next = new node(9);
     
    // 调用函数
    delete_a_linked_list(head);
     
    if(head == NULL){
        std::cout<<"链表为空\n";
    }else{
        std::cout<<"链表不为空\n";
    }
         
    return 0;
}  

输出

删除节点9
删除节点6
删除节点4
删除节点2
The Linked List is empty

时间复杂度: O(n)，其中n表示给定链表的长度。

辅助空间: O(n)，由于递归调用栈，其中n表示给定链表的长度。