#include <iostream>
using namespace std;
struct node{
	      int data;
	      struct node* next;
};
struct node* createnode(int val)
{
	struct node* p=(struct node*)malloc(sizeof(struct node));
	p->data=val;
	p->next=NULL;
	return p;
}
struct node* split(struct node* head)
{
	struct node* fast=head;
	struct node* slow=head;
	while(fast!=NULL && fast->next!=NULL)
	{
	fast=fast->next->next;
	if(fast!=NULL)
	slow=slow->next;
	}
	struct node* temp=slow->next;
	slow->next=NULL;
	return temp;
}
struct node* merge(struct node* first,struct node* second)
{
	if(first==NULL)
	return second;
    if(second==NULL)
	return first;
	if(first->data<second->data)
	{
		first->next=merge(first->next,second);
		return first;
	}
	else
	{
		second->next=merge(first,second->next);
		return second;
	}
}

struct node* mergesort(struct node* head)
{
	if(head==NULL ||head->next==NULL)
	return head;
struct node* second=split(head);
head=mergesort(head);
second=mergesort(second);
return merge(head,second);
	
}
void printlinked(struct node* head)
{
	while(head!=NULL)
	{
		cout<<head->data<< " ";
		head=head->next;
	}
}
int main() {
	struct node* head=createnode(5);
	head->next=createnode(12);
	head->next->next=createnode(10);
	head->next->next->next=createnode(8);
	head->next->next->next->next=createnode(8);
	struct node* result=mergesort(head);
	printlinked(result);
	return 0;
}