题目
字节面试题
复杂度分析
时间复杂度O(nlogn)
空间复杂度为O(1)
解题思路参照官方做法2：自底向上归并排序
这里给出注释版，便于本次和以后做这题的理解
cpp代码
/**
* 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:
//官方做法2：自底向上归并排序
ListNode* sortList(ListNode* head) {
if(head==nullptr) return head;
// 1. 首先从头向后遍历,统计链表长度
int length = 0; // 用于统计链表长度
ListNode* node = head;
while(node!=nullptr){
length++;
node = node->next;
}
// 2. 初始化 引入dummynode
ListNode * dummyHead = new ListNode(0);
dummyHead->next = head;
// 3. 每次将链表拆分成若干个长度为subLen的子链表 , 并按照每两个子链表一组进行合并
for(int subLen=1;subLen<length;subLen=subLen*2){
ListNode* prev = dummyHead;
ListNode* curr = dummyHead->next;// curr用于记录拆分链表的位置
while(curr!=nullptr){ // 如果链表没有被拆完
// 3.1 拆分subLen长度的链表1
ListNode* head1 = curr; // 第一个链表的头 即 curr初始的位置
for(int i=1;i<subLen&&curr!=nullptr&&curr->next!=nullptr;i++){// 拆分出长度为subLen的链表1
curr = curr->next;
}
// 3.2 拆分subLen长度的链表2
ListNode* head2 = curr->next; // 第二个链表的头 即 链表1尾部的下一个位置
curr->next = nullptr; // 断开第一个链表和第二个链表的链接
curr = head2; // 第二个链表头 重新赋值给curr
for(int i=1;i<subLen&&curr!=nullptr&&curr->next!=nullptr;++i){// 再拆分出长度为subLen的链表2
curr = curr->next;
}
// 3.3 再次断开 第二个链表最后的next的链接
ListNode* next = nullptr;
if(curr!=nullptr){
next = curr->next; // next用于记录 拆分完两个链表的结束位置
curr->next = nullptr; // 断开连接
}
// 3.4 合并两个subLen长度的有序链表
ListNode* merged = mergeTwoLists(head1,head2);
prev->next = merged; // prev->next 指向排好序链表的头
while(prev->next!=nullptr){ // while循环 将prev移动到 subLen*2 的位置后去
prev = prev->next;
}
curr = next; // next用于记录 拆分完两个链表的结束位置
}
}
// 返回新排好序的链表
return dummyHead->next;
}
//合并两个链表
ListNode* mergeTwoLists(ListNode* l1,ListNode* l2){
ListNode* dummy = new ListNode(0);
ListNode* curr = dummy;
while(l1!=nullptr && l2!=nullptr){ // 退出循环的条件是走完了其中一个链表
// 判断l1 和 l2大小
if(l1->val < l2->val){
// l1 小 ， curr指向l1
curr->next = l1;
l1 = l1->next; // l1 向后走一位
}else{
// l2 小 ， curr指向l2
curr->next = l2;
l2 = l2->next; // l2向后走一位
}
curr = curr->next; // curr后移一位
}
// 退出while循环之后,比较哪个链表剩下长度更长,直接拼接在排序链表末尾
if(l1==nullptr) curr->next = l2;
if(l2==nullptr) curr->next = l1;
// 最后返回合并后有序的链表
return dummy->next;
}
};
