链接:https://leetcode-cn.com/problems/sort-list/
题目
给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。
进阶:
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?
示例
示例 1:
输入:head = [4,2,1,3]
输出:[1,2,3,4]
示例 2:
输入:head = [-1,5,3,4,0]
输出:[-1,0,3,4,5]
示例 3:
输入:head = []
输出:[]
提示:
链表中节点的数目在范围 [0, 5 * 104] 内
-105 <= Node.val <= 105
思路
方法1
递归 实现归并排序
使用快慢指针分割链表
由于使用递归O(logn)栈内存空间
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(!head||head->next==nullptr)
return head;
ListNode *front=head->next,*back=head;
int index=0;
while(front->next)
{
front=front->next;
index++;
if(index%2==0)
{
back=back->next;
index=0;
}
}
front=back->next;
back->next=nullptr;
return sort(sortList(head),sortList(front));
}
ListNode*sort(ListNode*a,ListNode*b)
{
ListNode*ha=a,*hb=b;
ListNode*ptr=nullptr;
if(ha->val<=hb->val)
{
ptr=ha;
ha=ha->next;
}else
{
ptr=hb;
hb=hb->next;
}
ListNode *head=ptr;
while(ha!=nullptr&&hb!=nullptr)
{
if(ha->val<=hb->val)
{
ptr->next=ha;
ha=ha->next;
}else{
ptr->next=hb;
hb=hb->next;
}
ptr=ptr->next;
}
if(ha!=nullptr)
{
ptr->next=ha;
}
if(hb!=nullptr)
{
ptr->next=hb;
}
return head;
}
};
方法2
由于进阶要求常数级空间复杂度 所以不能用递归
可以手动分割等长链表 迭代
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(!head||head->next==nullptr)
return head;
int num=0;
ListNode*ptr=head;
while(ptr)
{
num++;
ptr=ptr->next;
}
ListNode *dhead=new ListNode(0,head);//定义头节点
for(int lenth=1;lenth<num;lenth<<=1)
{
ListNode *pre=dhead,*cur=dhead->next;//定义分支的头节点和 流动的节点
while(cur!=nullptr)//当前节点不为空
{
ListNode *head1=cur;
for(int i=1;i<lenth&&cur->next!=nullptr;++i)
{
cur=cur->next;
}
ListNode *head2=cur->next;
cur->next=nullptr;
cur=head2;
for(int i=1;i<lenth&&cur!=nullptr&&cur->next!=nullptr;++i)
{
cur=cur->next;
}
ListNode *n =nullptr;
if(cur!=nullptr)
{
n=cur->next;
cur->next=nullptr;
}
pre->next=merge(head1,head2);
while(pre->next!=nullptr){
pre=pre->next;
}
cur=n;
}
}
return dhead->next;
}
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummyHead = new ListNode(0);
ListNode* temp = dummyHead, *temp1 = head1, *temp2 = head2;
while (temp1 != nullptr && temp2 != nullptr) {
if (temp1->val <= temp2->val) {
temp->next = temp1;
temp1 = temp1->next;
} else {
temp->next = temp2;
temp2 = temp2->next;
}
temp = temp->next;
}
if (temp1 != nullptr) {
temp->next = temp1;
} else if (temp2 != nullptr) {
temp->next = temp2;
}
return dummyHead->next;
}
};
注意
链表问题可以定义额外头节点来 规范循环条件ListNode *dhead=new ListNode(0,head);