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 –

Insert a node at the head of a linked list

Count number of nodes in a linked list

Algorithm to reverse a linked list using iteration

1. We will use three node pointer “previous”, “current” and “next” to keep track of previous, current and next node during linked list reversal.

2. Initialize current pointer to head and previous pointer to NULL.

3. Traverse linked list from head till current->next != NULL.

4. In every iteration, set current->next = previous; and move all three pointers to next node.

5. Return previous pointer. This is the new head pointer of reversed linked list.