【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 ( n l o g n ) O(nlogn) O(nlogn)，但通常比基于 std::map 的方法更快，因为它具有更好的常数因子和较低的内存使用。

递归分析：

在这里插入代码片