有一个链表,然后请对它进行排序;
这里先写了一个归并排序;
#include<iostream> #include<vector> #include<algorithm> #include<ctime> using namespace std; struct ListNode { int val; ListNode* next; }; int getLength(ListNode* head); void mergeSort(ListNode*& head, ListNode*& first,ListNode*& tail,int n ); void merge(ListNode* lH,ListNode* rH,ListNode*& first,ListNode*& tail); ListNode* sortLinkList(ListNode *head) { if ( !head ) return head; int n =getLength(head); ListNode* first=NULL, *tail=NULL; mergeSort(head,first,tail,n); return first; } int getLength(ListNode* head) { int n=0; while(head) { n++; head=head->next; } return n; } void mergeSort(ListNode*& head, ListNode*& first,ListNode*& tail,int n ) { if ( !head || n<=0 ) return; if ( n== 1 ) { first=tail=head; return; } int half= n>>1; ListNode* lHead=NULL, *lTail=NULL; mergeSort(head,lHead,lTail,half); head=lTail->next; ListNode* rHead=NULL,*rTail=NULL; mergeSort(head,rHead,rTail,n-half); ListNode* rest=NULL; if ( lTail ) {rest=lTail->next;lTail->next=NULL;} if ( rTail ) {rest=rTail->next;rTail->next=NULL;} merge(lHead,rHead,first,tail); tail->next=rest; } void merge(ListNode* lH,ListNode* rH,ListNode*& first,ListNode*& tail) { ListNode guard; tail=&guard; ListNode tmp; tmp.val=INT_MAX; while( lH || rH ) { ListNode* toAdd=&tmp; if ( lH && lH->val <toAdd->val) toAdd=lH; if ( rH && rH->val < toAdd->val ) toAdd=rH; if ( toAdd == lH ) lH=lH->next; else rH=rH->next; tail->next=toAdd; tail=tail->next; } first=guard.next; }