Thread: Reversing LinkList In Reverse Order Using Recursion

Hi All

I was trying to reverse a linklist in reverse direction using the recursion. I was able to reverse n - 1 element but it is not printing the first one. Below is my code.

Code:

typedef struct linklist
{
  int data;
  linklist *next;
};

void add(int data,linklist **node)
{
  linklist *temp,*temp2;

  temp = (struct linklist *) malloc(sizeof(linklist));
  
  temp->data = data;
  temp->next = NULL;

  if (*node == NULL )
  {
    *node = temp;
    return;  
  }

  temp2 = *node;

  while ( temp2->next != NULL )
   temp2 = temp2->next;

  temp2->next =  temp;
  

}

void reverse_recur(linklist *node)
{
  
  if (node != NULL )
  {
     node = node->next;
     reverse_recur(node);

   if ( node != NULL)       
      printf("\n Print In Reverse Order\n %d\n",node->data);
  
  
  }
  
}


int main()
{
  
 linklist *node = NULL;

 add(1,&node);
 add(2,&node);
 add(3,&node);
 add(4,&node);

 print(&node);

reverse_recur(node);

This is happening since recursion is starting from second node, which is due to reason not printing the first one when recursion print values from stack once

node != NULL

Condition is met.

Do anybody help to print the first node too.
Currently I am using below statement for printing the first element;

reverse_recur(node);
printf("\n Print In Reverse Order\n %d\n",node->data);

But this I don;t want. Any body has idea on this.

Thanks

Hi

Did you mean this:

Code:

void reverse_recur(linklist *node)
{
  linklist *temp = node;
  if (node != NULL )
  {
     node = node->next;
     reverse_recur(node);
   if ( node != NULL)       
      printf("\n Print In Reverse Order\n %d\n",node->data);
   else
      printf("\n Print In Reverse Order\n %d\n",node->data);
  }
  
  
}

But this also didn';t work as when else is executed it has NULL and program crashed.

I have linklist of 1 2 3 4 and I want to print it as 4 3 2 1.
Thanks

You can't do node->data on a NULL pointer -- so yes, this will crash. It'll get to the end of the list (node==NULL), it'll fail the if condition on line 4 and the function will return back to the previous recursive call. Since you've already done node=node->next, node is NULL.

You need to get out of the recursion when you get to the end of the list, without trying to access node->data.
Also, I don't think you should be doing node=node->next before the printf statements, as then you'll miss off the first element in the list (which I think you said in your original post).

Thanks

That I was doing in my code earlier.

Code:

reverse_recur(node);
printf("\n Print In Reverse Order\n %d\n",temp->data);

So basically I am printing 4 to 2 elements (1 2 3 4 as my link list elements) and then printing current.one which is 1.

Is that you were saying?

I want to print every node inside reverse_recur() function. as since recurision is starting from 2nd node, its not priniting the first element. Is there way I can do that?

Thanks