Wednesday, January 16, 2008

Reversing a single linked list recursively

#include <stdio.h>
#include "malloc.h"

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

void insertIntoLL(struct Node **head, int inum)
{
struct Node* temp;
temp = *head;
if(temp == NULL)
{
temp = (struct Node *) malloc(sizeof(Node));
temp->num = inum;
temp->next = NULL;
*head = temp;
}
else
{
while(temp->next != NULL)
temp = temp->next;
temp->next = (struct Node *) malloc(sizeof(Node));
temp->next->num = inum;
temp->next->next = NULL;
}
}

void DisplayLL(struct Node* head)
{
Node* temp = head;
int num = 1;
while(temp != NULL)
{
printf("The value at node %d is %d\n", num, temp->num);
num++;
temp = temp->next;
}
}

Node* ReverseLLRecursively(Node* head)
{
Node *temp;
if(head->next)
{
temp=ReverseLLRecursively(head->next);
head->next->next=head;
head->next=NULL;
}
else
temp=head;
return temp;
}


int _tmain(int argc, _TCHAR* argv[])
{
Node *head = NULL;
insertIntoLL(&head,10);
insertIntoLL(&head,20);
insertIntoLL(&head,30);
insertIntoLL(&head,40);
insertIntoLL(&head,50);
DisplayLL(head);
Node *revHead = ReverseLLRecursively(head);
DisplayLL(revHead);
DisplayLL(head);
return 0;
}


Complexity: SIMPLE.

No comments: