LeetCode 热题 100_排序链表（33_148）
题目描述：
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
输入输出样例：
示例 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、每次取未排序单链表中一个结点，与排序好的链表中的结点从头开始挨个比对，查找对应插入位置再插入。
2、具体思路如下：
① 如果为空或只有一个元素返回单链表。
② 创建一个新的头节点用于统一排序元素的插入。
③ 先将第一个元素插入排序链表。
④ 其余元素在插入时，从排序链表头部开始查找插入位置，若遍历到排序链表的末尾，则在末尾插入。
3、复杂度分析：
① 时间复杂度：O(n)，其中 n 是链表的长度，最坏的情况是原列表有序，在每次插入都需与每个排序好的元素进行比较。
② 空间复杂度：O(1)。
思路二（归并排序(非递归)）：
1、我们必须将链表划分为1大小的分块开始进行两两归并排序。下一次划分为2大小的分块进行两两归并，再依次从4，8，16~length，最终合并成一个单链。
2、具体思路如下：
subLength=[1,2,4,8,16~length]
① 1、链表从前往后先拆下来subLength（分块）大小的链表head1，再拆下head1后subLength大小的的链表head2。
② 将head1和head2进行归并排序形成merged链表。
③ 将 merged链接到之前归并完成的尾结点（一开始是dummyHead）。
④ 再从head2后拆下来subLength（分块）大小的链表head3，再拆下head3后subLength大小的的链表head4。
⑤ 将head3和head4进行归并排序形成merged链表。
⑥ 将 merged链接到之前归并完成的尾结点。
…
…
…
⑦ 完成subLength大小的归并排序后，再进行subLength*2小的归并排序，直到分块大小>=length。
例：head = [4,2,1,3]
subLength=1， [4,2,1,3] => [[2,4],[1,3]]
subLength=2, [[2,4],[1,3]]=>[1,2,3,4]
3、复杂度分析
① 时间复杂度：O(nlogn)，其中 n 是链表的长度。
② 空间复杂度：O(1)。
代码实现
代码实现（思路一（挨个匹配插入））：
ListNode* sortList1(ListNode* head) {
if(head==nullptr||head->next==nullptr){
return head;
}
//创建一个新的头节点（统一操作）
ListNode *dummyHead=new ListNode(-1,head);
//r用于保存还未排序链表的首节点
ListNode *r=head->next;
//将dummyHead和第一个结点与后续链表断开
head->next=nullptr;
//tmp代表将要移动的结点
ListNode *tmp=r;
//pre代表插入节点在排序链表中的前驱结点
ListNode *pre=dummyHead;
//当未排序链表存在结点时，挨个插入排序链表
while(r!=nullptr){
tmp=r;
r=r->next;
//查找插入位置
while(pre->next!=nullptr&&tmp->val > pre->next->val){
pre=pre->next;
}
//插入
tmp->next=pre->next;
pre->next=tmp;
//下一个插入的元素比当前插入的元素大，则从当前元素位置开始查找插入位置
//否则从头开始查找
if(r!=nullptr&&r->val>tmp->val){
pre=tmp;
}else{
pre=dummyHead;
}
}
head=dummyHead->next;
//注意结点的释放
delete dummyHead;
return head;
}
代码实现（思路二（归并排序(非递归)））：
//两个单链表的合并排序（归并排序中两个块之间的合并）
ListNode* merge(ListNode* head1, ListNode* head2) {
//创建一个新的头节点（统一操作）
ListNode* dummyHead = new ListNode(0);
//代表合并过程中合并链表的尾结点
ListNode* tail = dummyHead;
//合并到其中一个链表为空
while (head1 != nullptr && head2 != nullptr) {
if (head1->val <= head2->val) {
tail->next = head1;
head1 = head1->next;
} else {
tail->next = head2;
head2 = head2->next;
}
tail = tail->next;
}
//链接剩余链表
tail->next=head1?head1:head2;
//head1存储合并好的首结点
head1=dummyHead->next;
delete dummyHead;
return head1;
}
ListNode* sortList2(ListNode* head) {
if (head == nullptr) {
return head;
}
//计算链表的长度
int length = 0;
ListNode* node = head;
while (node != nullptr) {
length++;
node = node->next;
}
//创建一个新的头节点（统一操作）
ListNode* dummyHead = new ListNode(0, head);
//以 subLength划分的单链表进行归并排序，subLength=[1,2,4,8~length]
for (int subLength = 1; subLength < length; subLength <<= 1) {
//每一趟将prev和curr重置从头开始,prev代表两个块合并完的尾结点用于连接
//curr 的作用是记录块的头，查找块的尾部，并断开块用于合并
ListNode* prev = dummyHead, *curr = dummyHead->next;
//遍历一次链表，处理subLength长度划分的各个单链表
//每次从前往后进行两块之间的归并排序,一直到整个链表
while (curr != nullptr) {
//head1 和 head2 来表示要合并的两个子链表
ListNode* head1 = curr;
//通过一个 for 循环来找到第一个子链表的尾部 curr
for (int i = 1; i < subLength && curr->next != nullptr; i++) {
curr = curr->next;
}
//head1 和 head2 来表示要合并的两个子链表
ListNode* head2 = curr->next;
//将head1和head2断开
curr->next = nullptr;
//我们更新 curr，让它指向第二个子链表的头
curr = head2;
//当结点足够时，找到了第二个子链表的尾部，并截断链表，此时curr代表head2的尾部
for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++) {
curr = curr->next;
}
//如果第二个子链表后有剩余节点，next代表其后的第一个节点，将head2断开
ListNode* next = nullptr;
if (curr != nullptr) {
next = curr->next;
curr->next = nullptr;
}
//合并 head1 和 head2。合并后的结果会接到 prev->next 上
ListNode* merged = merge(head1, head2);
prev->next = merged;
//使prev指向新合并的链表的最后一个节点
while (prev->next != nullptr) {
prev = prev->next;
}
curr = next;
}
}
head= dummyHead->next;
delete dummyHead;
return head;
}
以思路一为例进行调试
#include<iostream>
#include<vector>
using namespace std;
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 *createList(vector<int> arr){
ListNode *head=nullptr,*tail=nullptr;
for(const auto &val:arr){
if(head==nullptr){
head=tail=new ListNode(val);
}else{
tail->next=new ListNode(val);
tail=tail->next;
}
}
return head;
}
//方法一挨个插入
ListNode* sortList1(ListNode* head) {
if(head==nullptr||head->next==nullptr){
return head;
}
ListNode *dummyHead=new ListNode(-1,head);
ListNode *r=head->next;
head->next=nullptr;
ListNode *tmp=r;
ListNode *pre=dummyHead;
while(r!=nullptr){
tmp=r;
r=r->next;
//查找插入位置
while(pre->next!=nullptr&&tmp->val>pre->next->val){
pre=pre->next;
}
//插入
tmp->next=pre->next;
pre->next=tmp;
//在下一个插入的元素比当前的元素大，则从当前元素位置开始查找插入位置
if(r!=nullptr&&r->val>tmp->val){
pre=tmp;
}else{
pre=dummyHead;
}
}
head=dummyHead->next;
delete dummyHead;
return head;
}
int main(){
vector <int> a={4,2,1,3};
//创建单链表
ListNode *head=createList(a);
//对链表进行排序（方法一）
ListNode *ans=sortList1(head);
//输出排序后的结果
while(ans!=nullptr){
cout<<ans->val<<"->";
ans=ans->next;
}
cout<<"null";
return 0;
}
更改链接
LeetCode 热题 100_合并两个有序链表（27_21_简单_C++）请点击此链接
LeetCode 热题 100_排序链表（33_148)原题链接
欢迎大家和我沟通交流(✿◠‿◠)