# Reverse a Linked List in C/C++ using Recursion

In this post, we will see how to reverse linked list using recursion in C and C++.

For example,

Input:  1 -> 2 -> 3 -> 4 -> 5 -> nullptr

Output: 5 -> 4 -> 3 -> 2 -> 1 -> nullptr

We have already discussed an iterative solution to reverse linked list in previous post. In this post, we will cover recursive implementation of it. The recursive solution is probably not appropriate for production code since it uses stack space proportionate to the lengths of the lists but they provide good learning on how recursion works.

Below is simple recursive implementation that works by fixing .next pointers of the nodes and finally head pointer of the list. Probably the hardest part is accepting the concept that the reverse(&rest, head) does infact reverse the rest. Then, then there’s a trick to getting the one front node all the way to the end of the list. We recommend to make a drawing to see how the trick works.

## C

Output:

6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

## C++

Output:

6 -> 5 -> 4 -> 3 -> 2 -> 1 -> nullptr

We can also solve this problem by passing only reference to the head pointer to the function as demonstrated below:

## C

Output:

6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

## C++

Output:

6 -> 5 -> 4 -> 3 -> 2 -> 1 -> nullptr

We can simplify above code by passing previous node information to the function. Below is simple recursive implementation of it in C/C++ –

## C

Output:

6 -> 5 -> 4 -> 3 -> 2 -> 1 -> null

## C++

Output:

6 -> 5 -> 4 -> 3 -> 2 -> 1 -> nullptr

The time complexity of above solutions is O(n) and need O(n) extra space for the call stack.

(2 votes, average: 5.00 out of 5)