响应式培训网站模板,国药控股cms系统,图书管理系统网站开发绪论,网站建设心得8000字文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言
链表排序处理起来比较麻烦#xff0c;因为它不支持下标操作。这里写一下链表排序的常用方法。 题目
描述 给定一个节点数为n的无序单链表#xff0c;对其按升序排序。
数据范围… 文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言
链表排序处理起来比较麻烦因为它不支持下标操作。这里写一下链表排序的常用方法。 题目
描述 给定一个节点数为n的无序单链表对其按升序排序。
数据范围 0 n ≤ 100000 0n≤100000 0n≤100000保证节点权值在 [ − 1 0 9 , 1 0 9 ] [−10^9,10^9] [−109,109]之内。 要求空间复杂度 O ( n ) O(n) O(n)时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
解决方案一
1.1 思路阐述
链表不支持下标运算那就用数组来做。
先把链表的所有数据存放到一个数组中对数组进行排序直接调用C的库函数sort。
将排序完好数组一个一个给到新的链表即可。 缺点如果链表数据量太大那么开辟的空间也会很大。
1.2 源码
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
#include algorithm
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 the head node* return ListNode类*/ListNode* sortInList(ListNode* head) {// 所有数据存数组数组排序开辟新链表返回int a[1000000]{0};int index0;ListNode* finalListnew ListNode(-1);ListNode* curfinalList;//存数据while (head) {a[index]head-val;headhead-next;}//排序sort(a, aindex);//排序后的数据存到新链表int indexB0;while (index--) {ListNode* tempnew ListNode(a[indexB]);cur-nexttemp;curcur-next;}return finalList-next;}
};解决方案二
2.1 思路阐述
第二种方式是在链表中使用归并排序。
其实看到题目的要求空间复杂度 O ( n ) O(n) O(n)时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)最方便当然是用辅助数组排序来做。但是如果空间复杂度改成O(1)那么开辟新数组的方式显然不合适。看到时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)我第一反应就是快排但是由于链表不支持下标操作那退而求其次就是归并排序了。 下面粘的是官方的一个解答。
知识点1分治
分治即“分而治之”“分”指的是将一个大而复杂的问题划分成多个性质相同但是规模更小的子问题子问题继续按照这样划分直到问题可以被轻易解决“治”指的是将子问题单独进行处理。经过分治后的子问题需要将解进行合并才能得到原问题的解因此整个分治过程经常用递归来实现。
知识点2双指针
双指针指的是在遍历对象的过程中不是普通的使用单个指针进行访问而是使用两个指针特殊情况甚至可以多个两个指针或是同方向访问两个链表、或是同方向访问一个链表快慢指针、或是相反方向扫描对撞指针从而达到我们需要的目的。
思路
前面我们做合并两个有序链表不是使用归并思想吗说明在链表中归并排序也不是不可能使用合并阶段可以参照前面这道题两个链表逐渐取最小的元素就可以了但是划分阶段呢
常规数组的归并排序是分治思想即将数组从中间个元素开始划分然后将划分后的子数组作为一个要排序的数组再将排好序的两个子数组合并成一个完整的有序数组因此采用的是递归。而链表中我们也可以用同样的方式只需要找到中间个元素的前一个节点将其断开就可以将链表分成两个子链表然后继续划分直到最小然后往上依次合并。
终止条件 当子链表划分到为空或者只剩一个节点时不再继续划分往上合并。
返回值 每次返回两个排好序且合并好的子链表。
本级任务 找到这个链表的中间节点从前面断开分为左右两个子链表进入子问题排序。怎么找中间元素呢我们也可以使用快慢双指针快指针每次两步慢指针每次一步那么快指针到达链表尾的时候慢指针正好走了快指针距离的一半为中间元素。
具体做法
step 1首先判断链表为空或者只有一个元素直接就是有序的。
step 2准备三个指针快指针right每次走两步慢指针mid每次走一步前序指针left每次跟在mid前一个位置。三个指针遍历链表
当快指针到达链表尾部的时候慢指针mid刚好走了链表的一半正好是中间位置。
step 3从left位置将链表断开刚好分成两个子问题开始递归。
step 4将子问题得到的链表合并参考合并两个有序链表。2.2 源码
class Solution {
public://合并两段有序链表ListNode* merge(ListNode* pHead1, ListNode* pHead2) { //一个已经为空了直接返回另一个if(pHead1 NULL) return pHead2;if(pHead2 NULL)return pHead1;//加一个表头ListNode* head new ListNode(0); ListNode* cur head;//两个链表都要不为空while(pHead1 pHead2){ //取较小值的节点if(pHead1-val pHead2-val){ cur-next pHead1;//只移动取值的指针pHead1 pHead1-next; }else{cur-next pHead2;//只移动取值的指针pHead2 pHead2-next; }//指针后移cur cur-next; }//哪个链表还有剩直接连在后面if(pHead1) cur-next pHead1;elsecur-next pHead2;//返回值去掉表头return head-next; }ListNode* sortInList(ListNode* head) {//链表为空或者只有一个元素直接就是有序的if(head NULL || head-next NULL) return head;ListNode* left head; ListNode* mid head-next;ListNode* right head-next-next;//右边的指针到达末尾时中间的指针指向该段链表的中间while(right ! NULL right-next ! NULL){ left left-next;mid mid-next;right right-next-next;}//左边指针指向左段的左右一个节点从这里断开left-next NULL; //分成两段排序合并排好序的两段return merge(sortInList(head), sortInList(mid)); }
};
总结
链表排序除了用辅助数组还可以用归并的思想。关于归并排序在链表中的运用还是有点陌生需要多实践。
