C++程序 在给定约束条件下删除链表中给定节点

给定一个单向链表，编写一个函数来删除给定节点。您的函数必须遵循以下约束条件：

1. 它必须接受指向开始节点的指针作为第一个参数，并作为第二个参数接受要删除的节点，即头节点的指针不是全局的。
2. 它不应返回指向头节点的指针。
3. 它不应接受指向头节点指针的指针。

您可以假设链表永远不会变为空。

让函数名称为deleteNode()。在一个简单的实现中，当要删除的节点是第一个节点时，函数需要修改头指针。如前面的帖子所讨论的,当函数修改头指针时，函数必须使用以下给定方法之一，我们不能在这里使用任何这些方法。

解决方案：

我们明确处理节点要删除的是第一个节点的情况，将下一个节点的数据复制到头部并删除下一个节点。当删除的节点不是头节点时，可以通过找到前一个节点并更改前一个节点的下一个节点来正常处理。以下是实现方式。

// C++程序：在给定条件下删除链表中的一个节点
// #include位于 <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
 
// 一个链表节点的结构体
class Node
{
    public:
    int data;
    Node *next;
};
 
void deleteNode(Node *head, Node *n)
{
    // 当需要删除的节点是头节点时
    if(head == n)
    {
        if(head->next == NULL)
        {
            cout << "只有一个节点。链表无法变为空链表";
            return;
        }
 
        // 将下一个节点的数据复制到头节点
        head->data = head->next->data;
 
        // 存储下一个节点的地址
        n = head->next;
 
        // 断开下一个节点的链接
        head->next = head->next->next;
 
        // 释放内存
        free(n);
 
        return;
    }
 
    // 跟随普通的删除过程
    // 移除当前节点的链接，链接上一个节点和下一个节点
    Node *prev = head;
    while(prev->next != NULL && prev->next != n)
        prev = prev->next;
 
    // 检查要删除的节点是否真的存在于链表中
    if(prev->next == NULL)
    {
        cout << "链表中没有此节点";
        return;
    }
 
    // 移除当前节点
    prev->next = prev->next->next;
 
    // 释放内存
    free(n);
 
    return;
}
 
// 在头部插入一个节点
void push(Node **head_ref, int new_data)
{
    Node *new_node = new Node();
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}
 
// 打印链表整个序列
void printList(Node *head)
{
    while(head != NULL)
    {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}
 
// 驱动程序
int main()
{
    Node *head = NULL;
 
    // 创建含8个节点的链表 -- 12->15->10->11->5->6->2->3
    push(&head,3);
    push(&head,2);
    push(&head,6);
    push(&head,5);
    push(&head,11);
    push(&head,10);
    push(&head,15);
    push(&head,12);
 
    cout << "原始链表: ";
    printList(head);
 
    // 删除值为10的节点
    cout << "删除节点 " << head->next->next->data << " ";
    deleteNode(head, head->next->next);
 
    cout << "修改后的链表: ";
    printList(head);
 
    // 删除第一个节点
    cout << "删除第一个节点 ";
    deleteNode(head, head);
 
    cout << "修改后的链表: ";
    printList(head);
    return 0;
}
// 代码来自rathbhupendra```  

输出:

原始链表: 12 15 10 11 5 6 2 3

删除节点 10:
修改后的链表: 12 15 11 5 6 2 3

删除第一个节点
修改后的链表: 15 11 5 6 2 3

时间复杂度： O(n)，其中n表示给定数组的大小。

空间复杂度： O(1)，没有额外的空间需求，因此是常量。