删除链表中的节点

Question

我知道有很多关于从链表中删除节点的问题。但是我的思绪卡在了一个点上，我无法清除我的困惑。

我有一个包含节点 1,2,2 的链表。我想从中删除 2 的节点。我的代码只删除 2 的第一个节点而不是第二个节点。简而言之，我想删除与用户提供的密钥匹配的所有节点。这是我的代码：

void LinkedList::Delete(int key)
{
    if(head == 0)
        return;
    if(head->data == key)
    {
        Node *p = head;
        head = head->next;
        delete p;
    }
    else
    {
        Node *prev = 0;
        Node *temp = head;
        while(temp!=0)
        {
            if(temp->data == key)
            {
                Node *q = temp;
                temp = temp->next;
                prev = temp;
                delete q;
            }
            else
            {
                prev = temp;
                temp = temp->next;
            }
        }

    }
}

如果我注释掉 else 部分，那么它会在最后一行给出访问冲突错误，即 temp=temp->next 我知道问题是它应该指向哪个节点，如果它是在最后一个节点！

Answer 1

在下面的一段代码中，删除后，您的临时文件未指向下一个节点。所以，一旦你删除了“2”的第一个条目，你的循环就停止了。

 if(temp->data == key)
        {
            prev->next = temp->next;
            temp = 0;
            delete temp;
        }

尝试在 IF 块中执行以下操作。

 itemToDelete = temp;
 temp = temp->next;
 delete itemToDelete;

Answer 2

您的代码中存在一些问题。如果第一个节点等于“2”——您只删除第一个节点。为什么要为 Node *prev 分配内存？而且你有内存泄漏（见评论）。

您可以试试这个代码：

void LinkedList::Delete(int key)
{
    if (head == 0)
        return;

    Node* prev = 0;
    Node* cur = head;
    while (cur != 0)
    {
        if (cur->data == key)
        {
            Node* temp = cur;
            if (prev == 0)
                head = cur->next;
            else
                prev->next = cur->next;
            cur = cur->next;
            delete temp;
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }
    }
}

Answer 3

这是非常典型的 C++ 初学者错误，我敢打赌，当我输入完这个答案时，会有提示音告诉你如何删除指针（提示：先删除，然后取消——如果你需要）。

为了完整起见，您可以避免检查 prev 指针并使用指针到指针来简化代码。 See here for details.

void LinkedList::Delete(int key)
{
    for (Node** pp = &head; *pp; pp = &(*pp)->next)
    {
        Node* p = *pp;
        if (p->data == key)
        {
            *pp = p->next;
            delete p;
        }
    }
}

Answer 4

您的代码没有删除任何内容，因为您没有遍历列表。您只是在检查第一个元素是否等于键 (2)，但列表的第一个元素是 1。

如果要删除其键 == 函数参数键的每个节点，则需要遍历整个列表。

node* current_node{ head };
while (current_node)
{
    node* next{ current_node->next };
    if (current_node->key == key)
    {
        // This operation should take care of properly managing pointers
        // in the linked list when a node is erased.
        erase(current_node);
    }
    current_node = next;
}

Answer 5

我用 Turbo C++ 编译器写过。它工作正常。

//start deleteEnd code
void deleteEnd()
{
    if (first == NULL)
    {
        cout<<"No list Available";
        return;
    }
    next = first;
    while (next->add != NULL)
    {
        cur = next;
        next = next->add;
    }
    cur->add=NULL;
}
//deleteEnd

删除链表中的节点

Delete nodes in a linked list

c++

singly-linked-list