1、非递归
// 递归的归并排序
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);
for (int subLength = 1; subLength < length; subLength *= 2) {
ListNode *prev = dummyHead, *curr = dummyHead->next;
while (curr != nullptr) {
ListNode* head1 = curr;
// 取子长度的链表
for (int i = 1; i < subLength && curr->next != nullptr; ++i)
curr = curr->next;
ListNode* head2 = curr->next;
curr->next = nullptr;
curr = head2;
if (curr == nullptr) {
ListNode* merged = merge(head1, head2);
prev->next = merged;
break;
}
// 不只是取第一个和第二个链表的头节点,需要记录第二个链表的末尾,不然后面很难遍历
for (int i = 1; i < subLength && curr->next != nullptr; ++i) {
curr = curr->next;
}
// 下一次遍历从下一个结尾
ListNode* next = nullptr;
if (curr->next != nullptr) {
next = curr->next;
curr->next = nullptr;
}
ListNode* merged = merge(head1, head2);
prev->next = merged;
while (prev->next != nullptr) {
prev = prev->next;
}
curr = next;
}
}
return dummyHead->next;
}
// 两两合并
ListNode* merge(ListNode* head1, ListNode* head2) {
ListNode* dummmy = new ListNode();
ListNode* p = dummmy;
while (head1 && head2) {
if (head1->val < head2->val) {
p->next = head1;
head1 = head1->next;
} else {
p->next = head2;
head2 = head2->next;
}
p = p->next;
}
if (head1) {
p->next = head1;
} else {
p->next = head2;
}
p = dummmy->next;
delete dummmy;
return p;
}
};
2、递归
//递归的归并排序
class Solution {
public:
ListNode* sortList(ListNode* head) {
return sortList(head, nullptr);
}
ListNode* sortList(ListNode* head1, ListNode* head2)
{
//从节点head1到节点head2进行排序
if (head1 == nullptr)
return head1;
if (head1->next == head2)
{
head1->next = nullptr; //因为从begin,mid) [mid,last]
return head1;
}
//取终点再次进行折半
ListNode* fast = head1, * slow = head1;
while (fast != head2)
{
fast = fast->next;
slow = slow->next;
if (fast != head2)
fast = fast->next;
}
ListNode* l1 = sortList(head1, slow);
ListNode* l2 = sortList(slow, head2);
return merge(l1, l2);
}
//两两合并
ListNode* merge(ListNode* head1, ListNode* head2)
{
ListNode* dummmy = new ListNode();
ListNode* p = dummmy;
while (head1 && head2)
{
if (head1->val < head2->val)
{
p->next = head1;
head1 = head1->next;
}
else
{
p->next = head2;
head2 = head2->next;
}
p = p->next;
}
if (head1)
p->next = head1;
else
p->next = head2;
p = dummmy->next;
delete dummmy;
return p;
}
};
标签:ListNode,head2,head1,nullptr,next,链表,curr,排序 From: https://www.cnblogs.com/Kellen-Gram/p/18108777