首页 > 代码库 > sort list (7)
sort list (7)
Sort a linked list in O(n log n) time using constant space complexity.
解决这个问题让我很是纠结，能不能用快速排序呢？我试了很多次，结果总是超时，甚至在用系统自带的stl时也是这样。为什么呢？事后想想，快速排序没有充分利用链表的连贯性，快速排序要交换值得时候必须要遍历链表。甚至当使用将链表中的值保存到数组，再将利用快速排序算法排序好的数组重新生成链表的方法也会超时！那就是说遍历的次数不能超过1了。
但是如果利用归并排序的话就没有这个问题了。归并排序只需要在merge的时候和分割的时候需要遍历链表，而且这两个情况都不需要遍历整个链表。
链表有一个显著地特点，那就是，只要给出一个起始指针，就能唯一确定一个链表，下面的代码利用了这个特点。
1 class Solution { 2 public: 3 ListNode *sortList(ListNode *head) { 4 if(!head||!head->next) 5 return head; 6 return mergesort(head);} 7 ListNode *mergesort(ListNode *head){ 8 if(!head||!head->next) 9 return head;10 ListNode *fast;11 ListNode *slow;12 ListNode *mid;13 fast=slow=head;14 while(fast&&fast->next){15 fast=fast->next->next;16 mid=slow;17 slow=slow->next;18 }19 mid->next=NULL;20 ListNode *l=mergesort(head);//排序完之后究竟谁在链表的第一个呢？一定是head吗？21 ListNode *r=mergesort(slow);//刚开始的时候没有记录返回值，直接用head与slow，错了！22 return merge(l,r);23 24 }25 26 ListNode *merge(ListNode *l,ListNode *r){27 ListNode *temp=new ListNode (0);28 ListNode *p=temp;29 while(l&&r){30 if(l->val<r->val){31 p->next=l;32 l=l->next;33 }34 else{35 p->next=r;36 r=r->next;37 }38 p=p->next;39 }40 if(!l)41 p->next=r;42 else43 p->next=l;44 p=temp->next;45 delete temp;46 return p;47 }48 };
顺便附上第一次的时候利用快速排序的代码，顿时觉得无比的拙劣！
1 //利用了数据结构与算法分析一书 的思路 2 int size(ListNode *head){ 3 int sum=0; 4 while(head!=NULL){ 5 head=head->next; 6 sum++; 7 } 8 return sum; 9 }10 11 int num(ListNode *head,int pos){12 int i;13 for(i=0;i<pos;i++)14 head=head->next;15 return head->val;16 }17 void assign(ListNode *head,int pos,int num){18 int i;19 for(i=0;i<pos;i++)20 head=head->next;21 head->val=num;22 }23 void swap1(ListNode *head,int i,int j){24 int temp=num(head,i);25 assign(head,i,num(head,j));26 assign(head,j,temp);27 }28 int partition(ListNode *head ,int l,int r,int pivot){29 do{30 while(num(head,++l)<pivot);31 while((r!=0)&&num(head,--r)>pivot);32 swap1(head,l,r);33 }while(l<r);34 swap1(head,l,r);35 return l;36 }37 void qsort1(ListNode *head,int i,int j){38 if(j<=i)39 return ;40 int pivotindex=(i+j)/2;41 swap1(head,pivotindex,j);42 int k=partition(head,i-1,j,num(head,j));43 swap1(head,k,j);44 qsort1(head,i,k-1);45 qsort1(head,k+1,j);46 }47 class Solution {48 public:49 ListNode *sortList(ListNode *head) {50 qsort1(head,0,size(head)-1);51 return head;52 }53 };
sort list (7)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。