Untitled

#include <iostream>
using namespace std;


class Node{
	
public:
	int data;
	Node * link; // self refrential structures
	
	Node(int d){
		data = d;
		link = NULL;
	}
	
	~Node(){
		
	}
	
};

void print(Node * head){
	while(head){
		
		cout << head->data << ",";
		head = head->link;
	}
	
	cout << endl;
}

void insert(int data, Node * &head){
	
	// starting node
	if(head == NULL){
		head = new Node(data);
		return;
	}
	
	// 1-2-3
	Node * temp = head;
	while(temp->link){
		temp = temp->link;
	}
	
	temp->link = new Node(data);
	return;

}

Node * midpoint(Node * head){
	
	if(!head) return NULL;
	
	Node * slow = head;
	if(head->link == NULL){
		return slow;
	}
	
	
	Node * fast = head->link;
	while(fast!=NULL and fast->link!=NULL){
		slow = slow->link;
		fast = fast->link->link;
	}
	
	return slow;
	
}

Node * merge(Node * a, Node * b){
	
	if (a == NULL){
		return b;
	}
	
	if (b == NULL){
		return a;
	}
	
	Node * c;
	if(a->data < b->data){
		c = a;
		c->link = merge(a->link, b);
	} else {
		c = b;
		c->link = merge(a, b->link);
	}
	
	return c;
}


Node * mergeSort(Node * head){
	
	/// base case
	if (head == NULL or head->link == NULL){
		return head;
	}
	
	// Steps of merge sort
	// 1. Mid point
	// 2. Sort individual partitions
	// 3. Merge
	
	// Step 1
	Node * mid = midpoint(head);
	
	// Step 2
	Node * a = head;
	Node * b = mid->link;
	mid->link = NULL;
	
	a = mergeSort(a);
	b = mergeSort(b);
	
	return merge(a, b);
	
}


void buildList(Node * &head){
	
	int data;
	cin >> data;
	
	while(data != -1){
		insert(data, head);
		cin >> data;
	}
	
}



int main() {
	// your code goes here
	
	Node * head = NULL;
	buildList(head);
	print(head);
	Node * mid = midpoint(head);
	cout << mid->data << endl;
	head = mergeSort(head);
	print(head);
	return 0;
}