网站开发实践意义,领地免费网站,重庆模板做网站,查询网站备案密码一.题目要求
给你链表的头结点 head #xff0c;请将其按 升序 排列并返回 排序后的链表 。
二.题目难度
中等
三.输入样例
示例 1#xff1a; 输入#xff1a;head [4,2,1,3] 输出#xff1a;[1,2,3,4]
示例 2#xff1a; 输入#xff1a;head [-1,5,3,4,0] 输…一.题目要求
给你链表的头结点 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);mapint,vectorListNode* nodeMap;while(head){nodeMap[head-val].push_back(head);head head-next;}ListNode* p dummy;for(auto node : nodeMap){for(vectorListNode*::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 的方法更快因为它具有更好的常数因子和较低的内存使用。
递归分析
在这里插入代码片
