Reverse a singly linked list : Recursively

Following approach can be followed to reverse a singly linked list recursively



Approach : 

1.Divide the list in two parts : first and rest.
2.Recursively call the reverse method with rest.
3.link rest-->first
4.fix the last node

Implementation: 


public node reverse(Node head){

if( head==null) return;

Node first= head;
Node rest= first.next;

if(rest== null) return;

reverse(rest); //recursively call reverse for the rest .

first.next.next= first;// next now points to current

first.next = null; //fix the last node

head= rest;

return head;

}

Complexity :

Time: O(n)
Space: O(1)