LeetCode 148. 排序链表
2020-12-13 06:02
标签：list 复杂度 nod 空间 要求 node ext 输入 ret 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 LeetCode 148. 排序链表 标签：list 复杂度 nod 空间 要求 node ext 输入 ret 原文地址：https://www.cnblogs.com/programyang/p/11162130.html
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
算法：归并排序(且只能归并排序，因为题目做了要求)。我们依据归并排序的思想。将原链表分为两部分进行递归排序即可。/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* merge(ListNode* l1,ListNode* l2){
auto l=new ListNode(-1);
auto cur=l;
while(l1&&l2){
if(l1->val>l2->val){
cur->next=l2;
l2=l2->next;
}
else
{
cur->next=l1;
l1=l1->next;
}
cur=cur->next;
}
cur->next=l1?l1:l2;
return l->next;
}
ListNode* sortList(ListNode* head) {
if(!head||!head->next)return head;
auto f=head,s=head;
while(f->next&&f->next->next){
f=f->next->next;
s=s->next;
}
f=s;
s=s->next;
f->next=NULL;
auto le=sortList(head);
auto ri=sortList(s);
return merge(le,ri);
}
};