#include<iostream>

using namespace std;

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

Node* head;

void print();
void insert(int x, int pos);
void deleteNode(int pos);
void insertAtEnd(int x);
void reverseRev(Node* head);

int main(){
	head = NULL;

	insert(2,1); //2
	insert(3,2); //2 3
	insert(6,1); //6 2 3
	insert(0,2); //6 0 2 3
	insertAtEnd(7); // 6 0 2 3 7
	insertAtEnd(9); // 6 0 2 3 7 9
	insert(5,2); //6 5 2 3 7 9
	print();
	reverseRev(head);
	print();
	return 0;
}

void insert(int x, int pos){
	Node* temp  = head;
	Node* n = new Node();
	n->data = x;
	if(pos == 1){
		n->next = head;
		head = n;
		return;
	}

	for(int i =1;i<=pos-2;i++){
		temp=temp->next;
	}

	n->next = temp->next;
	temp->next = n;

}

void print(){
	Node* temp = head;

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


void insertAtEnd(int x){
	Node* temp = new Node();
	temp->data = x;
	temp->next = NULL;

	Node* ptr = head;
	while(ptr->next!=NULL){
		ptr = ptr->next;
	}
	ptr->next = temp;
}

void reverseRev(Node* ptr){

	if(ptr->next == NULL){
		head = ptr;
		return;
	}

	reverseRev(ptr->next);
	Node* temp = ptr->next;
	temp->next = ptr;
	ptr->next = NULL;
}