先使用快慢指针将找到链表的中点，然后将链表切分成左右两部分，然后对左右指针递归进行排序，最后归并两个已经排序的链表。递归返回的条件是head->next==NULL;
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head == NULL || head->next==NULL) return head;
ListNode * slow = head,* fast = head,*pre = NULL;
while(fast && fast->next){
pre = slow;
slow = slow->next;
fast = fast->next->next;
}
pre->next = NULL;//断开
return merge(sortList(head),sortList(slow));
}
ListNode * merge(ListNode *left,ListNode *right){
ListNode *p = new ListNode(-1);
ListNode *res = p;
while(left!=NULL && right !=NULL){
if(left->val <= right->val) {
res->next = left;
left = left->next;
}else{
res->next = right;
right = right->next;
}
res = res->next;
}
if(left!=NULL) res->next = left;
if(right!=NULL) res->next = right;
//res = p->next;
//free(p);
//p=NULL;
return p->next;
}
};
