ListNode *sortList(ListNode *head){

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

ListNode* p = head, *q = head->next;

while (q && q->next)

{

p = p->next;

q = q->next->next;

}

ListNode* left = sortList(p->next);

p->next = NULL;

ListNode* right = sortList(head);

return merge(left, right);

}

ListNode* nerge(ListNode* left, ListNode* right){

ListNode dummy(0);

ListNode* p = &dummy;

while (left && right)

{

if (left->val < right->val)

{

p->next = left;

left = left->next;

}else

{

p->next = right;

right = right->next;

}

p = p->next;

}

if (left) p->next = left;

if (right) p->next = right;

return dummy.next;

}