Write a c program to reverse a linked list using recursion. Given a singly linked list, we have to write a code to reverse a linked list using recursion. This question is very important in terms of interviews.
In my previous post, I have explained C program to reverse a singly linked list. In this post, We are going to write a code to reverse a linked list using recursion. If you are not familiar with the concept of recursion then check my previous tutorial on recursion vs iteration.
The time complexity to reverse a linked list using recursion is O(n).
Reverse a Linked List using Recursion
What is a Linked List?
Linked list is a linear collection of data elements, called nodes. Each node is connected to a next node by links ( using a pointer). So linked list is a group of nodes which together represent a sequence. Each node consists of two parts a data and a pointer to the next node.
To understand the concept of linked list, let’s practice some questions related to linked list.
C program to count number of nodes in a linked list
C program to insert a node at the beginning of a linked list
C Program to Reverse a Linked List using Recursion
We have discussed what is linked list. Let’s write a c code to reverse a linked list using recursion.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
#include <stdio.h> /* Define struct */ struct node{ int data; struct node* next; }; struct node* head; void insert_node(int data){ /* Create a new node. */ struct node* newnode = (struct node*)malloc(sizeof(struct node*)); newnode->data = data; newnode->next = head; head = newnode; } void reverse(struct node* p){ if(p->next == NULL){ head = p; return; } /* Calling reverse method recursively */ reverse(p->next); struct node* rev = p->next; rev->next = p; p->next = NULL; } void print(){ struct node* p; p = head; while(p!=NULL){ printf("%d\n",p->data); p=p->next; } printf("\n"); } main() { head = NULL; insert_node(2); insert_node(4); insert_node(6); print(); reverse(head); print(); } |
