单链表的排序，时间复杂度为O(nlogn)
作者：Lew's Personal Blog 发布于：2020-3-26 13:51 Thursday 分类：Leetcode
#include <iostream>
using namespace std;
struct ListNode
{
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL){}
};
ListNode* mergeTwoList(ListNode* l1, ListNode* l2)
{
if(l1 == nullptr)
return l2;
else if(l2 == nullptr)
return l1;
// else if(l1 == nullptr && l2 == nullptr)
// return nullptr;
ListNode *head = nullptr; //递归的思想
if(l1->val <= l2->val)
{
head = l1;
head->next = mergeTwoList(l1->next, l2);
}
else
{
head = l2;
head->next = mergeTwoList(l1, l2->next);
}
return head;
}
ListNode* mergeTwoList1(ListNode* l1, ListNode* l2)
{
if(!l1)
return l2;
else if(!l2)
return l1;
ListNode *head = new ListNode(-1);
ListNode *p = head;
while(l1 && l2)
{
if(l1->val <= l2->val)
{
p->next = l1;
l1 = l1->next;
}
else if(l1->val > l2->val)
{
p->next = l2;
l2 = l2->next;
}
p = p->next;
}
p->next = (l1 == nullptr)? l2 : l1;
return head->next;
}
ListNode* mergeTwoList2(ListNode* l1, ListNode* l2)
{
if(!l1)
return l2;
else if(!l2)
return l1;
if(l1->val <= l2->val)
{
l1->next = mergeTwoList2(l1->next, l2);
return l1;
}
else if(l1->val > l2->val)
{
l2->next = mergeTwoList2(l1, l2->next);
return l2;
}
}
ListNode* sortList(ListNode* head)
{
if(!head || !head->next)
return head;
ListNode *preSlow = nullptr;
ListNode *slow = head;
ListNode *fast = head;
while (fast && fast->next)
{
preSlow = slow;// 保存移动前的节点
slow = slow->next;
fast = fast->next->next;
}
//断开
preSlow->next = nullptr;
return mergeTwoList1(sortList(head), sortList(slow));
}
void printList(ListNode *head)
{
cout << "*******print-----list*******" << endl;
while(head)
{
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main(int argc, char **argv)
{
ListNode l1(4); ListNode a1(2);
ListNode l2(2); ListNode a2(9);
ListNode l3(1); ListNode a3(10);
ListNode l4(3); ListNode s1(1);
ListNode s2(2); ListNode s3(3);
l1.next = &l2;
l2.next = &l3;
l3.next = &l4;
l4.next = nullptr;
s1.next = &s2;
s2.next = &s3;
s3.next = nullptr;
a1.next = &a2;
a2.next = &a3;
a3.next = nullptr;
//printList(mergeTwoList1(&s1, &a1));
//printList(&l1);
printList(sortList(&l1));
getchar();
return 0;
}
标签： 单链表
« 上一篇 github 搜索命令总结 | unordered_map 下一篇»