Reverse linked list crash confusion

Question

I never normally post a question asking what is wrong with code, but I am a bit baffled here and don't see the reason a function below should fail.

I am writing a function to reverse a linked list. The first function ReverseList1() causes a runtime error and crashes when tested with the driver code form main().

The second function ReverseList2(), using a pointer to a pointer instead as the head argument works fine. Why, It is still pointing to the same data? Perhaps I am missing something obvious and crucial but I can't see it. Thanks in advance.

//// First function/////

void ReverseList1(struct Node* head, struct Node* prev, struct Node* next)
{
    // not valid list
    if (head == NULL)
    {
        return;
    }

    struct Node* cur = head;

    while(cur != NULL)
    {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    head = prev;
}

//////// Second function - doesn't crash when use this////

void ReverseList2(struct Node** head, struct Node* prev, struct Node* next)
{
    // not valid list
    if (head == NULL)
    {
        return;
    }

    struct Node* cur = *head;

    while(cur != NULL)
    {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    *head = prev;
}

////// Driver code to test//////

int main()
{
    struct Node* head= new struct Node;
    head->data = 1;

    head->next = new struct Node;
    head->next->data = 2;

    head->next->next = new struct Node;
    head->next->next->data = 3;

    head->next->next->next = new struct Node;
    head->next->next->next->data = 4;

    head->next->next->next->next = NULL;

    //ReverseList1(head, NULL, NULL); // Runtime error
    ReverseList2(&head, NULL, NULL)

    cout<<head->data<<endl;
    cout<<head->next->data<<endl;
    cout<<head->next->next->data<<endl;
    cout<<head->next->next->next->data<<endl;
    return 0;
}

Don't tag random languages, tag only the language you are actually using. — Baum mit Augen, Oct 17 '17 at 09:21
Also, the entire code is *extremely* poor C++ to begin with, time to get yourself some C++ book from this decade. — Baum mit Augen, Oct 17 '17 at 09:22
C++ provides us with the power to write in a style which may suit us depending on our needs. The struct declarations are C style yes, but still valid. There can be reasons to write code like this. — Engineer999, Oct 17 '17 at 09:24
Without changing anything fundamental to your solution, you could write `typedef struct Node* Link;` (or the same without the redundant `struct`) and use that. Then you'll see that you are passing `Link` values _by value_ to `ReverseList1`, and since it returns `void` it cannot reasonably export any useful result to its caller. — Marc van Leeuwen, Oct 17 '17 at 09:41

score 1 · Answer 1 · answered Oct 17 '17 at 09:22

1

using a pointer to a pointer instead as the head argument works fine. Why, It is still pointing to the same data

No, it is not pointing to same data. The pointer points to the node. The pointer to pointer points to the pointer that points to the node.

When you assign the pointer variable that is local to the function, it has no effect on any variable outside the function. By not updating the head pointer that is not a local variable to the function, the implementation of the algorithm is incomplete.

When you dereference a pointer that points to an object that is not a local variable, then assigning that dereferenced object does have an effect on that object.

answered Oct 17 '17 at 09:22

eerorika

232,697
12
197
326

Thanks for the answer without unnecessary criticism like so many others. I realise now that I am doing something fundamentally wrong in this case. When I pass head to ReverseList1() , am I not passing the address of the structure created dynamically in main(). I would have thought that the modifications I make inside the function would reflect changes outside then? – Engineer999 Oct 17 '17 at 14:48
Yes, modifications that you make inside the function *to the structure created dynamically in main* do reflect changes outside the function. But changes to the local pointer do not. – eerorika Oct 17 '17 at 14:51
What is the local pointer in this case? I thought I am passing the address of the struct? If with a normal variable such as an int for example, if I pass the address of the int to a function which takes an int *, the changes to the int in the function will reflect changes outside, but not in the case for struct? – Engineer999 Oct 17 '17 at 14:56
@Engineer999 `What is the local pointer in this case?` The argument of the function. `... but not in the case for struct?` Wrong. If you change the pointed object, whether an int or struct, the changes will reflect outside. But modifying the pointer, whether it points to int or a struct, has no effect on the original pointer from which the function argument was copied from. – eerorika Oct 17 '17 at 15:00

Reverse linked list crash confusion

1 Answers1