Data Structure Linked List: Merge Sort for Linked Lists

#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 ;
}