#include <iostream>

 #include <vector>

 #include <algorithm>

 #include <queue>

 #include <stack>

 #include <string>

 #include <fstream>

 #include <map>

 #include <set>

 using namespace std;

 struct node {

     int data;

     node *next;

     node() : data(), next(NULL) { }

     node(int d) : data(d), next(NULL) { }

 };

 void push(node* &head, int k) {

     node *new_node = new node(k);

     new_node->next = head;

     head = new_node;

 }

 void print(node* head) {

     if (!head) return;

     cout << head->data << " ";

     print(head->next);

 }

 void frontbacksplit(node *head, node *&a, node *&b) {

     node *p, *q;

     if (!head || !head->next) {

         a = head;

         b = NULL;

         return;

     }

     p = head;

     q = head->next;

     while (q) {

         q = q->next;

         if (q) {

             q = q->next;

             p = p->next;

         }

     }

     a = head;

     b = p->next;

     p->next = NULL;

 }

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

     node *ans = NULL;

     if (!a) return b;

     if (!b) return a;

     if (a->data < b->data) {

         ans = a;

         ans->next = sortmerge(a->next, b);

     }

     else {

         ans = b;

         ans->next = sortmerge(a, b->next);

     }

     return ans;

 }

 void mergesort(node *&head) {

     if (!head || !head->next) return;

     node *a, *b;

     node *h = head;

     frontbacksplit(h, a, b);

     mergesort(a);

     mergesort(b);

     head = sortmerge(a, b);

 }

 int main() {

     node *head = NULL;

     push(head, );

     push(head, );

     push(head, );

     push(head, );

     push(head, );

     push(head, );

     mergesort(head);

     print(head);

     return ;

 }