给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

提示：

• 链表中节点的数目在范围 [0, $5\ast 10^4$] 内
• $-10^5$ <= Node.val <= $10^5$

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

建议用vscode时间测试，分别转成数组排序和只在链表基础上操作

题解1 STL - multiset

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {if(!head || !head->next) return head;ListNode* subhead = head;multiset<int> kkset;while(subhead){kkset.insert(subhead->val);subhead = subhead->next;}subhead = head;// 直接改值for(auto& i : kkset){subhead->val = i;subhead = subhead->next;}subhead = nullptr;return head;}
};

题解2 归并【自顶向下】

class Solution {
public:// 递归ListNode* mergesort(ListNode* head, ListNode* tail){if(! head || head->next == tail){// 不含tailif(head) head->next = nullptr;return head;}// 找到head和tail之间的中点(slow)ListNode *fast, *slow;fast = slow = head;while(fast != tail){slow = slow->next;fast = fast->next;if(fast != tail)fast = fast->next;}// ListNode* midnode = slow;// recursion// return  merge(mergesort(head, midnode),  mergesort(midnode, tail));return  merge(mergesort(head, slow),  mergesort(slow, tail));}ListNode* sortList(ListNode* head) {return mergesort(head, nullptr);}// 21.合并两个有序链表ListNode* merge(ListNode*l1, ListNode* l2){ListNode* dummynode = new ListNode(0);ListNode *p = dummynode;dummynode->next = p;while(l1 || l2){if(l1){if(l2 && l1->val <= l2->val){p->next = l1;p = p->next;l1 = l1->next;continue;}if(!l2){p->next = l1;break;}}if(l2){if(l1 && l2->val < l1->val){p->next = l2;p = p->next;l2 = l2->next;continue;}if(!l1){p->next = l2;break;}}}return dummynode->next;}
};

题解3 归并【自底向上】

自底向上：子串长度 l 从1开始，合并后的串长度*2，1+1 -> 2+2 -> 4+4 ->…

// 有时间自己再写一遍
class Solution {
public:ListNode* sortList(ListNode* head) {if (head == nullptr) {return head;}int length = 0;ListNode* node = head;while (node != nullptr) {length++;node = node->next;}ListNode* dummyHead = new ListNode(0, head);for (int subLength = 1; subLength < length; subLength <<= 1) {ListNode* prev = dummyHead, *curr = dummyHead->next;while (curr != nullptr) {ListNode* head1 = curr;for (int i = 1; i < subLength && curr->next != nullptr; i++) {curr = curr->next;}ListNode* head2 = curr->next;curr->next = nullptr;curr = head2;for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++) {curr = curr->next;}ListNode* next = nullptr;if (curr != nullptr) {next = curr->next;curr->next = nullptr;}ListNode* merged = merge(head1, head2);prev->next = merged;while (prev->next != nullptr) {prev = prev->next;}curr = next;}}return dummyHead->next;}ListNode* merge(ListNode* head1, ListNode* head2) {ListNode* dummyHead = new ListNode(0);ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;while (temp1 != nullptr && temp2 != nullptr) {if (temp1->val <= temp2->val) {temp->next = temp1;temp1 = temp1->next;} else {temp->next = temp2;temp2 = temp2->next;}temp = temp->next;}if (temp1 != nullptr) {temp->next = temp1;} else if (temp2 != nullptr) {temp->next = temp2;}return dummyHead->next;}
};