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