这里链表与数组不同的是链表无法随机访问,在数组中我们都能精准的找到中间位置,这里我们采用快慢指针来确定中间节点,然后通过递归到单个元素然后分割链表,再链接链表(下面将一一讲解)
快慢指针确定中间节点
/*head为已知条件*/
Listnode* tail=nullptr;
Listnode* slow=head;
Listnode* fast=head;
while(fast!=tail) //快指针多移动一次到尾时,慢指针则为中间节点
{
slow=slow->next;
fast=fast->next;
if(fast!=tail)
{
fast=fast->next;
}
Listnode* mid=slow; //中间节点
}
分割链表
ListNode* apart_list(ListNode* head,ListNode* tail)
{
if(head==nullptr) return nullptr;
if(head->next==tail) return head;
Listnode* slow=head;
Listnode* fast=head;
while(fast!=tail) //快指针多移动一次到尾时,慢指针则为中间节点
{
slow=slow->next;
fast=fast->next;
if(fast!=tail) //头闭尾开只有一个元素head 无法继续分割返回head节点
{
fast=fast->next;
}
Listnode* mid=slow; //中间节点
}
/*这里的merge为合并函数*/
/*我们这里递归分割左右链表,递归到只有一个元素无法分割后链接两边节点*/
return merge(apart_list(head,mid),apart_list(mid,tail));
}
/*
假如链表如下:
1 4 3 5 2
第一次分割1,nullptr中间节点为3 也就是 return merge(apart_list(1,3),apart_list(3,nullptr))
第二次分割1,3中间节点为2 然后 return merge(apart_list(1,2),apart_list(2,3))
第三次分割1,2无法进行分割 此时满足head->next=tail 1节点下一节点置空 返回1节点
第四次分割2,3同理 置空2节点的下一节点后返回2节点
然后通过执行merge(2,3)将分割的单个节点2和3有序链接 返回给上一级递归
同理3,nullptr也是如此
*/
链接链表
这个就简单了就是合并两个有序链表
ListNode* merge(ListNode* l,ListNode* r)
{
ListNode* temp=new ListNode(0);
ListNode* l_now=l;
ListNode* r_now=r;
ListNode* now=temp;
/*都有元素则比较大小*/
while(l_now!=nullptr&&r_now!=nullptr)
{
if(l_now->val<=r_now->val)
{
now->next=l_now;
l_now=l_now->next;
}
else
{
now->next=r_now;
r_now=r_now->next;
}
now=now->next;
}
/*链接剩下的元素*/
if(l_now!=nullptr)
{
now->next=l_now;
}
else now->next=r_now;
return temp->next;
}
完整代码
/**
* 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* apart_list(ListNode* head,ListNode* tail)
{
if(head==nullptr) return nullptr;
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(apart_list(head,mid),apart_list(mid,tail));
}
ListNode* merge(ListNode* l,ListNode* r)
{
ListNode* temp=new ListNode(0);
ListNode* l_now=l;
ListNode* r_now=r;
ListNode* now=temp;
while(l_now!=nullptr&&r_now!=nullptr)
{
if(l_now->val<=r_now->val)
{
now->next=l_now;
l_now=l_now->next;
}
else
{
now->next=r_now;
r_now=r_now->next;
}
now=now->next;
}
if(l_now!=nullptr)
{
now->next=l_now;
}
else if(r_now!=nullptr)
{
now->next=r_now;
}
return temp->next;
}
ListNode* sortList(ListNode* head) {
return apart_list(head,nullptr);
}
};
时间复杂度为O(nlogn)空间复杂度为O(logn)