https://leetcode.cn/problems/sort-list/?envType=study-plan-v2&envId=top-100-liked148. 排序链表 - 力扣（LeetCode）
一、题目要求
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3] 输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]
示例 3：
输入：head = [] 输出：[]
提示：
- 链表中节点的数目在范围
[0, 5 * 104]内 -105 <= Node.val <= 105
进阶：你可以在 O(nlogn) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
二、解法1-大堆 O(NlogN)
大堆的概念是根大于等于左右节点的二叉树，所以大堆的根一定是最大的，只要把所有节点插入大堆，然后一个一个的将根提取出来尾插即可。
class Solution {
public:ListNode* sortList(ListNode* head) {// 比较器function<bool(ListNode*,ListNode*)> Comp = [](ListNode* n1, ListNode* n2){return n1->val > n2->val;};priority_queue<ListNode*, std::vector<ListNode*>, function<bool(ListNode*, ListNode*)>> maxheap(Comp);ListNode* cur = head;while(cur){maxheap.push(cur);cur = cur->next;}ListNode* newCur = new ListNode();ListNode* newHead = newCur; // 哨兵位while(!maxheap.empty()){newCur->next = maxheap.top();maxheap.pop();newCur = newCur->next;newCur->next = nullptr;}return newHead->next;}
};三、解法2-归并排序 O(NlogN) 进阶
为了让空间复杂度只有O(1)，我们可以使用归并排序，这需要用到合并有序链表的代码。
归并排序的思想是对半分解链表，直到只有一个节点时返回，返回后有两条链表，每条链表一个节点，此时它们是有序的，使用合并有序链表的函数进行合并排序，结果的这一条链表也是有序的，然后再次返回，继续和其他有序链表进行合并排序；
最后就可以得到完成排序好的链表了。
需要注意的是，递归过程中每次分解链表时，除了找到后半部分的头，还要使前半部分的尾节点指向nullptr，因为这样才能使用合并有序链表的函数。
class Solution {
public:ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { // 合并有序链表ListNode* preHead = new ListNode(-1);ListNode* prev = preHead;while (l1 != nullptr && l2 != nullptr) {if (l1->val < l2->val) {prev->next = l1;l1 = l1->next;} else {prev->next = l2;l2 = l2->next;}prev = prev->next;}// 合并后 l1 和 l2// 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可prev->next = l1 == nullptr ? l2 : l1;return preHead->next;}ListNode* _sortList(ListNode* head, int length) { // 归并排序if (length <= 1)return head;ListNode* cur = head;ListNode* first_end = head;for (int i = 0; i < length / 2; i++) { // 找到后半部分的头cur = cur->next;if (i == length / 2 - 2) // 找到前半部分的尾，使它的next指向nullptrfirst_end = cur;}first_end->next = nullptr;return mergeTwoLists(_sortList(head, length / 2),_sortList(cur, length - length / 2));}ListNode* sortList(ListNode* head) {int length = 0;ListNode* cur = head;while (cur) { // 计算长度cur = cur->next;length++;}return _sortList(head, length);}
};