# Reversing a linked list - recursively.

0 Tallied Votes 695 Views

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;

{
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;
}

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

{
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()
{
node* nd = llist->CreateList(3,llist->n);
llist->PrintList(nd);
nd = llist->Reverse(llist->n);
llist->PrintList(nd);
return 0;
}

#endif``````

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.

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

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)``

.

Nice Example. Thanks. :)

``````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. :)

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;
}
return 0;
}``````
``````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)
{
}``````
dios 0
``````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);
}
}
``````

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.

``````void revList(struct node* prevNode, struct node * nextNode)
{
if (nextNode != NULL)
{
if (nextNode->next == NULL)