第36天。
今天的题目好像是之前就做过的了，Sort List:
Sort a linked list in O(n log n) time using constant space complexity.
要O(nlogn)的算法，显然就是要用归并或快排啦，但是因为他是链表，所以只能是归并排序。
归并排序首先要解决的问题就是，如何分成两半，这里用的方法是快慢指针：
1 ListNode* sortList(ListNode* head) {2 if (head == nullptr || head->next == nullptr ) return head;3
4 ListNode *slow = head;5 ListNode *fast = head;6 ListNode *pre = head;7
8 while(fast && fast->next) {9 pre = slow;10 slow = slow->next;11 fast = fast->next->next;12 }13
14 pre->next = nullptr;15 head = sortList(head);16 collapsed lines
16 slow = sortList(slow);17
18 return mergeList(head,slow);19 }20 ListNode *mergeList(ListNode *p1,ListNode *p2) {21 ListNode ret(0);22 ListNode *p = &ret;23 while(p1&&p2) {24 if (p1->val > p2->val) { p->next = p2; p2 = p2->next; }25 else {p->next = p1; p1 = p1->next; }26 p = p->next;27 }28 if (p1) p->next = p1;29 if (p2) p->next = p2;30 return ret.next;31 }因为是之前做过的，而且好像还写过Blog,所以就不详细写了。