c - reversing linked list

Question

I am trying to reverse a linked list using recursion and wrote the following code for it. The list is start of the list at the beginning.

 node *reverse_list_recursive(node *list)
 {
      node *parent = list;
      node *current = list->next;

      if(current == NULL)
       return parent;

      else
       {
           current = reverse_list_recursive(current);
           current->next = parent;
           printf("
 %d  %d 
",current->value,parent->value);
           return parent;
       }

  }

I could see that all the links are getting reversed. However when I try to display, I get an infinite prints of the numbers. I suspect an error when I am trying to reverse the link for the first number originally in the list.

What am I doing wrong?

Answer 1

Suppose I have a linked list:

 ----------      ----------      ----------      ---------- 
|  1  |    |--->|  2  |    |--->|  3  |    |--->|  4  |    |--->NULL
 ----------      ----------      ----------      ---------- 

Your code converts it to:

   ----------------------          ----------------------
   |                    |          |                    |
   v                    |          v                    |
 ----------      ----------      ----------      ----------
|  1  |    |--->|  2  |    |    |  3  |    |    |  4  |    | 
 ----------      ----------      ----------      ---------- 
                   ^                    |
                   |                    |
                   ----------------------

Notice that the first element still points back to 2.

If you add the line parent->next = NULL after the first two, you will get:

           ----------------------          ----------------------
           |                    |          |                    |
           v                    |          v                    |
         ----------      ----------      ----------      ----------
NULL<---|  1  |    |    |  2  |    |    |  3  |    |    |  4  |    | 
         ----------      ----------      ----------      ---------- 
                           ^                    |
                           |                    |
                           ----------------------

which is in fact the correct structure.

The complete code is: (You only need to print the current value for each recursive call)

node *reverse_list_recursive(node *list)
  {
      node *parent = list;
      node *current = list->next;

      if(current == NULL)
       return parent;

      else
       {
           current = reverse_list_recursive(current);
           parent->next = NULL;
           current->next = parent;
           printf("
 %d 
",current->value);
           return parent;
       }

  }