Sort a linked list in O(n log n) time using constant space complexity.
由于链表的特性,不能快速查找,但是可以快速移动元素,通过归并排序可以实现O(nlogn)复杂度内的排序
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* Merge(ListNode* s,ListNode* a,ListNode* b,int step){ // s->a------a.tail>b--------b.tail->t //if length of b smaller than step b is the tail of the list ListNode* ptr=b; ListNode* tail; int lenb=0,lena=step; while(ptr!=NULL){ lenb++; if(lenb==step)break; ptr=ptr->next; } if(lenb==step) tail=ptr->next; else tail=NULL; int ca=0,cb=0; while(ca<lena&&cb<lenb){ if(a->val<b->val){ s->next=a; a=a->next; ca++; } else{ s->next=b; b=b->next; cb++; } s=s->next; } while(ca<lena){ s->next=a; a=a->next; s=s->next; ca++; } while(cb<lenb){ s->next=b; b=b->next; s=s->next; cb++; } s->next=tail; return s; } void MergeAll(ListNode* root,int step,int total){ ListNode* s=root; ListNode* ptr; ListNode* a,*b; int count=0; int remain; while(count<total){ remain=total-count; if(remain<=step)return; ptr=s->next; a=ptr; for(int i=0;i<step;i++)ptr=ptr->next; b=ptr; s=Merge(s,a,b,step); count+=step*2; } } void MergeSort(ListNode* root,int total){ int step=1; while(step<total){ MergeAll(root,step,total); step*=2; } } ListNode *sortList(ListNode *head) { ListNode* root=new ListNode(0); root->next=head; int count=0; while(head!=NULL){ count++; head=head->next; } MergeSort(root,count); ListNode* ret=root->next; delete root; return ret; } };