问题表述
问题分析
题目本身比较好理解,这里给出两种解法。链表得题目关键是要注意节点之间得指向,另外注意各个节点,例如虚拟头节点,当前节点,上一个节点,下一个节点等等,链表在内存分布是散开的,由指针联系着节点。
- 忽略所有的指针,存储所有的节点,然后对所有的节点按照节点值排序,这里就需要自己去定义节点排序的函数了,然后重新连接已经排序的节点就好了,这种方式感觉比较简单。这里其实我有一个疑问,如果用这种方法,那原本连接节点的指针会自动释放占用的内存资源吗?
- 归并排序的思路:先找到链表的中间节点,这里找中间节点要考虑奇偶,有两种方式;然后根据中间节点开始分链表,直到分到只有一个元素为止,这一个就是已经排好序的了;然后开始合并。递归进行分治的时候注意终止条件,另外,合并的时候链表最后是只要有任何一个节点还剩余,直接连接剩余的头节点就行了,而数组是需要while循环一个个将元素放入辅助数组。
先说下自定义排序问题
sort函数
#include<algorithm>
sort(fisrt,last,cmp)//fisrt,last都是下标
注意compare函数写在类外或者定义为静态函数
std::sort要求函数对象,或是静态/全局函数指针,非静态成员函数指针不能直接传递给std::sort。
static bool cmp(const T&a,const T&b){//T是模板
return a<b
}
如果是想升序,那么就定义当a<b的时候返回true;
如果是想降序,那么就定义当a>b的时候返回true;
找链表中间节点的问题
如果链表是奇数没啥问题,肯定中间节点就一个,如果链表节点是偶数个,那是去中间的第一个还是第二个节点,有两种写法。
如果取得是中间的第一个节点:
建议做题的时候先打草稿,理清楚思路,然后开始做题。
ListNode*mid(ListNode*node){
ListNode*fast=node->next;//这里node不能为空
ListNode*slow=node;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
如果获取得是第二个中间节点
ListNode*mid(ListNode*node){
ListNode*fast=node;
ListNode*slow=node;
while(fast&&fast->next){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
代码表述
/**
* 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:
static bool cmp(ListNode*x,ListNode*y){
return x->val<y->val;//自定义排序方法
}
ListNode* sortList(ListNode* head) {
if(head==nullptr)return head;
ListNode*dummy=new ListNode(-1);
dummy->next=head;
//将链表放在数组中,一个位置就是一个集合,装下对应类型的数据
//排序数组思路比较简单
vector<ListNode*>ans;
while(dummy->next){
ans.push_back(dummy->next);
dummy=dummy->next;
}
sort(ans.begin(),ans.end(),cmp);//
int n=ans.size();
ListNode*node=new ListNode(0);
node->next=ans[0];
ListNode*root=node;
for(int i=0;i<n;i++){
node->next=ans[i];
node=node->next;
}
node->next=nullptr;
return root->next;
}
};
复杂度
时间复杂度:O(nlogn)其中 n 是链表的长度。
空间复杂度:O(n),链表节点个数。
/**
* 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) {
if(head==nullptr||head->next==nullptr)return head;
//找中点
ListNode*m=mid(head);
ListNode*l=sortList(head);
ListNode*r=sortList(m);
return mergeTwoLists(l,r);
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
//虚拟头节点
ListNode*node=new ListNode(-1);//建立虚拟头节点
auto res=node;//要返回的节点
//归并排序的思想了
while(l1&&l2){
if(l1->val<=l2->val){
node->next=l1;
l1=l1->next;//不要忘记了更新链表节点
}
else{
node->next=l2;
l2=l2->next;
}
node=node->next;
}
if(l1)node->next=l1;
else if(l2)node->next=l2;
return res->next;
}
ListNode*mid(ListNode*head){
ListNode*fast=head->next;
ListNode*slow=head;
//auto pre=slow;
while(fast&&fast->next){
//pre=slow;
fast=fast->next->next;
slow=slow->next;
}
//pre->next=nullptr;
ListNode*head1=slow->next;
slow->next=nullptr;
// return slow;
return head1;
}
};
复杂度
时间复杂度:O(nlogn)其中 n 是链表的长度。
空间复杂度:O(logn)空间复杂度主要是递归树占用得栈空间。