Reverse a singly linked list recursively

Algorithm

Step 1 : create a function that takes a linked list as argument and reverses it.
Step 2 : In the function,
a)    if it is single node or null node just make it as head and return it.
b)    Recursively traverse up end leaving first making the next node to point itself, hence reversing the links.
Step 3 : make next of first node to be Null, which makes it as last node.
Step 4 : call the function on the given Linked list to reverse it.

C++ Program

```#include <bits/stdc++.h>
using namespace std;

struct LL{
int data;
LL *next;
};

void insertAtBeginning(struct LL**head,int dataToBeInserted)
{
struct LL* curr=new LL;

curr->data=dataToBeInserted;
curr->next=NULL;

*head=curr; //if this is first node make this as head of list

else
{
curr->next=*head; //else make the current (new) node's next point to head and make this new node a the head
}

//O(1) constant time
}

void reverseListRecursively(struct LL *root,struct LL**head)
{
if(root->next==NULL) //if this is the only node make it head and return
{
return;
}

else
{
reverseListRecursively(root->next,head); //traverse upto end first
root->next->next=root;  //Make the next node to point itself , hence reversing the links
root->next=NULL;
}
//O(2*number of nodes)

}
{
while(temp!=NULL)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;

temp=temp->next; //move to next node
}
//O(number of nodes)
cout<<endl;
}

int main()
{

struct LL *head = NULL; //initial list has no elements

cout<<"Initial List is :-\n";