#include <bits/stdc++.h>
using namespace std;

struct node{
	int data;
	node *next;
	node(int d)
	{
		data=d;
		next=NULL;
	}
};
void pushlast(node *& head,int value)
{
	node *temp=new node(value);
	if(head==NULL)
	{
		head=temp;
	}
	else
	{
		node *p=NULL;
		p=head;
		while(p->next!=NULL)
		{
			p=p->next;
		}
		p->next=temp;
	}
}
void pushfront(node *& head,int value)
{
	node* temp=new node(value);
	temp->next=head;
	head=temp;
}
void showlist(node * head)
{
	node *p=NULL;
	p=head;
	while(p->next!=NULL)
	{
		cout<<p->data<<" ";
		p=p->next;
	}
	cout<<p->data<<"\n";
}
void mid(node *head)
{
	node *slow,*fast;
	slow=head;
	fast=head;
	int check=0;
	while(fast!= NULL)
	{
		fast=fast->next;
		check=++check%2;
		if(check==0)
		{
			slow=slow->next;
		}
	}
	cout<<"mid element:"<<slow->data<<"\n";
}
void kth_node_last(node * head,int k)
{
	node *slow,*fast;
	slow=head;
	fast=head;
	cout<<k;
	while(k--)
	{
		fast=fast->next;
	}
	while(fast!=NULL)
	{
		fast=fast->next;
		slow=slow->next;
	}
	cout<<"th element from last:"<<slow->data<<"\n";
}
void reverse(node *& head)
{
	node *curr,*prev,*upnext;
	curr=head;
	prev=NULL;
	upnext=head;
	while(curr!=NULL)
	{
		upnext=curr->next;
		curr->next=prev;
		prev=curr;
		curr=upnext;
	}
	head=prev;
}

node * merge(node *a,node * b)
{

	if(b==NULL)
	{
		return a;
	}

	if((a->data) <= (b->data))
	{
		node *temp=NULL;
		temp=a->next;
		a->next=b;
		b=temp;

	}
	else
	{
		node *temp=NULL;
		temp=b->next;
		b->next=a;
		a=b;
		b=temp;
	}
	a->next=merge(a->next,b);
 return a;
}

void loop(node *head)
{
	node *slow,*fast;
	slow=head;
	fast=head->next;
	while(slow!=fast){
		slow=slow->next;
		fast=fast->next->next;
		if(fast->next==NULL)
		{
			cout<<"loop is not present";
			return;
		}
	}
	cout<<"loop is present";
}

int main()
{
	node *a=NULL,*b=NULL;
	pushlast(a,2);
	pushlast(a,5);
	pushlast(a,6);
	pushlast(a,9);
	pushlast(a,10);
	pushlast(b,4);
	pushlast(b,7);
	pushlast(b,8);
	pushlast(b,12);
	pushfront(b,1);
	cout<<"a is :";
	showlist(a);
	cout<<"\nb is: ";
	showlist(b);
	a=merge(a,b);
	cout<<"\nnew a :";
	showlist(a);
	cout<<"\nnew b :";
	showlist(b);

	// node *head=NULL;
	// pushlast(head,5);
	// pushlast(head,6);
	// pushlast(head,8);
	// pushfront(head,9);
	// pushfront(head,1);
	// pushfront(head,10);
	// pushfront(head,11);
	// pushfront(head,15);
	// showlist(head);
	// mid(head);
	// kth_node_last(head,5);
	// reverse(head);
	// showlist(head);

}



// if((a->next==NULL)||(b==NULL))
// 	{
// 		return NULL;
// 	}
// 	if(a->data <= b->data)
// 	{
// 		node *temp=a;
// 		temp=temp->next;
// 		a->next=b;
// 		b=temp;

// 	}
// 	else if(a-> data > b->data)
// 	{
// 		a=a->next;
// 	}
// 	a->next=merge(a,b);
//  return a;