#include <iostream>
using namespace std;
class node{
    public :
    int data;
    node * next;
    node (int data){
        this->data=data;
        next=NULL;
    }
};
void insertAtHead(node * &head,int data){
    if(head==NULL){
        head=new node(data);
        return ;
    }
    node * n=new node(data);
    n->next=head;
    head=n;

}
void printLinkList(node * head){
    while(head){
        cout<<head->data<<"->";
        head=head->next;
    }
    return ;
}
void insertAtPosition(node * &head,int data,int position){
    if(position==0){
        insertAtHead(head,data);
        return ;
    }
    node * temp=head;
    for(int i=1;i<position;i++){
        temp=temp->next;
    }
    node * n=new node(data);
    n->next=temp->next;
    temp->next=n;
    return ;
}
node * reverseLinkListIterative(node * &head){
    if(head==NULL){
        return NULL;
    }
    if(head->next==NULL){
        return head;
    }
    node * prev=NULL;
    node *temp=NULL;
    node * curr=head;
    while(curr){
        temp=curr->next;
        curr->next=prev;
        prev=curr;
        curr=temp;
      

        
         
    }
    return  prev;


}
node* reverseLinkListRecursive(node * head){
    if(head==NULL ){
        return head;
    }
    if( head->next==NULL){
        return head;
    }
    node * reversedHead=reverseLinkListRecursive(head->next);
   head->next->next=head;
   head->next=NULL;
  //  temp->next=new node(head->data);
    return reversedHead;

    
}
int main() {
    node * head=NULL;
    cout<<"Insert at head function running "<<endl;
   insertAtHead(head,1);
   insertAtHead(head,2);
    insertAtHead(head,3);
    insertAtHead(head,4);
    insertAtHead(head,5);
     cout<<"print inserted link list  "<<endl;
    printLinkList(head);
   insertAtPosition(head,600,5);
    cout<<endl;
    cout<<"insert at any postion "<<endl;
    printLinkList(head);
     cout<<endl;
     cout<<"Reversed Linked List recursive approach "<<endl;
  head=reverseLinkListRecursive(head);
 
printLinkList(head);
    cout<<endl;
    
    cout<<"Reversed Linked List iterative approach "<<endl;
   printLinkList( reverseLinkListIterative(head));

    
}