Reverse Linked-List (recursive)

Problem Statement :

             Reverse a Linked List recursively (don't use any extra space either)

Solution: 

 Here in this problem we need to reverse a singly linked list recursively without using any extra space, below diagram show how a revered linked list would look like.

Reversing the linked list can be achieved through
1. Iterative method (by maintaining 3 pointers)
2. Using stack ( as push and pop operation reverses the data set)
3. Recursive approach


Approach to reverse the Linked List using recursion is discussed below.
   Recursive calls are made

Intermediate steps while reversing the linked list are shown below:

Full Source Code is here

The sub-routine to reverse is shown below.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

/** * Reverse Linked List (recursively) * @param head : the start pointer of the linked List * @return: new head Pointer */ public Node reverse(Node head){ Node revHead ; // to store the new Head pointer if( head== null || head.next==null ) return head; revHead=reverse(head.next) ; head.next.next = head; // points to itself to create loop head.next = null; // breaks the loop (old link) return revHead ; }