先使用快慢指針將找到鏈表的中點，然后將鏈表切分成左右兩部分宣蔚，然后對左右指針遞歸進行排序痛倚，最后歸并兩個已經排序的鏈表咬展。遞歸返回的條件是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;
}
};
