链表删除-ag捕鱼王app官网

在本文中，我们将学习如何从链表中删除节点。

链表删除算法

令 head 为指向链表第一个节点的指针，令 temp 为要从链表中删除的节点的值。

迭代算法

• 初始化指针 curr 指向 head 以遍历链接列表，而将 prev 设置为 null 以在删除时跟踪 temp 之前的节点。
• 如果要删除的节点是 head 即 temp！=null && curr->data==temp，则将 head 设置为 curr->next 并删除 curr。
• 否则，请执行以下操作，直到我们到达要删除的节点为止。
  • prev=temp。
  • temp=temp->next。
• 如果 temp==null，返回；
• 将 prev->next 设置为 temp->next，并删除 temp 节点。

递归算法

• 如果 head==null，则链表为空，没有要删除的元素。因此，返回；
• 如果 head->data==temp，即我们找到了要删除的节点
  • 将 head 存储在临时节点 t 中。
  • 将 head 设置为 head->next 以删除该节点。
  • 删除 t 并返回到较早的递归调用。
• 如果以上条件均不满足，则递归调用 head->next 上的 deletenode() 以继续寻找节点。

链接列表删除图解

假设我们具有以下链接列表 1 -> 2 -> 3 -> 4，并且我们想删除值为 3 的节点。

• 用值 1 和 prev 将指向 head 节点的指针 curr 初始化为 null。
• 反复移动 curr，直到到达值为 3 和 prev 为 2 的节点。
• 将 prev（即 2）指向 curr->next（即 4）。
• 删除值为 3 的 curr 节点。

链接列表删除实施

#include using namespace std;
class node {
    public:
        int data;
        node* next;
        node(int x) {
            this->data = x;
            this->next = null;
        }
};
void deletenode(node*& head, int val)
{
    if (head == null) {
        cout << "element not present in the list\n";
        return;
    }
    if (head->data == val) {
        node* t = head;
        head = head->next;
        delete (t);
        return;
    }
    deletenode(head->next, val);
}
void deleteiter(node** head, int x)
{
    node* temp = *head;
    node* prev = null;
    if (temp != null && temp->data == x)
    {
        *head = temp->next;
        delete temp;
        return;
    }
    else
    {
        while (temp != null && temp->data != x)
        {
            prev = temp;
            temp = temp->next;
        }
        if (temp == null)
            return;
        prev->next = temp->next;
        delete temp;
    }
}
void printlist(node* head)
{
    node*curr = head;
    while (curr != null) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << "\n";
}
int main()
{
    node* head = new node(1);
    head -> next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);
    head->next->next->next->next = new node(5);
    printlist(head);
    deletenode(head, 3);
    printlist(head);
    deleteiter(&head, 4);
    printlist(head);
    return 0;
}

链表删除算法的复杂性

时间复杂度

• 平均情况

要删除链接列表中第 i 个位置的节点，我们必须访问 i 个节点。因此，时间复杂度约为 o(i)。而且，链表中有 n 个节点，因此平均情况下的时间复杂度为 o(n/2) 或 o(n)。时间复杂度约为 o(n)。

• 最佳情况

最好的情况是当我们要删除链接列表的开头时。最佳情况下的时间复杂度是 o(1)。

• 最坏情况

最坏情况下的时间复杂度是 o(n)。这与平均情况下的时间复杂度相同。

空间复杂度

在迭代实现的情况下，此算法的空间复杂度为 o(1)，因为它除了临时变量外不需要任何数据结构。

在递归实现中，由于递归调用堆栈所需的空间，空间复杂度为 o(n)。