```
ListNode* Merge(ListNode* left, ListNode* right)
{
ListNode* root = new ListNode(0);
ListNode* node = root;
while(left != NULL && right != NULL)
{
if(left->val < right->val)
{
node->next = left;
left = left->next;
}
else
{
node->next = right;
right = right->next;
}
node = node->next;
}
if(left == NULL)
node->next = right;
if(right == NULL)
node->next = left;
node = root;
root = root->next;
node->next = NULL;
delete node;
return root;
}
ListNode* sortList(ListNode* root)
{
if(root == NULL || root->next == NULL)
return root;
ListNode* quick = root->next;
ListNode* slow = root;
while(quick != NULL && quick->next != NULL)
{
quick = quick->next->next;
slow = slow->next;
}
ListNode* mid = slow->next;
slow->next = NULL;
root = sortList(root);
mid = sortList(mid);
return Merge(root, mid);
}
```