一.题目要求
给你链表的头结点 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 = []
输出：[]
四.解题思路
解法1：用map按值大小存结点
解法2：归并排序(GPT)
五.代码实现
解1
/**
* 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) {
ListNode* dummy = new ListNode(0);
map<int,vector<ListNode*>> nodeMap;
while(head)
{
nodeMap[head->val].push_back(head);
head = head->next;
}
ListNode* p = dummy;
for(auto node : nodeMap)
{
for(vector<ListNode*>::iterator it = node.second.begin(); it != node.second.end(); it++)
{
(*it)->next = nullptr;
p->next = *it;
p = p->next;
}
}
return dummy->next;
}
};
解2
class Solution {
public:
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* mid = getMid(head);
ListNode* left = sortList(head);
ListNode* right = sortList(mid);
return merge(left, right);
}
private:
ListNode* getMid(ListNode* head) {
ListNode* midPrev = nullptr;
while (head && head->next) {
midPrev = (midPrev == nullptr) ? head : midPrev->next;
head = head->next->next;
}
ListNode* mid = midPrev->next;
midPrev->next = nullptr; // 断开链表
return mid;
}
ListNode* merge(ListNode* list1, ListNode* list2) {
ListNode dummy(0);
ListNode* ptr = &dummy;
while (list1 && list2) {
if (list1->val < list2->val) {
ptr->next = list1;
list1 = list1->next;
} else {
ptr->next = list2;
list2 = list2->next;
}
ptr = ptr->next;
}
ptr->next = (list1) ? list1 : list2;
return dummy.next;
}
};
六.题目总结
归并排序在链表排序中非常有效，因为它可以利用链表的节点指针操作，无需像数组那样进行大量的元素交换，其时间复杂度是 O(NlogN)，但通常比基于 std::map 的方法更快，因为它具有更好的常数因子和较低的内存使用。
递归分析：
在这里插入代码片
