LeetCode 148. 排序链表(C++)（自底向上归并排序）
https://blog.****.net/weixin_44178736/article/details/111188252
class Solution {
public:
ListNode* sortList(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);
//c<<=2 就是 c=c<<2 把c左移2位得到的值给 c 即是subLength×2
for (int subLength = 1; subLength < length; subLength <<= 1) {
//前一个节点prev 当前节点curr
ListNode* prev = dummyHead, *curr = dummyHead->next;
while (curr != nullptr)
{
ListNode* head1 = curr;
//移到subLength-1个结点 找出一部分子链 长度为subLength结点的子链
for (int i = 1; i < subLength && curr->next != nullptr; i++)
{
curr = curr->next;
}
//尾结点后面一个点
ListNode* head2 = curr->next;
//切断子链
curr->next = nullptr;
curr = head2;
移到第二次的 subLength-1个结点 找出一部分子链 长度为subLength结点的子链
for (int i = 1; i < subLength && curr != nullptr && curr->next != nullptr; i++)
{
curr = curr->next;
}
ListNode* next = nullptr;
//切断第二个子链表
if (curr != nullptr)
{
next = curr->next;
curr->next = nullptr;
}
ListNode* merged = merge(head1, head2);
prev->next = merged;//取到合并后的子链
while (prev->next != nullptr)
{
//指针跳出此链表
prev = prev->next;
}
//当前指向刚才的curr->next
curr = next;//然后归并剩下的链表
}
}
return dummyHead->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;
}
};