#include
using namespace std;
class Node{
public:
int data;
Node *next;
Node(int d){
data=d;
next=NULL;
}
};
void insertAtHead(Node *&head,int data){
Node *n=new Node(data);
n->next=NULL;
head=n;
}
int length(Node *head){
Node *temp=head;
int len;
while(temp->next!=NULL){
len+=1;
temp=temp->next;
}
return len;
}
void insertAttail(Node *head,int data){
if(head==NULL){
head=new Node(data);
return;
}
Node *tail=head;
while(tail->next!=NULL){
tail=tail->next;
}
Node *n=new Node(data);
tail->next=n;
return;
}
void insertAtmiddle(Node *&head,int data,int pos){
if(head==NULL)
insertAtHead(head,data);
else if(pos>length(head)){
insertAttail(head,data);
}
else{
int jump=1;
Node *temp=head;
while(jump<=pos-1){
temp=temp->next;
}
Node *n=new Node(data);
n->next=temp->next;
temp->next=n;
}
}
void print(Node * head){
Node *temp=head;
while(temp->next!=NULL){
cout<data<<" ";
temp=temp->next;
}
}
int main(){
Node *head=NULL;
insertAtHead(head,3);
insertAtHead(head,4);
insertAtHead(head,5);
insertAttail(head,7);
insertAtmiddle(head,20,3);
print(head);
return 0;
}