#include <bits/stdc++.h>
using namespace std;
struct node
{
int val;
string name;
node* nxt;
};
node* getnewnode()
{
node* newly = new node();
newly->val = 0;
newly->name = "END";
newly->nxt = NULL;
return newly;
}
//node *head = NULL;
void show(node* head){
node* trav = head;
while(trav)
{
cout << trav->val << " "<<trav->name << endl;
trav = trav->nxt;
}
}
void addmiddle(int position,node* head)
{
node* temp = getnewnode();
node *t = head;
for(int i=0;i<position-2;i++)
t = t->nxt;
temp->nxt = t->nxt;
t->nxt = temp;
}
void printrev(node* temp)
{
if(temp==NULL)
{
cout << "reverse print"<<endl; return;
}
printrev(temp->nxt);
cout << temp->val << " "<<temp->name << endl;
}
node* reversebyiter(node* head)
{
node* current=head,*prev=NULL,*next;
while(current)
{
next = current->nxt;
current->nxt = prev;
prev = current;
current = next;
}
head = prev;
return head;
}
node* forrest;
node* reversebyrecur(node* head)
{
if(head->nxt == NULL)
{
forrest = head;
return head;
}
reversebyrecur(head->nxt);
node *temp=head->nxt->nxt;
head->nxt->nxt = head;
head->nxt = NULL;
return forrest;
}
int main() {
node *head = NULL;
bool intheend = 1;
bool inthemiddle = 1;
for (int i=0;i<5;i++)
{
node *temp = getnewnode();
cin >> temp->val;
cin >> temp->name;
//temp->nxt = head;
//head=temp;
if (head == NULL)
{
temp->nxt = head;
head=temp;
}
else
if(intheend == 1)
{
node* t2 = head;
while(t2->nxt)
{
t2 = t2->nxt;
}
t2->nxt = temp;
}
}
show(head);
addmiddle(3,head);
cout<<"------------------------------------------------"<<endl;
show(head);
cout<<"------------------------------------------------"<<endl;
node* k = head;
printrev(k);
cout<<"------------------------------------------------"<<endl;
show(head);
head = reversebyiter(head);
cout<<"revrsed the linked list-------------------------"<<endl;
show(head);
head = reversebyrecur(head);
cout<<"revrsed the linked list 2 by recur--------------"<<endl;
show(head);
return 0;
}