Reverse linked list | Part 2 (Recursive Solution)

Given a singly list it, reverse it using recursion.

 

For example,


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

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

 


 

We have already discussed iterative solutions to reverse the linked list in Part 1. 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 in fact 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++

Download   Run Code

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++

Download   Run Code

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++

Download   Run Code

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.

 
Source: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

 
Thanks for reading.




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 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz