#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 reversePrint();
void recPrint(Node* temp);
void recReversePrint(Node* temp);

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 0 2 3 7 9
	recPrint(head);
	recReversePrint(head);
	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 recPrint(Node* temp){

	if(temp == NULL) {
		cout<<endl;
		return;
	}
	cout << temp->data << " ";
	recPrint(temp->next);

}
void recReversePrint(Node* temp){

	if(temp == NULL) {
		cout<<endl;
		return;
	}

	recReversePrint(temp->next);
	cout << temp->data << " ";

}