在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。
输入
{30,20,40} 输出
{20,30,40}
class Solution { public: ListNode* getmid(ListNode* head) { ListNode *slow = head, *fast = head; //while(slow->next != NULL && fast->next->next != NULL) 写错了，找了好久 while(fast->next != NULL && fast->next->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; } ListNode* merge(ListNode* a, ListNode *b) { ListNode* head = new ListNode(0); //释放 ListNode* res = head; while( a!= NULL && b!=NULL) { if(a->val < b->val) { head->next = a; a = a->next; } else { head->next = b; b = b->next; } head = head->next; } if(b != NULL) a = b; head->next = a; return res->next; } ListNode* sortList(ListNode* head) { // write code here if(head == NULL || head->next == NULL) return head; ListNode* mid = getmid(head); ListNode* midNext = mid->next; mid->next = NULL; return merge(sortList(head), sortList(midNext)); } };1、顺序列表 归并排序算法 2、每次使用快慢两个指针，可用个数替换（第一次直接求得总个数，然后归并排序） 3、时间复杂度 图表引用地址
