Thread: Linked list reverse recursively

Originally Posted by gaurav_13191

I know I should write it myself but the problem is that when I don't understand how the above recursion works, I don't think I would be able to write it myself.

That is not necessarily true "in general". Sometimes examples clear things up, sometimes they just make things murkier. Also, you can put yourself in more of a box if you begin to believe that a demonstration of a concept defines the concept itself.

Fortunately, this one is fairly straightforward.

I know what the above code is trying to do and the concepts but just a little stuck over the pointers being updated when the function returns. I have spent a lot of time trying it myself and then when I couldn't, I tried the above code, which is perfectly fine but maybe my concepts are not clear.

All the action is here:

Code:

    first = *head_ref;
    rest  = first->link;

[...]

    /* put the first element on the end of the list */
    recursiveReverse(&rest);
    first->link->link  = first;
  
    /* tricky step -- see the diagram */
    first->link  = NULL;   

    /* fix the head pointer */
    *head_ref = rest;

Recursion has a FILO ordering -- the first call is the last to return, the last call is the first to return.

Let's say you pass this a four node list, 1->2->3->4.
The second call then receives 2->3->4.
The third call 3->4.
The fourth call receives 4, and returns to 3.
In three, the first node is 3, and first->link is 4, so 4->link is set to 3:

Code:

  first->link->link  = first;

The first->link is set to NULL and 4 is set to head, leaving 4->3 when the third call returns into the second.
In the second call, 2 (the "first" node) has not been changed. That means 2->link still points to 3. So 3 now points to 2, and 2->NULL, leaving 4->3->2 when we return to the first call.
In the first call -- the final one to complete -- 1->link is still 2. So first->link->link sets 2 to point to 1. Then first->link is set to NULL.

Notice that the recursion is called using &rest, and that address is set to head in each successive call. The last call was the forth one, which only got passed one node (4). That means when the recursion completes and head is set to "rest" you'll have: 4->3->2->1.

Make sense?