Write a program to reverse a linked list using recursion. Given a linked list print them in reverse order using recursion. This question is mostly asked in interviews.

In my last post, I have explained how to reverse a linked list using an iterative approach. In this post, We will learn how to reverse a linked list using recursion. The time complexity for both iterative and recursive approach is O(n).

**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 next node.

I assume you have basic understand of recursion. If you are not familiar with recursion then check my previous post on recursion concept and difference between recursion and iteration.

## Program 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. */ 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(); } |

Some more questions on linked list –