Sort a linked list in O(n log n) time using constant space complexity.
链表排序可以用很多方法,插入,冒泡,选择都可以,也容易实现,但是复杂度不符合题意要求。
然后时间复杂度在O(nlogn)的排序算法中,堆排序,快速排序,归并排序。
- 堆排序,主要是基于数组的,这里是链表,实现起来比较麻烦。
- 快速排序,快速排序最坏情况的时间复杂度是O(n2)
- 归并排序,在对数组的归并排序中,是有O(n)的空间复杂度的,但是链表可以不需要,我们可以用构造虚拟节点法
就地合并两个有序链表。
因此,我们就选择用归并排序来解决这道题,合并两个有序链表将作为链表常见算法题之一,在算法总结那篇文章中会出现。
归并的核心思想就是divide-merge。如何divide,又涉及到链表常见算法——找到中间节点。找到中间节点后,即可把链表
划分成两个链表,然后再合并。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* sortList(ListNode* head) {
if(head==NULL||head->next==NULL)
return head;
return MergeSort(head); }
/* ListNode* Merge(ListNode* r,ListNode* l){
if(r==NULL||l==NULL)
return r?r:l;
ListNode*p,*q;
if(r->val<l->val)
{p=r;
q=l;}
else{
p=l;
q=r;
}
ListNode head=p;
ListNode* tmp=r;
ListNode* bf=p;
while(p&&q){
if(p->val<q->val){
bf=p;
p=p->next;
}
else{
tmp=q;
q=q->next;
bf->next=tmp;
}
}
if(!q){
bf->next=q;
}
return head;
}*/
ListNode * Merge(ListNode *lh, ListNode *rh){
ListNode *temp=new ListNode();
ListNode *p=temp;
while(lh&&rh){
if(lh->val<=rh->val){
p->next=lh;
lh=lh->next;
}
else{
p->next=rh;
rh=rh->next;
}
p=p->next;
}
if(!lh)
p->next=rh;
else
p->next=lh;
p=temp->next;
temp->next=NULL;
delete temp;
return p;
}
ListNode* MergeSort(ListNode* head){
if(head==NULL||head->next==NULL)
return head;
ListNode* p=head;
ListNode* middle=head,*pre=NULL;;
while(p&&p->next!=NULL){
p=p->next->next;
pre=middle;
middle=middle->next;
}
pre->next=NULL;
head=MergeSort(head);
middle=MergeSort(middle); return Merge(head,middle);
}
};