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

Download   Run Code

Output:

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

C++

Download   Run Code

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

Download   Run Code

Output:

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

C++

Download   Run Code

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

Download   Run Code

Output:

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

C++

Download   Run Code

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.

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (2 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
newest oldest most voted
Notify of
Neha
Guest

I understood the first and third method, i cant understand the 2nd one. In 2nd, I noticed that the variable rest is having the same value for all the recursion call once the code reached beyond the recursiveReverse(&rest). But first->next has different values. I was able to understand why first->next has different values by writing them on a stack and comparing it with each call. But i could not understand how rest is having the same value for all the calls instead of the (rest = first->next) from the stack. Pls explain.
Is it because we are passing the address of rest in the function call? Is it matched by the same name of the variable?