两种方法
递归法(自顶向下法)
迭代法(自底向上法)
递归法（自顶向下法）
这里链表与数组不同的是链表无法随机访问，在数组中我们都能精准的找到中间位置，这里我们采用快慢指针来确定中间节点，然后通过递归到单个元素然后分割链表，再链接链表（下面将一一讲解）
快慢指针确定中间节点
/*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)
自底向上法
和数组一样我们需要不断的增加分区间的距离
/**
* 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)
{
return head;
}
int length=0;
ListNode* node=head;
while(node!=nullptr)
{
length++;
node=node->next;
}
ListNode* temp=new ListNode(0,head);
for(int len=1;len<length;len*=2) //增加半区间
{
ListNode* pre=temp,*now=temp->next;
while(now!=nullptr)
{
ListNode* head1=now;
for(int i=1;i<len&&now->next!=nullptr;i++)
{
now=now->next;
}
ListNode*head2=now->next;
now->next=nullptr; //分割
now=head2;
for(int i=1;i<len&&now!=nullptr&&now->next!=nullptr;i++)
{
now=now->next;
}
ListNode* next=nullptr;
if(now!=nullptr)
{
next=now->next;
now->next=nullptr;
}
ListNode* marged=merge(head1,head2);
pre->next=marged;
while(pre->next!=nullptr)
{
pre=pre->next;
}
now=next;
}
}
return temp->next;
}
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;
}
};时间复杂度为O(logn)空间复杂度为O(n)
