# Reverse linked list | Recursive Solution

In this post, we will see how to reverse linked list using recursion.

For example,

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

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

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, headRef) 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

We can also solve this problem by passing only reference to the head pointer to the function. i.e. reverse(&head).

## C++

Output:

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

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

## C++

Output:

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

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

Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂

Get great deals at Amazon