Reverse linked list with recursive function with detailed explanation

Hi Guys,

Here i am going to explain how to reverse linked list with recursive function.

There are two ways to reverse a linked list.

1. Iterative way
2. Recursive function

But i gonna explain the second one (Recursive function).

It hardly takes just 7 lines of code to reverse the linked list. But understanding the recursive function is very difficult unless you know the recursive call.

I am gonna explain in very easy manner , so that every body can understand it.

Lets take the below linked list.

7, 12, 14, 6, 8

Below method initially takes head node as a parameter  and starts with execution.

public static Node reverseNode(Node node) {  

     if (node == null || node.next == null) {  

         return node;  

     }  

     Node remaining = reverseNode(node.next);  

     node.next.next = node;  

     node.next = null;  

    return remaining;  

 }

But with the above piece of code its very hard to understand the concept. So i expanded the above code in JVM stack call , so that everybody can understand very easily.

Above function will stop executing when last node(8) 's next will be null.so while returning when you reach at node with value 6,If you closely observe node.next.next=node is actually setting 8-6(i.e. reversing the link between node with value 6 and 8) and node.next=null is removing link 6->8. So in each iteration, you are reversing link between two nodes

output is : 8 , 6, 14, 12, 7

Click to Read more Data structure questions and answer