148. 排序链表 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

快慢指针 找中点//slow：（5个停在3,10个停在5）

class Solution { public: ListNode* sortList(ListNode* head) { if(head==NULL||head->next==NULL) return head; // /*快慢指针 查找剧中节点*/ // ListNode* fast=head, *slow=head; // ListNode* tmp=head; // while(fast!=nullptr&&fast->next!=nullptr){ // tmp=slow; // fast=fast->next->next; // slow=slow->next; // } // tmp->next=NULL; // ListNode* left=sortList(head); // ListNode* right=sortList(slow); ListNode* fast=head->next,* slow=head; while(fast&&fast->next){ fast=fast->next->next; slow=slow->next; } ListNode* pre=slow->next; slow->next=NULL; ListNode* left=sortList(head); ListNode* right=sortList(pre); return merge(left,right); }

后面那一种查找中点的方式更加简单，巧妙之处在于“fast=head->next;"

ListNode* merge(ListNode* left, ListNode* right) { ListNode* result=new ListNode(0); ListNode* cur=result; while(left!=NULL&&right!=NULL){ if(left->val<right->val) { cur->next=left; cur=cur->next; left=left->next; } else{ cur->next=right; cur=cur->next; right=right->next; } } if(left!=NULL){ cur->next=left; } if(right!=NULL){ cur->next=right; } // cur->next=(left==NULL? right:left); return result->next; }