题目描述
给你链表的头结点 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)$
Comments