148 排序链表

解题思路：
\qquad 题目希望能在$O(nLogn)$时间复杂度内解决问题，满足这个条件的常用排序算法有：快速排序（Quick Sort）、归并排序（Merge Sort）和堆排序（Heap Sort）。

• 由于链表节点中的next指针，使节点按特定顺序链接。因而不适合频繁的移动元素，所以快速排序对于链表，用起来不是很方便。
• 堆排序，是利用堆这一数据结构的特点进行排序，将待排序元素存入栈，每次取堆顶的元素，自然是有序的。但要将链表节点存入栈，需要重写堆的排序方法，略微有些麻烦。
• 归并排序，将序列不断二分，对左右两个序列继续排序后，将返回的两个有序序列按顺序合并的排序算法。无论是二分，还是合并有序序列，都可以按照从左至右的顺序访问元素并完成，因此十分适合对链表排序。

\qquad 代码实现有几个注意的点：
\qquad 可以使用快慢指针，快速找到链表中间的节点；
\qquad 使用自定义节点做一个伪head，这样可以少判head为空的情况，返回时也要注意返回head->next;
\qquad 递归的终止条件，除了head为空之外，链表内只有一个元素的情况也要返回，不然会陷入死循环。

ListNode* sortList(ListNode* head) {if(head == nullptr || head->next == nullptr) return head;ListNode* slow;ListNode* fast = head;while(fast != nullptr){if(fast == head) slow = head;else slow = slow->next;if(fast->next == nullptr) fast = nullptr;else fast = fast->next->next;}if(slow != nullptr){fast = sortList(slow->next);slow->next = nullptr;}else fast = sortList(nullptr);slow = sortList(head);ListNode* joined = new ListNode(0);ListNode* curr = joined;while(slow != nullptr || fast != nullptr){if(slow != nullptr && fast != nullptr){if(slow->val <= fast->val){curr->next = slow;slow = slow->next;}else {curr->next = fast;fast = fast->next;}curr = curr->next;}else if(slow == nullptr){curr->next = fast;break;}else{curr->next = slow;break;}}return joined->next;}