[ Home  |  FAQ-Related Q&As  |  General Q&As  |  Answered Questions ]

    Search the Q&A Archives

Write a recursive C program to reverse the singly link list ...

<< Back to general questions

Question by Gaurav Gupta
Submitted on 4/21/2004
Related FAQ: N/A
Rating: Rate this question: Vote
Write a recursive C program to reverse the singly link list


Answer by samcorp
Submitted on 8/8/2004
Rating: Not yet rated Rate this answer: Vote
#include "alloc.h"

  

/* structure containing a data part and link part */  

struct node  

{  

int data ;  

struct node *link ;  

} ;  

  

reverse ( struct node ** ) ;  

  

main( )  

{  

struct node *p ;  

p = NULL ;  /* empty linked list */  

  

addatbeg ( &p, 1 ) ;  

addatbeg ( &p, 2 ) ;  

addatbeg ( &p, 3 ) ;  

addatbeg ( &p, 4 ) ;  

addatbeg ( &p, 5 ) ;  

addatbeg ( &p, 6 ) ;  

  

clrscr( ) ;  

display ( p ) ;  

printf ( "\nNo. of elements in the linked list = %d", count ( p ) ) ;  

  

reverse ( &p ) ;  

display ( p ) ;  

printf ( "\nNo. of elements in the linked list = %d", count ( p ) ) ;  

}  

  

/* adds a new node at the beginning of the linked list */  

addatbeg ( struct node **q, int num )  

{  

struct node *temp ;  

  

/* add new node */  

temp = malloc ( sizeof ( struct node ) ) ;  

temp -> data = num ;  

temp -> link = *q ;  

*q = temp ;  

}  

  

reverse ( struct node **x )  

{  

struct node *q, *r, *s ;  

  

q = *x ;  

r = NULL ;  

  

/* trasverse the entire linked list */  

while ( q != NULL )  

{  

s = r ;  

r = q ;  

q = q -> link ;  

r -> link = s ;  

}  

  

*x = r ;  

}  

  

/* displays the contents of the linked list */  

display ( struct node *q )  

{  

printf ( "\n" ) ;

  

/* traverse the entire linked list */

while ( q != NULL )

{

printf ( "%d ", q -> data ) ;  

q = q -> link ;  

}  

}  

  

/* counts the number of nodes present in the linked list */  

count ( struct node * q )  

{  

int c = 0 ;  

  

/* traverse the entire linked list */  

while ( q != NULL )  

{  

q = q -> link ;  

c++ ;  

}  

  

return c ;  

}


 

Answer by thulasi
Submitted on 10/1/2004
Rating: Not yet rated Rate this answer: Vote
i don't know

 

Answer by Manoj Gupta
Submitted on 10/18/2004
Rating: Not yet rated Rate this answer: Vote
#include<stdio.h>

struct node{
    int val;
    struct node *next;
  };

/* here is the function that does your job */
void printRev(struct node *list){
  if(list->next)
       printRev(list->next);
  printf("%d\n",list->val);
}

void main (){


int i=1;
struct node *list,*start,*temp;
printf("\nThe default value for first and last element is 0\n\n");
start=(struct node*)malloc(sizeof(struct node));
start->val=0; // by default 0 is start value
start->next=NULL;
list=start;
do{

  printf("(to terminate enter 0) Value:");
  scanf("%d",&i);
  temp=(struct node*)malloc(sizeof(struct node));
  temp->val=i;
  temp->next=NULL;
  list->next=temp;
  list=temp;
}while(i);

printf("\ndumping \n");
printRev(start);
}

 

Answer by manojkumargupta at gmail com
Submitted on 10/26/2004
Rating: Not yet rated Rate this answer: Vote
/*
   This program is designed by Manoj Kumar Gupta
   My email id is manojkumargupta@gmail.com

   Note:- This script is designed to help people to understand
   the link list and recursive functions

   This works perfectly with gcc.
*/


#include<stdio.h>

struct node
{
  int val;
  struct node *next;
}*start;

/* here is the function that does your job */
void revList (struct node *list,struct node *priv){
  if (list->next){
  revList(list->next,list);
  }else
  start=list;
  list->next=priv;
}


void dumplist (struct node *list){
    printf ("%d\n", list->val);
  if (list->next)
    dumplist (list->next);
}


