Deleting node inside of linked list

Question

I'm stuck on this particular function that frees all even nodes from the linked list. I've figured out how to free all the nodes from a linked list but I cannot figure this out. The code i'm posting is very wrong. What I don't understand is how to use a node *temp variable and link it to the head->next node, as the head is what is being freed (because it is even). Also, at the end of the while loop, I know that I need to increment to the next node in the list, but I seem to be doing that already in the first if statement, so wouldn't calling current = current->next actually be taking me to current->next->next, and skipping a node? Sorry for this massive block of text.

node *delete_even_node(node *head)
{
    node *temp, *current = head;
    if (head == NULL)
        return NULL;
    while (current != NULL)
    {
        if (current->data % 2 == 0)
        {
            printf("Deleting Even %d\n", current->data);
            temp = current->next; //problem starts
            temp = temp->next;
            free(temp);
        }
        else
            current = current->next;
        current = current->next; 
    }
    return head;
}

This yields quite a lot of results. Does not any of those help? stackoverflow.com/search?q=%5Bc%5D+delete+node+linked+list — klutt
It is not enough to delete the node. You must also update the pointers to the deleted nodes, that is either the head or the next field of the preceding node. — M Oehm
@klutt Ah, yes you're right. I found something just had to do some more digging. — idkusrname126
And you want to delete current, not the node two places after it. (And If current->next == NULL, the assignment temp = temp->next will crash.) — M Oehm

Vlad from Moscow Vlad from Moscow · Accepted Answer · 2020-10-25T18:37:59

There are two approaches.

If to use your approach when the pointer to the head node is passed by value then the function can look the following way.

node * delete_even_node( node *head )
{
    while ( head && head->data % 2 == 0 )
    {
        node *tmp = head;
        head = head->next;
        free( tmp );
    }

    if ( head )
    {
        node *current = head;
        while ( current->next )
        {
            if ( current->next->data % 2 == 0 )
            {
                node *tmp = current->next;
                current->next = current->next->next;
                free( tmp );
            }
            else
            {
                current = current->next;
            }
        }
    }

    return head;
}

Another approach is to pass the pointer to the head node by reference.

For example

void delete_even_node( node **head )
{
    while ( *head )
    {
        if ( ( *head )->data % 2 == 0 )
        {
            node *tmp = *head;
            *head = ( *head )->next;
            free( tmp );
        }
        else
        {
            head = &( *head )->next;
        }
    }
}

And the function is called like

delete_even_node( &head );

Deleting node inside of linked list

1 Answers