Recursive function to reverse linked list(Code Snippet Explanation) [closed]

Question

Can someone please explain the code below:

void reverseList(node **href){
   node *first;
   node *rest;

  if(*href == NULL){
     return;
   }

    first = *href;
    rest = first->next;

    if(rest == NULL){
      return;
    }

   reverseList(&rest);
   first->next->next = first;
   first->next = NULL;


   *href = rest;
}

Note : href is the head reference of the linked list.

What i don't understand is the last statement => *href = rest as this step will happen when the recursion is unfolding wouldn't this make the second node from the start head ref but we want the last node as our head ref.

How will this make the last node as our head_ref?

Answer 1

reverseList will update *href so it points to the new head of the list it's given; this is the node that used to be last.
I think what could be confusing you is that all calls update *href to the same value; when the recursive call returns, it will point to the last node of the input, which is the first node of the result.
This value is only set when the recursion terminates.

I'm going to rename first and rest in an attempt to clarify this.

The first condition,

if(*href == NULL){
    return;
}

is there to handle the case when you start with the empty list.

The following handles the common base case, where you eventually reach a one-element list:

old_head = *href;

/* "If the list has exactly one element, do nothing." */
if(old_head->next == NULL){
    return;
}

Then, you recurse (keep in mind that the parameter is both an "in" and an "out" parameter)

new_head = old_head->next;
reverseList(&new_head);

and now, through the power of recursion, new_head points to the head of the reversed "rest of the list".
This is also the pointer that's going to be our result.
(The last node of the tail is also the last node of the entire list, right?)

What we need now is to set up the end of the new list (the initial part of it has already been reversed during the recursion).

Since we saved old_head before, we can reverse the next pointer of the node that used to follow it:

old_head->next->next = old_head;
old_head->next = NULL;

that is, this

old_head                                            new_head 
  |                                                    | 
  v                                                    v
+---+    +---+         +-----------------------------+
| ------>|   |  <----- |        reversed             |
|   |    |  ----->     | former continuation of list |
+---+    +---+         +-----------------------------+

becomes this (old_head->next->next = old_head;)

old_head                                             new_head 
  |                                                    |
  v                                                    v
+---+    +---+         +-----------------------------+
| ------>|   |  <----- |         reversed            |
|   |<-----  |         | former continuation of list |
+---+    +---+         +-----------------------------+

and then (old_head->next = NULL;)

old_head                                             new_head 
  |                                                    |
  v                                                    v
+---+    +---+         +-----------------------------+
| X |    |   |  <----- |         reversed            |
| X |<-----  |         | former continuation of list |
+---+    +---+         +-----------------------------+

Then, we update the parameter so our caller also gets a pointer to the new head:

*href = new_head;