Reversing a linked list - recursively.

lazylibran82 0 Tallied Votes 685 Views Share

This code allows you to create a linked list and reverse it recursively.

/***********list.h***************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef class _node
{
public:
	 int datum;
	_node *next;
	_node *prev;
}node;

class linkedlist
{
public:
	node* CreateList(int num,node*);
	node* Reverse(node* nd); 
	node* n;
};

/******************list.cpp******************/

#ifndef LIST_H
#define LIST_H
#include "list.h"

// Create a random list of elements
node* linkedlist::CreateList(int num,node* List)
{
	node *firstEle = NULL;

	firstEle = new node(); 
	firstEle->datum = 1;
	firstEle->next = NULL;
	List = firstEle;

	for(int i =1; i<num; i++)
	{
		firstEle->next = new node(); 
		firstEle->next->datum = i+1+ pow((-i),(i+1));
		firstEle->next->next = NULL;
		firstEle = firstEle->next;
	}
	return List;
}

void linkedlist::PrintList(node *nd)
{
	printf("Printing the List\n");
	while(nd!= NULL)
	{
		printf("%d\t",nd->datum);
		nd = nd->next;
	}
	printf("\n");
}


node* linkedlist::Reverse(node*p)
{
	node* rev;
	static node* tail = NULL;
	static int count =0;

	if(p->next)
	{
		count++;					
// Use the static variable to return once all the elements of
// the list are reversed.
		rev = Reverse(p->next);
		count--;
		rev->next = p;          // Construct the reversed list.
		rev->next->next = NULL;
		if(count == 0)
			return tail;
		else
			return rev->next;
	}
	else
	{
		tail = p;        // store the pointer to the tail element
		tail->next = NULL;
		return tail;
	}

}

#endif
/*******************main.cpp*********************/
#ifndef LIST_H
#include "list.h"
main()
{        
             linkedlist *llist = new linkedlist();
	node* nd = llist->CreateList(3,llist->n);
             llist->PrintList(nd);
	nd = llist->Reverse(llist->n);
	llist->PrintList(nd);
             return 0;
}

#endif
ChaseVoid 30 Junior Poster

That is not even C a program. It's written in C++ using C header files. C doesn't support classes. it's not object oriented.

wael.salman 0 Newbie Poster

C supports part of OOP or c++. C++ was build according to C basics. Structures in C++ is the same as classes except access attributes.

So you can use in Structures and build your linked list

mstorch 0 Newbie Poster

A couple of quick optimizations:

tail->next = NULL;

statement is not needed in else block of Reverse().

rev->next->next = NULL;

should be moved right after

if(count == 0)

.

Haranadh 0 Newbie Poster

Nice Example. Thanks. :)

Haranadh 0 Newbie Poster
rev->next->next = NULL;  

//this line has to be there.
//Else it wont work.
//Check it once.
//If we go for the recursive function then 
//why don't you have two arguments? Try the below code?
===========
OutputList = ReverseNew(LList,NULL); //Call should be like this.
===========
Node* ReverseNew(Node *NList, Node * Remaining)
{
	if(NList == NULL) return Remaining;
	Node *tList = NList->Next;
	NList->Next = Remaining;
	return ReverseNew(tList,NList);
}

==========

*** If linked list is very big, then a big stack will be created for recursive function, may cause problem.
*** Need to think, as recursive will not be a better solution. :)

danifar 0 Newbie Poster

REVERSE THE LIST USING RECUSION SHORT AND SWEET

struct node* reverse (struct node * n)
      {
         struct node * m ;

         if (! (n && n -> next))
           return n ;
         
         m = reverse (n -> next) ;
         n -> next -> next = n ;
         n -> next = NULL ;
         return m ;
      }



int InvertList(struct node **head)
{
	struct node *temp1,* rev_list = *head;
	struct node* temp = *head;
	if(NULL == rev_list)
	{
		return -1;
	}
	
	while(temp)
	{
		temp1 = temp->next;
		temp->next = rev_list;
		rev_list = temp;
		temp = temp1;
	}
	(*head)->next = NULL;
	*head = rev_list;	
	return 0;
}
xXFireBladeXx 0 Newbie Poster
Node *reverseHelper (Node *ptr, Node *prev)
{
	if (ptr->next)
	{
		Node *next=ptr->next;
		ptr->next = prev;
		return reverseHelper(next, ptr);
	}
	else
	{
		ptr->next = prev;
		return ptr;
	}
}

Node *reverse(LL *list)
{
	return reverseHelper(list->head,NULL);
}
dios 0 Newbie Poster
struct node * reverse(struct node **s)
{
     struct node *t;

     if(((*s)->next)!=NULL)
     {
         t=reverse(&((*s)->next));
          ((*s)->next)->next=(*s);
          (*s)->next=NULL;
          return t;             
     }
     else
     {
     return (*s);
}
}
arshdeepkaur 0 Newbie Poster

reverse using recursion..
i think this if condition is wrong
if (! (n && n -> next))

it should be
if (! (n->next && n->next->next))
this is to ensure that n points to the 2nd last node. (i.e. if n->next->next is NULL we have to return n as here n is pointing to the 2nd last node and we have to start reversing links from here)

because if you return the last node as per "if (! (n && n -> next))",
n->n->next = head will crash as n->next->next is NULL..since head is aldready pointing to the last node.
so we have to ensure that n is pointing to the 2nd last node.

Prad_1 0 Newbie Poster
void revList(struct node* prevNode, struct node * nextNode)
{
    if (nextNode != NULL)
    {
        if (nextNode->next == NULL)
                    head = nextNode;
        struct node* temp;
        temp = nextNode->next;
        nextNode->next = prevNode;
        revList(nextNode, temp);
    }

}
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.