DATA STRUCTURES IN C – LINKED LIST (20 PROGRAMS)

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

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”

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

struct node *head=NULL;
//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=one;
    	//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:");
    	printf("\nLinked List:");
    	print(head);

    	head = reverse_using_recursion(head, NULL);
    	//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:");
    	printf("\nLinked List:");
    	print(head);

    	return 0;
}

Output :

Before Reversing:
Linked List:
List:
1
2
3
4

After Reversing:
Linked List:
List:
4
3
2
1