Linked List in C- Reversing a Linked List using Recursion

## Linked List in C- Reversing a Linked List using Recursion :

Input:
head pointer points to first node “one”

Output:
head pointer points to first node “four”

Source Code :

```#include<stdio.h>

//Input:
//	Linked List: one->two->three->four
//	head pointer points to first node "one"
//
//Output:
//	Linked List: four->three->two->one
//	head pointer points to first node "four"

struct node
{
//Structure named node to store integer in variable data and a pointer variable which can store address location of next node
int data;
struct node *next;
//Pointer variable next is a self referential pointer which stores the address of structure node
};

//Pointer head is used to store the starting node of the input linked list

void print(struct node *temp)
{
//This funtion is used to print the data in each of the node in the linked list
//Process of moving from one node to another node is called as traversing
printf("\nList:");
while(temp!=NULL)
{
printf("\n%d ",temp->data);
temp=temp->next;
}
}

struct node *reverse_using_recursion(struct node *ptr , struct node *previous)
{
//Recursive function to reverse a linked list

struct node *temp;
//Pointer to store the address of return value

if(ptr->next == NULL)
{
//Exit condition for recursive function is most important thing to consider.Else the recursive function will be called infinitely
//The condition will be true for last node i.e the node with next pointer NULL
ptr->next = previous;
return ptr;
}
else
{
temp = reverse_using_recursion(ptr->next, ptr);
//Passing the address of next node and address of current node

ptr->next = previous;
//Making a node point to previous node
return temp;
}
}

int main()
{
struct node *one = (struct node*)malloc(sizeof(struct node));
struct node *two = (struct node*)malloc(sizeof(struct node));
struct node *three = (struct node*)malloc(sizeof(struct node));
struct node *four = (struct node*)malloc(sizeof(struct node));
//Four nodes are created

//head points to node one of input linked list

one->data=1;
one->next=two;

two->data=2;
two->next=three;

three->data=3;
three->next=four;

four->data=4;
four->next=NULL;
//End of linked list

//one->two->three->four

printf("\nBefore Reversing:");

//Recursive function is called to reverse the linked list
//The addess of last node is returned by the recursive function which is stored in pointer "head"

printf("\nAfter Reversing:");

return 0;
}```

Output :

```Before Reversing: