如果节点是头节点则不会被删除

Question

这是我的代码，至少是重要的部分。每当我运行它并尝试删除 head 节点时，它都不起作用（输出将是一个大的负数）。它适用于所有其他节点。

是我的代码有问题，还是你不能替换 head？

node* displayList(node* head) {
    node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    return NULL;
}

node* deleteVal(node* head, int val) {
    node* cur, * prev;
    if (head == NULL)
        return head;
    
    if (head->data == val) {
        cur = head->next;
        delete head;
        head = cur;
        return head;
    }
    cur = head;
    prev = NULL;
    while (cur->data != val && cur != NULL) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) {
        return head;
    }
    prev->next = cur->next;
    return head;
}

int main() {
    node* head1 = initNode(), * head2=initNode(), * head3 = initNode();
    int val;
    head1 = input();
    head2 = input();
    head3 = input();
    conca(head1, head2, head3);
    cout << "the concatated list is: ";
    displayList(head1);
    cout << endl<<"enter the value you want to delete: ";
    cin >> val;
    deleteVal(head1, val);
    cout << "the new list is: ";
    displayList(head1);
    return 0;
}

Answer 1

对于初学者来说，while 循环的条件

while (cur->data != val && cur != NULL) {
    prev = cur;
    cur = cur->next;
}

必须改成

while ( cur != nullptr && cur->data != val) {
    prev = cur;
    cur = cur->next;
}

另外你确实需要像

一样删除找到的节点

prev->next = cur->next;
delete cur;
return head;

并且在 main 中，您必须将指针重新分配给头节点，例如

head1 = deleteVal(head1, val);

随着显示的更新，函数可以如下所示

node* deleteVal(node* head, int val) {
    node* cur, * prev;
    if (head == NULL)
        return head;
    
    if (head->data == val) {
        cur = head->next;
        delete head;
        head = cur;
        return head;
    }
    cur = head;
    prev = NULL;
    while ( cur != NULL && cur->data != val ) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) {
        return head;
    }
    prev->next = cur->next;
    delete cur;
    return head;
}

并在主写

head1 = deleteVal(head1, val);

Answer 2

deleteVal() 编码错误。

当不删除 head 节点时，如果在列表中找不到 val，您的 while 循环将表现出 未定义的行为。在那种情况下，cur会在检查完最后一个节点后变成NULL，然后循环会尝试再访问一次cur->data，也就是UB。

您需要交换 while 语句的条件，以便在 cur 之前检查 NULL 它的 data 会员被访问：

while (cur != NULL && cur->data != val)

此外，如果 while 循环确实在剩余节点中找到 val，您只是简单地从列表中取消链接找到的节点，但您实际上并没有 delete'ing那个节点，因此你正在泄漏它的内存。

试试这个：

node* deleteVal(node* head, int val) { node *cur, *prev; if (head == NULL) return head; if (head->data == val) { cur = head->next; delete head; return cur; } // we know the head node doesn't match, no need to // test it again, so start the loop on the 2nd node... cur = head->next; prev = head; while (cur != NULL && cur->data != val) { prev = cur; cur = cur->next; } if (cur != NULL) { prev->next = cur->next; delete cur; } return head; }

话虽这么说，但显示的代码还存在其他问题。

main() 忽略了 deleteVal() 的 return 值。因此，如果 head1 指向的节点实际上是列表中的 removed/deleted，main() 无法知道这一点，因此最终传递 now-invalid node* 之后指向 displayList() 的指针。因此，您需要将 deleteVal() 的 return 值分配回 head1 以反映新的列表状态：

head1 = deleteVal(head1, val);

这就是为什么通过 return 值 return 新列表指针不是一个好的设计选择（除非你在 C++17 和更高版本中将其标记为 nodiscard )，因为它太容易被忽略。更好的设计选择是通过 reference/pointer 传入调用者的变量，这样函数可以在需要时直接更新调用者的变量。

此外，main() 在调用 input() 时会泄漏 head1、head2 和 head3 节点。您正在使用 initNode() 创建新节点，然后重新分配指向由 input() 创建的新节点的指针，因此您无法从 initNode().
访问原始节点
事实上，即使在调用 deleteVal() 之后，您也不会在退出程序之前释放任何剩余的节点。虽然 OS 确实会在程序退出时回收所有使用的内存，但最好的做法是显式释放您分配的任何内容。

还有，你的deleteVal()复杂得没必要，可以大大简化。

此外，displayList() 到 return 根本没有充分的理由。

话虽如此，请尝试更像这样的东西：

void displayList(node* head) { node* curr = head; while (curr != NULL) { cout << curr->data << " "; curr = curr->next; } cout << endl; } void deleteVal(node* &head, int val) { node *cur = head, **prev = &head; while (cur != NULL) { if (cur->data == val) { *prev = cur->next; delete cur; return; } prev = &(cur->next); cur = cur->next; } } void deleteList(node* &head) { node *cur = head, *next; head = NULL; while (cur != NULL) { next = cur->next; delete cur; cur = next; } } int input() { // <-- return int, not node* ! ... return ...; // <-- just the user's entered value, not a node wrapping the value } int main() { node* head1 = initNode(), *head2 = initNode(), *head3 = initNode(); head1->data = input(); head2->data = input(); head3->data = input(); conca(head1, head2, head3); cout << "the concatenated list is: "; displayList(head1); cout << "enter the value you want to delete: "; int val; cin >> val; deleteVal(head1, val); cout << "the new list is: "; displayList(head1); deleteList(head1); return 0; }

如果节点是头节点则不会被删除

node not getting deleted if it's the head

c++

linked-list

nodes

singly-linked-list

function-definition