#include <iostream>
using namespace std;

// To execute C++, please define "int main()"

// The TestCase is shown below
// Input : 1 2
// Output : 3



struct ListNode {

   int val;

      ListNode *next;

    ListNode() : val(0), next(nullptr) {}

    ListNode(int x) : val(x), next(nullptr) {}

    ListNode(int x, ListNode *next) : val(x), next(next) {}

 };



ListNode* merge(ListNode *head, ListNode *leftNode, ListNode *rightNode, ListNode *midNode){
	ListNode *newHead = new ListNode(-1);
	ListNode *realHead = newHead;
	ListNode *p = midNode->next;
	while(leftNode != midNode && p != rightNode){
		if(leftNode->val <= p->val){
			newHead->next = leftNode;
			leftNode = leftNode->next;
		}
		else {
			newHead->next = p;
			p = p->next;
		}
	}
	while(leftNode != midNode){
		newHead->next = leftNode;
		leftNode = leftNode->next;
	}
	while(p != rightNode){
		newHead->next = p;
		p = p->next;
	}
	return realHead->next;
}

ListNode* mergeSort(ListNode *head, ListNode *leftNode, ListNode *rightNode){
	ListNode *newHead = head;
	if(leftNode == rightNode) return leftNode;
	ListNode *midNode = head;
	ListNode *right; 
	while(newHead){
		midNode = midNode->next;
		newHead = newHead->next;
		if(newHead->next == nullptr){
			right = newHead;
		}
		if(newHead) newHead = newHead->next;
		if(newHead->next == nullptr){
			right = newHead;
		}
	}
	mergeSort(head, leftNode, right);
	mergeSort(head, midNode->next, rightNode);
	return merge(head, leftNode, midNode, rightNode);
}

int main() {
	printf("dqwwqddwq");
	ListNode *p[10];
	for(int i = 0; i < 10; i++){
		p[i] = new ListNode(rand()%18);
	}
	for(int i = 0; i < 9; i++){
		p[i]->next = p[i + 1];
	}
	
	printf("dqwwqddwq");
	ListNode *head = mergeSort(p[0], p[0], p[9]);
	while(head){
		printf("%d---", head->val);
		head = head->next;
	}
  	return 0;
}