题目描述
给你链表的头结点 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 \times 10^4] $内
- $-10^5 \leq Node.val \leq 10^5$
解题思路
链表的排序是一道很经典的题目,可以实现的排序算法有很多种。本道题主要实现了链表的归并排序。
链表的归并排序的思想与数组的归并排序并无二致,也可以分为递归和迭代两种方式来实现。
在具体的实现过程中主要有以下几点差别:
-
在数组中需要合并两个有序数组,那么在链表中就需要合并两个有序链表。具体实现方法可以参见Leetcode21.合并两个有序链表;
-
在链表的归并排序中,需要有断链的操作,否则会出现错误。
代码如下所示:
示例代码
迭代版:
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) {}
};
ListNode* mergerTwoList(ListNode* firstHead,ListNode* secondHead)
{
//合并两个有序链表
if(!firstHead) return secondHead;
if(!secondHead) return firstHead;
ListNode* virtualHead=new ListNode(0);
ListNode* firstPtr=firstHead;
ListNode* secondPtr=secondHead;
ListNode* curPtr=virtualHead;
while(firstPtr&&secondPtr)
{
if(firstPtr->val<secondPtr->val)
{
curPtr->next=firstPtr;
firstPtr=firstPtr->next;
curPtr=curPtr->next;
curPtr->next=nullptr;
}
else{
curPtr->next=secondPtr;
secondPtr=secondPtr->next;
curPtr=curPtr->next;
curPtr->next=nullptr;
}
}
if(firstPtr) curPtr->next=firstPtr;
if(secondPtr) curPtr->next=secondPtr;
return virtualHead->next;
}
ListNode* findMidPtr(ListNode* head)
{
//获取中间结点
if(head==nullptr||head->next==nullptr) return head;
ListNode* fastPtr=head->next->next;
ListNode* slowPtr=head;
if(fastPtr&&fastPtr->next)
{
fastPtr=fastPtr->next->next;
slowPtr=slowPtr->next;
}
return slowPtr;
}
ListNode* sortList(ListNode* head)
{
if(head==nullptr||head->next==nullptr) return head;
ListNode* midPtr=findMidPtr(head);
ListNode* rightHead=midPtr->next;
midPtr->next=nullptr;
ListNode* leftPtr=sortList(head);
ListNode* rightPtr=sortList(rightHead);
return mergerTwoList(leftPtr,rightPtr);
}
时间复杂度:$O(nlogn)$
空间复杂度:$O(logn)$
迭代版:
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) {}
};
ListNode* mergerTwoList(ListNode* firstHead,ListNode* secondHead)
{
//合并两个有序链表
if(!firstHead) return secondHead;
if(!secondHead) return firstHead;
ListNode* virtualHead=new ListNode(0);
ListNode* firstPtr=firstHead;
ListNode* secondPtr=secondHead;
ListNode* curPtr=virtualHead;
while(firstPtr&&secondPtr)
{
if(firstPtr->val<secondPtr->val)
{
curPtr->next=firstPtr;
firstPtr=firstPtr->next;
curPtr=curPtr->next;
curPtr->next=nullptr;
}
else{
curPtr->next=secondPtr;
secondPtr=secondPtr->next;
curPtr=curPtr->next;
curPtr->next=nullptr;
}
}
if(firstPtr) curPtr->next=firstPtr;
if(secondPtr) curPtr->next=secondPtr;
return virtualHead->next;
}
int getLength(ListNode* head)
{
//获得链表长度
int length=0;
while(head!=nullptr)
{
length++;
head=head->next;
}
return length;
}
ListNode* split(ListNode* head,int step)
{
//断链,返回第二部分链表的头结点
if(head==nullptr) return head;
ListNode* cur=head;
for(int i=1;i<step&&cur->next!=nullptr;++i)
{
cur=cur->next;
}
ListNode* right=cur->next;
cur->next=nullptr;
return right;
}
ListNode* sortList(ListNode* head)
{
if(head==nullptr||head->next==nullptr) return head;
int length=getLength(head);
ListNode* virtualHead=new ListNode(-1,head);
//步长从1,2,4,...,一直到length
for(int subLength=1;subLength<length;subLength*=2)
{
//pre指针指向已经排好序的链表末尾,cur指针指向将要进行处理的链表的头结点
ListNode* pre=virtualHead;
ListNode* cur=virtualHead->next;
//while循环处理一次步长的所有合并操作
while(cur!=nullptr)
{
//head1为第一部分头
ListNode* head1=cur;
//head2为第二部分头
ListNode* head2=split(head1,subLength);
//cur为剩余需要处理的链表的头
cur=split(head2,subLength);
//合并一二部分
ListNode* merged=mergerTwoList(head1,head2);
//更新其他指针的状态
pre->next=merged;
while(pre->next!=nullptr)
{
pre=pre->next;
}
}
}
return virtualHead->next;
}
时间复杂度:$O(nlogn)$
空间复杂度:$O(1)$
文章评论