思路:
基础题目,设置3个指针,2个分别指向2个有序链表,第3个用来拼接最后的合并链表(保存好要返回的头结点)。没什么好说的。
应用:
链表排序。对链表进行归并排序的时候,本题的算法相当于是归并排序中的merge操作。
拓展:链表排序
难点:
- 找链表中点
- merge操作的实现
逐个攻破:
- 先来说merge操作的实现
有2种方式,1种是递归,1一种是循环。其中递归方便理解,但空间复杂度为O(n)(系统栈的调用)
递归实现:
TreeNode* merge(TreeNode *a,TreeNode *b){
//定义终止条件
if(a==nullptr)
return b;
if(b==nullptr)
return a;
//开始递归过程
if(a->val<=b->val){
a->next=merge(a->next,b);
reutrn a;
}
else{
b->next=merge(a,b->next);
return b;
}
}
循环实现merge
TreeNode *merge(TreeNode *a,TreeNode *b){
//judge illegal
if(a==nullptr)
return b;
if(b==nullptr)
return a;
TreeNode *c,*head;
if(a->val<=b->val){
c=a;
a=a->next;
}
else{
c=b;
b=b->next;
}
head=c;
while(a&&b){
if(a->val<=b->val){
c->next=a;
a=a->next;
}
else{
c->next=b;
b=b->next;
}
c=c->next;
}
c->next=nullptr;
if(a!=nullptr)
c->next=a;
if(b!=nullptr)
c->next=b;
return head;
}
可见循环的代码比递归的代码要冗余许多,但是执行效率会更高,两种实现方式都不是很难,其实就是简单的逻辑判断,判断一下是a链表的值还是b链表的值大,分别处理即可
- 找到链表中点
采用快慢指针的方法,快指针走2步,慢指针走一步,因为要切分链表一定要明确切分的范围,否则容易犯迷糊,比如把链表切分成[head,slow],[slow->next,null]两部分或者[head,slow->prior],[slow,null]两部分,定义好切分的范围后,写代码会思路更加清晰,不容易出错。
另外值得注意的是链表不具备随机访问的能力,因此我们需要额外设置一个指针split来标记我们的链表切分点(可以标记slow节点的前一个或者后一个节点)
逻辑代码(不推荐封装成函数,因为我们需要split和slow两个节点,封装成函数如果用cpp的话还是挺麻烦的)
find the middle point in a linkedList
vector<TreeNode *>findMP(TreeNode *head){
//judge illeagal
if(head==nullptr)
return nullptr;
TreeNode *slow=head,*fast=head,*split=head;
while(fast&&fast->next){
fast=fast->next->next;
split=slow;//mark the slow->prior
slow=slow->next;
}
return {split,slow} //[head,split],[slow,nullptr]
}
整体实现:
目前我们已经实现了找到链表中点和merge操作,那么我们就可以用归并排序进行链表排序了。
```cpp
TreeNode *sortList(TreeNode *head){
//judge illeagal
if(head==nullptr||head->next==nullptr)
return head;
//find the middle point
vector<TreeNode> split=findMP(head);
split[0]->next=nullptr;
head=sortList(head);
split[1]=sortList(split[1]);
merge(split[1]);
}
循环实现:(待补充)
网友评论