main ()
{
  int i = 1;
  struct node *list, *temp;
  printf ("\nThe default value for first and last element is 0\n\n");
  start = (struct node *) malloc (sizeof (struct node));
  start->val = 0;               // by default 0 is start value
  start->next = NULL;
  list = start;
  do
    {
      printf ("(to terminate enter 0) Value:");
      scanf ("%d", &i);
      temp = (struct node *) malloc (sizeof (struct node));
      temp->val = i;
      temp->next = NULL;
      list->next = temp;
      list = temp;
    }
  while (i);

  printf ("\nReversed list is :-\n");
  revList(start,NULL);
  dumplist(start);
  return 0;
}

 

Answer by manojkumargupta
Submitted on 10/26/2004
Rating: Not yet rated Rate this answer: Vote
/* This program is designed by Manoj Kumar Gupta
   My email id is manojkumargupta@gmail.com
   Note:- This script is designed to help people to understand
   the link list and recursive functions
   This works perfectly with gcc. */


#include<stdio.h>

struct node
{
  int val;
  struct node *next;
}*start;

/* here is the function that does your job */
void revList (struct node *list,struct node *priv){
  if (list->next){
  revList(list->next,list);
  }else
  start=list;
  list->next=priv;
}

void dumplist (struct node *list){
    printf ("%d\n", list->val);
  if (list->next)
    dumplist (list->next);
}

main ()
{
  int i = 1;
  struct node *list, *temp;
  printf ("\nThe default value for first and last element is 0\n\n");
  start = (struct node *) malloc (sizeof (struct node));
  start->val = 0;               // by default 0 is start value
  start->next = NULL;
  list = start;
  do
    {
      printf ("(to terminate enter 0) Value:");
      scanf ("%d", &i);
      temp = (struct node *) malloc (sizeof (struct node));
      temp->val = i;
      temp->next = NULL;
      list->next = temp;
      list = temp;
    }
  while (i);

  printf ("\nReversed list is :-\n");
  revList(start,NULL);
  dumplist(start);
  return 0;
}

 

Answer by manokkumargupta at gmail com
Submitted on 11/5/2004
Rating: Not yet rated Rate this answer: Vote
/* This program is designed by Manoj Kumar Gupta
   My email id is manojkumargupta@gmail.com
   Note:- This script is designed to help people to understand
   the link list and recursive functions
   This works perfectly with gcc. */


#include<stdio.h>

struct node
{
  int val;
  struct node *next;
}*start;

/* here is the function that does your job */
void revList (struct node *list,struct node *priv){

  if(list == NULL) return ;

  if (list->next)  revList(list->next,list);
  else start=list;
  list->next=priv;
}

void dumplist (struct node *list){
    printf ("%d\n", list->val);
  if (list->next)
    dumplist (list->next);
}

main ()
{
  int i = 1;
  struct node *list, *temp;
  printf ("\nThe default value for first and last element is 0\n\n");
  start = (struct node *) malloc (sizeof (struct node));
  start->val = 0;               // by default 0 is start value
  start->next = NULL;
  list = start;
  do
    {
      printf ("(to terminate enter 0) Value:");
      scanf ("%d", &i);
      temp = (struct node *) malloc (sizeof (struct node));
      temp->val = i;
      temp->next = NULL;
      list->next = temp;
      list = temp;
    }
  while (i);

  revList(start,NULL);
  printf ("\nReversed list is :-\n");
  dumplist(start);
  return 0;
}

 

Answer by tony
Submitted on 2/4/2005
Rating: Not yet rated Rate this answer: Vote
My answer is great

 

Answer by pankale
Submitted on 2/21/2005
Rating: Not yet rated Rate this answer: Vote

if u can't follow mail me at pankale@rediffmail.com

struct node
{
  int data;
   struct node *next;
};

struct node *first=NULL;
struct node *t_first;

main()
{

  all node creation, deltion , append
  etc. etc calls goes in main.
   to reverse u callthe following function;

   cal_rec(first);

   ............
}

   void cal_rec( struct node *node)
     {
        if(node == NULL) {
          printf(" No list to reverse , create a List \n" );
            }

      else if( node->next == NULL) {
          printf( " Single node Present, no need to reverse \n");
             }
        else
           {
              t_first=first;
              rec(node);
            }

  }
  
  


  void rec(struct node *p)
   {
     struct node *t;

          
     t=p->next;
     if(t!=NULL)
         rec(t);

     if(t == NULL) {
       first= p;
      }

     else if( p == t_first ) {
       first= t_first;
     }

     else
      {
         t->next=p;
       }

}

 

