贵州省住房城乡建设厅网站,网站改版 升级的目的是什么意思,广告牌,自适应和响应式网站文章目录 题目描述法一 自顶向下归并排序法二#xff09;自底向上归并排序 题目描述 题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1) 的空间复杂度#xff0c;时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序#xff08;快速排序的最差时间复杂度是… 文章目录 题目描述法一 自顶向下归并排序法二自底向上归并排序 题目描述 题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1) 的空间复杂度时间复杂度是 O(nlogn) 的排序算法包括归并排序、堆排序和快速排序快速排序的最差时间复杂度是 O(n2其中最适合链表的排序算法是归并排序 法一 自顶向下归并排序 class Solution {
public:ListNode* sortList(ListNode* head){return sortList(head, nullptr);}ListNode* sortList(ListNode* head, ListNode* tail){if(headnullptr){return head;}if(head-nexttail){head-nextnullptr;return head;}ListNode *fasthead, *slow 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 *l1, ListNode *l2){ListNode *dummy new ListNode(-1);ListNode *curdummy, *s1l1, *s2l2;while(s1 s2){if(s1-val s2-val){cur-next s1;s1 s1-next;} else {cur-next s2;s2 s2-next;}cur cur-next;}cur-next s1 ? s1 : s2;return dummy-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;}
};
