Reversing a linked list list

Question

I was trying to reverse a linked list but I kept comming across an issue. I finally figured out was wrong and fixed it, however I do not understand why my last approach doesn't work. The code below is the one that successfully reverses a linked list.

void reverse_list(list** head)
{
    list* currNode = *head;
    list* prevNode = NULL;
    list* tmpNode;

    while(1)
    {
        tmpNode = currNode->next;
        currNode->next = prevNode;
        if(tmpNode == NULL)
        {
            *head = currNode;
            break;
        }
        prevNode = currNode;
        currNode = tmpNode;
    }

}

However, the code below does not work. Both use double pointers, but in this one I dereferenced head twice to get to the actual object and assigned it with *currNode. When I run this code, It ends up going into an infinite loop and its missing the last item. For example, if the items were 1,2,3,4,5, then the reverse would be 5,4,3,2, and it keeps printing the same list. I don't understand why this approach isn't working since I'm accessing the actual object (by derefrening twice) and assigning it with a new object (*currNode).

void reverse_list(list** head)
{
    list* currNode = *head;
    list* prevNode = NULL;
    list* tmpNode;

    while(1)
    {
        tmpNode = currNode->next;
        currNode->next = prevNode;
        if(tmpNode == NULL)
        {
            **head = *currNode;
            break;
        }
        prevNode = currNode;
        currNode = tmpNode;
    }

}

The code below has the same issue as the one above. I followed the same approach as with the above code only this one uses a single pointer.

void reverse_list(list* head)
{
    list* currNode = head;
    list* prevNode = NULL;
    list* tmpNode;

    while(1)
    {
        tmpNode = currNode->next;
        currNode->next = prevNode;
        if(tmpNode == NULL)
        {
            *head = *currNode;
            break;
        }
        prevNode = currNode;
        currNode = tmpNode;
    }

}

Any help to understand this would greatly be appreciated. Thank you!

Answer 1

Different levels of indirection.

Given list** head, *head is the value pointed to by head, a pointer to a Node, a list *. We dereference one more time and **head dereferences to list * and then to list. We're all out of pointers and and are accessing the object at the end of the line. So

**head = *currNode;

dereferences both pointers all the way back to the objects. This is assigning values to objects, not addresses to pointers to objects. Rather than changing the linkage of the list by updating pointers, whatever list head ultimately pointed at has been changed to match currNode, breaking the integrity of the list.

*head = currNode;

only derefences head one level closer to the object. Here we are operating on pointers and changing linkage.

In the final example we have

*head = *currNode;

and this is similar to the first failed attempt. It is assigning values rather than changing the pointers.