Using pointers to pointers to update linked lists in C

Question

I am currently working through C Programming A Modern Approach by K.N. King, and one of the exercise questions is:

The following function is supposed to insert a new node into its proper place in an ordered list, returning a pointer to the first node in the modified list. Unfortunately, the function doesn't word correctly in all cases. Explain what's wrong with it and show how to fix it. Assume that the node structure is the one defined in Section 17.5.

struct node
{
    int value;
    struct node next;
};

struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
    struct node *cur = list, *prev = NULL;
    while (cur->value <= new_node->value) {
        prev = cur;
        cur = cur->next;
    }
    prev->next = new_node;
    new_node->next = cur;
    return list;
}

After trying to understand this for a while and struggling, I eventually came across another stackoverflow question where someone posted this as their answer. I currently don't have enough reputation to ask about it on there, so I'm asking here to try to wrap my head around this.

struct node * insert_into_ordered_list( struct node *list, struct node *new_node )
{
    struct node **pp = &list;

    while ( *pp != NULL && !( new_node->value < ( *pp )->value ) ) 
    {
        pp = &( *pp )->next;
    }

    new_node->next = *pp;
    *pp = new_node;

    return list;
}

Could someone explain to me how the previous node, the one before the inserted new_node is being updated to point at the inserted new_node? I'm guessing the line *pp = new_node; has something to do with it, but I can't understand how. Thank you.

Answer 1

pp either initially points to the pointer head or due to the while loop to the data member next of some node

while ( *pp != NULL && !( new_node->value < ( *pp )->value ) ) 
{
    pp = &( *pp )->next;
}

For example if pp points to head. If head is equal to NULL or new_node->value < head->value then these statements

new_node->next = *pp;
*pp = new_node;

in fact are equivalent to

new_node->next = head;
head = new_node

If pp points to the data member next of some node then these statements

new_node->next = *pp;
*pp = new_node;

change the value of the of the current data member next with the address of the new node

*pp = new_node;

and before this the data member next of the new node is set to the value stored in the data member next of the current node.

As for this function

struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
    struct node *cur = list, *prev = NULL;
    while (cur->value <= new_node->value) {
        prev = cur;
        cur = cur->next;
    }
    prev->next = new_node;
    new_node->next = cur;
    return list;
}

then there is no check whether the pointer cur becomes (or initially is) equal to NULL. And secondly the pointer list is not changed when the new node is inserted before the node pointed to by list.

The function could be defined the following way

struct node *insert_into_ordered_list(struct node *list, struct node *new_node)
{
    if ( list == NULL || new_node->value < list->value )
    {
        new_node->next = list;
        list = new_node;
    }
    else
    { 
        struct node *cur = list;
        while ( cur->next != NULL && cur->next->value <= new_node->value) 
        {
            cur = cur->next;
        }
    
        new_node->next = cur->next;
        cur->next = new_node;
    }

    return list;
}