# Tutorial :Linked list recursive reverse

### Question:

I was looking at the code below from stanford library:

``void recursiveReverse(struct node** head_ref)  {      struct node* first;      struct node* rest;        /* empty list */      if (*head_ref == NULL)         return;          /* suppose first = {1, 2, 3}, rest = {2, 3} */      first = *head_ref;      rest  = first->next;        /* List has only one node */      if (rest == NULL)         return;          /* put the first element on the end of the list */      recursiveReverse(&rest);      first->next->next  = first;         /* tricky step -- see the diagram */      first->next  = NULL;                 /* fix the head pointer */      *head_ref = rest;  }  ``

What I don't understand is in the last recursive step for e.g if list is 1-2-3-4 Now for the last recursive step first will be 1 and rest will be 2. So if you set *head_ref = rest .. that makes the head of the list 2 ?? Can someone please explain how after reversing the head of the list becomes 4 ??

### Solution:1

Draw out a stack trace...

``Intial - {1,2,3,4}  Head - 1  Rest = 2,3,4  Recurse(2,3,4)  Head = 2  Rest = 3,4  Recurse(3,4)  Head = 3   Rest = 4  Recurse (4)  Head = 4  Rest = null //Base Case Reached!! Unwind.    So now we pick up   Recurse(3,4)  Head = 3   Rest = 4  // Return picks up here  first->next->next  = first;   so list is:  3,4,3  // set head to null,  null ,4,3,  //Off with his head!  4,3  Return    Now we're here  Recurse(2,3,4)  Head = 2  Rest = 3,4  Previous return leaves state as:  Head = 2  //But Head -> next is still 3! -- We haven't changed that yet..  Rest = 4,3    Head->next is 3,   Head->next->next = 2 makes the list (actually a tree now)  4->3->2     ^     |     2  And chop off the head leaving  4->3->2  and return.    Similarly, do the last step which will leave  4->3->2->1        ^        |        1  and chop off the head, which removes the one.   ``

### Solution:2

Consider the list:

``   1  ->  2  ->  3  ->  4 -> NULL     ^      ^     |      |   first   rest  ``

Where `first` points to the first node and rest points to the node next to `first`.

Since the list is not empty and list does not contain one node we make recursive call to `reverse` to reverse the list pointed to by `rest`. This is how the list looks after reversing the rest of the list:

``   1  ->  2  <-  3  <-  4     ^      |             ^     |     NULL           |   first                 rest  ``

As seen `rest` now points to the reversed list which has `4` at the beginning and `2` at the end of list. The next pointer of node `2` is `NULL`.

Now we need to append the first node to the end of the reversed-rest list. To append anything to the end of the list we need to have access to the last node of the list. In this case we need to have access to the last node of the reversed-rest list. Look at the diagram, `first -> next` points to the last node reversed-rest list. Therefore `first -> next -> next` will be next pointer of the last node of the reversed-rest list. Now we need to make it point to `first` so we do:

``first -> next -> next = first;  ``

After this step the list looks like:

``   1  <-  2  <-  3  <-  4     ^  ->                ^     |                    |   first                 rest  ``

Now the `next` field of the last node of the list must be `NULL`. But it is not the case now. The `next` field of the last node ( node `1`) is pointing to the node before it ( node `2`). To fix this we do:

``first -> next = NULL;  ``

After this the list looks like:

``NULL <- 1  <-  2  <-  3  <-  4          ^                    ^          |                    |        first                 rest  ``

As seen the list is now correctly reversed with `rest` pointing to the head of the reversed list.

We need to return the new head pointer so the that changes are reflected in the calling function. But this is a `void` function and `head` is passed as double pointer so changing the value of `*head` will make the calling function see the changed head:

``*head = rest;  ``

### Solution:3

The rest isnâ€™t `2`, itâ€™s `2 -> 3 -> 4`, which gets reversed recursively. After that we set `*head_ref` to `rest`, which is now (recursively reversed!) `4 -> 3 -> 2`.

The important point here is that although both `first` and `rest` have the same type, i.e. `node*`, they are conceptually fundamentally different: `first` points to one single element, while `rest` points to a linked list of elements. This linked list is reversed recursively before it gets assigned to `*head_ref`.

### Solution:4

I recently wrote a recursive method for reversing a linked list in ruby. Here it is:

``def reverse!( node_1 = @head, node_2 = @head.link )      unless node_2.link           node_2.link = node_1          @head = node_2          return node_1      else           return_node = reverse!(node_1.link, node_2.link)          return_node.link = node_1          node_1.link = nil          return node_1      end      return self  end  ``

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »