【LeetCode热题100】148. 排序链表（链表）

一.题目要求

给你链表的头结点 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 的方法更快，因为它具有更好的常数因子和较低的内存使用。

递归分析：

在这里插入代码片