免费个人博客网站模板下载,平面设计图片大全,可以做哪些网站有哪些,auto post wordpress文章目录 写在前面Tag题目来源解题思路方法一#xff1a;链表转数组方法二#xff1a;自顶向下归并排序方法三#xff1a;自底向上的归并排序 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内… 文章目录 写在前面Tag题目来源解题思路方法一链表转数组方法二自顶向下归并排序方法三自底向上的归并排序 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【链表】【分治】【归并排序】 题目来源
148. 排序链表 解题思路
方法一链表转数组
一种朴素的解法是将链表中的节点存储到数组中然后对数组按节点值进行升序排序排好序后将节点数组再连接成一条链表。该方法比较简单直接给出代码。
代码
/*** 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:// 自定义排序的仿函数struct myclass {bool operator() (ListNode *n1, ListNode *n2) {return n1-val n2-val;}} myobject;ListNode* sortList(ListNode* head) {if (head nullptr || head-next nullptr) {return head;}vectorListNode* tmp;ListNode *curr head;while (curr ! nullptr) {tmp.push_back(curr);curr curr-next;}sort(tmp.begin(), tmp.end(), myobject);int n tmp.size();head tmp[0];curr head;for (int i 1; i tmp.size(); i) {curr-next tmp[i];curr curr-next;}// 最后一个结点的next要置空curr-next nullptr;return head;}
};复杂度分析
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) n n n 是链表中节点个数。本题的时间瓶颈在于排序的时间复杂度。
空间复杂度 O ( n ) O(n) O(n)使用一个额外的数组记录链表中的节点的空间复杂度为 O ( n ) O(n) O(n)。最坏情况下需要排序的序列是逆序的需要 n 次递归调用。因此需要 O ( n ) O(n) O(n) 的栈空间
方法二自顶向下归并排序
对链表进行自顶向下的归并排序步骤如下
找到链表的中点以中点为分界将链表拆分成两个子链表。寻找链表的中间节点可以使用快慢指针来实现快指针每次移动 2 步慢指针每次移动 1 步当快指针到达链表末尾时慢指针指向的链表节点即为链表的中点。递归对两个子链表进行排序。将两个升序的子链表进行合并。合并两个有序链表可以参考 【面试经典150 | 链表】合并两个有序链表。
代码
/*** 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 {
private:ListNode* sortList(ListNode* head, ListNode* tail) {if (head nullptr) { // 递归出口return head;}if (head-next tail) { // 递归出口head-next nullptr;return head;}ListNode* slow head, *fast 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* head1, ListNode* head2) {ListNode* dummy new ListNode(0);ListNode* prev dummy;while (head1 head2) {if (head1-val head2-val) {prev-next head1;head1 head1-next;}else {prev-next head2;head2 head2-next;}prev prev-next;}prev-next head1 ? head1 : head2;return dummy-next;}
public:ListNode* sortList(ListNode* head) {return sortList(head, nullptr);}
};复杂度分析
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) n n n 是链表中节点个数。
空间复杂度 O ( l o g n ) O(logn) O(logn)空间复杂度取决于递归调用的占空间。
方法三自底向上的归并排序
归并排序除了自顶向下实现也可自底向上实现。自底向上的归并排序空间复杂度为 O ( 1 ) O(1) O(1)。
首先要求出链表的长度 len。利用迭代可以轻松求出。
接着将链表拆分成子链表进行合并具体步骤如下
枚举需要排序的子链表长度自底向上的排序初始化子链表长度 subLen 1。每次将链表拆分成若干个长度为 subLen 的子链表最后一个链表的长度可以小于 subLen按照每两个子链表一组进行合并合并后即可得到若干个长度为 subLen × 2 的有序子链表最后一个子链表的长度可以小于 subLength × 2。合并两个子链表仍然使用「21. 合并两个有序链表」的做法。将 subLen 的值加倍重复第 2 步对更长的有序子链表进行合并操作直到有序子链表的长度大于或等于 len整个链表排序完毕。
代码
/*** 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 {
private:ListNode* merge(ListNode* head1, ListNode* head2) {ListNode* dummy new ListNode(0);ListNode* prev dummy;while (head1 head2) {if (head1-val head2-val) {prev-next head1;head1 head1-next;}else {prev-next head2;head2 head2-next;}prev prev-next;}prev-next head1 ? head1 : head2;return dummy-next;}public:ListNode* sortList(ListNode* head) {if (head nullptr) {return head;}int len 0;ListNode* node head;while (node ! nullptr) {len;node node-next;}ListNode* dummy new ListNode(0, head);for (int subLen 1; subLen len; subLen 1) {ListNode* prev dummy, *cur dummy-next;while (cur) {ListNode* head1 cur; // 第一个长度为 subLen 的子节点开头for (int i 1; i subLen cur-next; i) {// 第一个 subLen 子节点末尾的节点cur cur-next;}ListNode* head2 cur-next;// 第二个长度为 subLen 的子节点开头cur-next nullptr;cur head2;for (int i 1; i subLen cur cur-next; i) {// 第二个 subLen 子节点末尾的节点cur cur-next;}ListNode* next nullptr; // 维护下一个长度为 subLen 的子节点开头if (cur) {next cur-next;cur-next nullptr;}ListNode* merged merge(head1, head2);prev-next merged; while (prev-next) {prev prev-next;}cur next;}}return dummy-next;}
};复杂度分析
时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn) n n n 是链表中节点个数。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
