This code allows you to create a linked list and reverse it recursively.
Reversing a linked list - 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.