node not getting deleted if it's the head

Question

This is my code, the important part at least. Whenever I run it and try to delete the head node, it won't work (the output will be a large negative number). It will work for all other nodes.

Is it something with my code, or you just can't replace the 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

deleteVal() is coded wrong.

When NOT removing the head node, your while loop will exhibit undefined behavior if val is not found in the list. In that situation, cur will become NULL after the last node is checked, and then the loop will try to access cur->data one more time, which is UB.

You need to swap the conditions of the while statement so that cur is checked for NULL before its data member is accessed:

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

Also, if the while loop does find val in the remaining nodes, you are simply unlinking the found node from the list, but you are not actually delete'ing that node, thus you are leaking its memory.

Try this instead:

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;
}

Now, that being said, there are other issues with the code shown.

main() is ignoring the return value of deleteVal(). So, if the node pointed to by head1 were actually removed/deleted from the list, main() has no way of knowing that, and thus ends up passing a now-invalid node* pointer to displayList() afterwards. So, you need to assign the return value of deleteVal() back to head1 to reflect the new list state:

head1 = deleteVal(head1, val);

This is why it is not a good design choice to return a new list pointer by return value (unless you mark it as nodiscard in C++17 and later), as it is too easy to ignore. A better design choice is to pass in the caller's variable by reference/pointer instead, so the function can update the caller's variable directly when needed.

Also, main() is leaking the head1, head2, and head3 nodes when calling input(). You are creating new nodes with initNode(), and then reassigning the pointers to point at new nodes created by input(), thus you lose access to the original nodes from initNode().

In fact, even after calling deleteVal(), you are not freeing any remaining nodes before exiting the program. While it is true that the OS will reclaim all used memory when the program exits, it is best practice to explicitly free anything you allocate.

Also, your deleteVal() is needlessly complex, it can be greatly simplified.

Also, there is no good reason for displayList() to return anything at all.

With that said, try something more like this instead:

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;
}