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 »