给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
先贴上我的通过页面，用时和内存都算前列，超过93.12%，不可思议，因为我的思路很简单，代码也就几行。
再看官方的代码和时空大小，代码特别长，非常容易写错，而且性能表现平平无奇。
leetcode官方ac代码：
//自顶向下归并 class Solution { public: ListNode* sortList(ListNode* head) { return sortList(head, nullptr); } ListNode* sortList(ListNode* head, ListNode* tail) { if (head == nullptr) { return head; } if (head->next == tail) { head->next = nullptr; return head; } ListNode* slow = head, *fast = head; while (fast != tail) { slow = slow->next; fast = fast->next; if (fast != tail) { fast = fast->next; } } ListNode* mid = slow; return merge(sortList(head, mid), sortList(mid, tail)); } 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; } }; //自底向上归并 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; } };
我的思路：正常排序大家都会写，链表排序呢，正是因为他没有随机读取的原因，两层遍历用时很久。那我们把他转换成数组，排序完，再转回来不就行了么？（这个方法当然也有局限性，但是能够投机取巧的还是可以的）
ac代码（详细注释）
class Solution { public: ListNode* sortList(ListNode* head) { ListNode *cur = head; // 创建一个指针cur并初始化为头节点 vector<int> s; // 创建一个vector s，用于存储链表节点的值 // 将链表节点的值存储到vector s中 while(cur != nullptr) { s.push_back(cur->val); cur = cur->next; // 移动cur指针到下一个节点 } cur = head; // 将cur重新指向头节点，用于重新排列链表节点的值 // 对vector s中的值进行排序 sort(s.begin(), s.end()); // 将排序后的值重新赋给链表节点 for(int i = 0; i < s.size(); i++) { cur->val = s[i]; cur = cur->next; // 移动cur指针到下一个节点 } return head; // 返回排序后的链表 } };