Answer by Hrushik Thakore
Submitted on 4/6/2005
Rating: Not yet rated Rate this answer: Vote
Singly Link List Program
Doubly Link List Program
Circular Link List Program

 

Answer by Sandeep Brahma
Submitted on 4/24/2005
Rating: Not yet rated Rate this answer: Vote
reverse(NODE *List)
{

NODE first,last,temp=NULL;
last=list;

  while(last!=NULL)
  {
    first=last->next;
    last=temp;
    last=first;
  }

}

:Explanation:
//1->2->3->4->~  (~ = NULL)

//1~
//2->1~
//3->2->1->~
//4->3->2->1->~

 

Answer by sirmansoor
Submitted on 5/4/2005
Rating: Not yet rated Rate this answer: Vote
class llist
         {
            int data;
            llist *next;
         }

      main()
      {


           llist *parse,*curr,*first;
         cout<<"Do u wanna give data(y/n)";

         while((ch=getche())=='y')
         {
         llist objList = new llist();
         cout<<"Give value of Data";
         cin>>objList->data;
         if(first==null)
         {
         first = &objList;
         curr = first;
         }
         else
         {
         curr->next = &objList;
         curr = curr->next;
         }
         cout<<"Do u wann give data(y/n)";
         }

         parse = first;
         if(parse != null)
          revllist(parse)
         cout<<"llist complete";

      }


      revllist(llist *parse)
      {
      if(parse->next != null)
       revllist(parse->next);
       cout<<parse->data;
       }

 

Answer by DKB
Submitted on 6/7/2005
Rating: Not yet rated Rate this answer: Vote
This is what I want to know

 

Answer by ashish
Submitted on 6/11/2005
Rating: Not yet rated Rate this answer: Vote
ashish

 

Answer by Kinnari
Submitted on 6/19/2005
Rating: Not yet rated Rate this answer: Vote
Without Recurtion
struct node *p,*q,*r;
r=null;
p=head;
while(p)
{
    q=p->next;
    p->next=r;
    r=p;
    p=q;
}
head=p;

With recurtion
list *tail;  

list *reverse (list *head)  
{  
  if (head->next == NULL)  
  {  
    tail = head;  
    return;  
  }else{  
    reverse (head->next);  
    head->next->next = head;  
    head->next = NULL;  
  }  
}  

 

Answer by Sanjay Kumar
Submitted on 8/22/2005
Rating: Not yet rated Rate this answer: Vote
Node * ReverseList(Node **head, Node *node)
{
  Node * temp;

  if(!node)
  {
    *head = nd;
    return nd;
  }
  
  tmp = ReverseList(head, node->next);
  node-> next = NULL;
  tmp-> next = node;

  return node;
}

}

 

Answer by radium
Submitted on 9/19/2005
Rating: Not yet rated Rate this answer: Vote
#include <stdio.h>

int count = 0;

struct ListObj
{
int num;
ListObj* next;
};

class LinkList
{
public:
LinkList(){m_head = 0;}
~LinkList(){};

ListObj* GetNext(ListObj* cur)
{
  return cur->next;
}

void AddHead(ListObj* temp)
{
  temp->next = m_head;
  m_head = temp;
}


ListObj* GetHead()
{
  return m_head;
}

void Reverselist(ListObj* lastNode, ListObj* ReverseNode)
{
  count++;

  ListObj* head;
  ListObj* next;

  head = GetHead();  
  
  if (ReverseNode == 0)
   return;
  
  next = ReverseNode->next;  
  ReverseNode->next = head;
  lastNode->next = next;  

  m_head = ReverseNode;  
  Reverselist(lastNode, next);
  
}

private:
ListObj* m_head;
};



void main()
{
LinkList list;

for (int i = 0; i<15; i++)
{
  ListObj * temp = new ListObj();
  temp->num = i;
  temp->next = 0;
  list.AddHead(temp);
}

ListObj * head = list.GetHead();
ListObj * cur = head;

for( ;cur!= 0; cur = list.GetNext(cur))
{
  printf("num = %i\n", cur->num);
}

list.Reverselist(head, head->next);

printf("Reversed......\n");
head = list.GetHead();
cur = head;
for( ;cur!= 0; cur = list.GetNext(cur))
{
  printf("num = %i\n", cur->num);
}

printf("Total steps = %i\n", count);
//delete function later...

}

 

Answer by radium
Submitted on 9/19/2005
Rating: Not yet rated Rate this answer: Vote
#include <stdio.h>

int count = 0;

struct ListObj
{
int num;
ListObj* next;
};

class LinkList
{
public:
LinkList(){m_head = 0;}
~LinkList(){};

ListObj* GetNext(ListObj* cur)
{
  return cur->next;
}

void AddHead(ListObj* temp)
{
  temp->next = m_head;
  m_head = temp;
}


ListObj* GetHead()
{
  return m_head;
}

void Reverselist(ListObj* lastNode, ListObj* ReverseNode)
{
  count++;

  ListObj* head;
  ListObj* next;

  head = GetHead();  
  
  if (ReverseNode == 0)
   return;
  
  next = ReverseNode->next;  
  ReverseNode->next = head;
  lastNode->next = next;  

  m_head = ReverseNode;  
  Reverselist(lastNode, next);
  
}

private:
ListObj* m_head;
};



void main()
{
LinkList list;

for (int i = 0; i<15; i++)
{
  ListObj * temp = new ListObj();
  temp->num = i;
  temp->next = 0;
  list.AddHead(temp);
}

ListObj * head = list.GetHead();
ListObj * cur = head;

for( ;cur!= 0; cur = list.GetNext(cur))
{
  printf("num = %i\n", cur->num);
}

list.Reverselist(head, head->next);

printf("Reversed......\n");
head = list.GetHead();
cur = head;
for( ;cur!= 0; cur = list.GetNext(cur))
{
  printf("num = %i\n", cur->num);
}

printf("Total steps = %i\n", count);
//delete function later...

}

 

Answer by raja
Submitted on 10/29/2005
Rating: Not yet rated Rate this answer: Vote
List* reverse2 (List* head, int length) {
      static List** first = NULL;
      static int len = 0;
      len++;
      if ((head == NULL) || (length <=0))
         return NULL;
      else if (head->next == NULL) {
           first = &head;
           return head;
           }
      else {
         List* reversed = reverse2(head->next,length-1);
         reversed ->next = head;
         if (length == len){
             head->next = NULL;
             return *first;
         }            
         return head;
      }
}  

 

Answer by wamra
Submitted on 1/30/2006
Rating: Not yet rated Rate this answer: Vote
here is  an alternative to recursive... would it work ?

int ¤t;
int &last;
int &temp;

current= &LinkList;
last=current;

while(current->next != null)
{
     temp=current->next;
     current->next=last;
     last=current;
     current=temp;    
}

 

Answer by dffd
Submitted on 4/30/2006
Rating: Not yet rated Rate this answer: Vote
dfdffddf

 

Answer by pick
Submitted on 7/11/2006
Rating: Not yet rated Rate this answer: Vote
sumanta

 

Answer by get_rakesh
Submitted on 12/11/2006
Rating: Not yet rated Rate this answer: Vote
void ReverseList2(tagList *p)
{
   static tagList *pr = NULL;
   
   if(p != NULL)
   {
      tagList *tmp = p->next;
      if(tmp ==   NULL)
         First   =   p;
      p->next = pr;
      if(pr==NULL)
         Last=p;
      pr = p;
      p = tmp;
      ReverseList2(p);
   }
}

 

Answer by anon
Submitted on 12/20/2006
Rating: Not yet rated Rate this answer: Vote
http://www.faqs.org/qa/qa-9150.html

 

Answer by sadique
Submitted on 2/22/2007
Rating: Not yet rated Rate this answer: Vote
i want to down load this program

 

Your answer will be published for anyone to see and rate.  Your answer will not be displayed immediately.  If you'd like to get expert points and benefit from positive ratings, please create a new account or login into an existing account below.


Your name or nickname:
If you'd like to create a new account or access your existing account, put in your password here:
Your answer:

FAQS.ORG reserves the right to edit your answer as to improve its clarity.  By submitting your answer you authorize FAQS.ORG to publish your answer on the WWW without any restrictions. You agree to hold harmless and indemnify FAQS.ORG against any claims, costs, or damages resulting from publishing your answer.

 

FAQS.ORG makes no guarantees as to the accuracy of the posts. Each post is the personal opinion of the poster. These posts are not intended to substitute for medical, tax, legal, investment, accounting, or other professional advice. FAQS.ORG does not endorse any opinion or any product or service mentioned mentioned in these posts.

 

<< Back to general questions

[ Home  |  FAQ-Related Q&As  |  General Q&As  |  Answered Questions ]
© 2008 FAQS.ORG. All rights reserved.