用快排思想实现单链表

算法思想：对于一个链表，以head节点的值作为key，然后遍历之后的节点，可以得到一个小于key的链表和大于等于key的链表；由此递归可以对两个链表分别进行快速。这里用到了快速排序的思想即经过一趟排序能够将小于key的元素放在一边，将大于等于key的元素放在另一边；

面试回答：如果面试官问快速排序是否适合单链表，答案当然是不适合；但是如果问单链表可不可以用快速排序，答案当然是肯定的；下面贴出一段拙劣的代码，希望大家修正！

1. struct LinkNode{  
2.     int value;  
3.     LinkNode* next;  
4.     LinkNode(): value(0), next(NULL) {};  
5. };  
6.   
7.   
8. void Quicksort(LinkNode* &head, LinkNode* &end){  
9.     LinkNode *head1, *head2, *end1, *end2;  /*  记录每次分割后前后两个链表的头尾节点*/  
10.     head1 =  head2 = end1 = end2  = NULL;     
11.       
12.     if( head == NULL ) return;  //如果遍历的当前节点为空，返回  
13.   
14.     LinkNode *p, *pre1, *pre2;  /*用于遍历链表将链表中的元素分成大于key和小于key两个部分*/  
15.     p = pre1 = pre2 = NULL;  
16.       
17.     int key = head->value;  
18.     p = head->next; head->next = NULL;    //将head的值孤立出来  
19.     while( p != NULL ) {  
20.         //小于key的链表  
21.         if ( p->value < key ){  
22.             if( !head1 ) { head1 = p; pre1 = p; }  
23.             else{ pre1->next = p; pre1 = p; }  
24.             p = p->next;  
25.             pre1->next = NULL;  
26.         }  
27.         //大于等于key的链表  
28.         else{  
29.             if( !head2 ) { head2 = p; pre2 = p; }  
30.             else { pre2->next = p; pre2 = p; }  
31.             p = p->next;  
32.             pre2->next = NULL;  
33.         }  
34.     }  
35.   
36.     end1 = pre1; end2 = pre2;   /*产生新链表的首尾节点*/  
37.   
38.     //对左右两个链表进行递归快排  
39.     Quicksort(head1, end1);  
40.     Quicksort(head2, end2);  
41.   
42.     //从递归栈返回的时候，将key节点和左右两个链表连起来  
43.     //左右链表都存在  
44.     if( end1 && head2){  
45.         end1->next = head;   head->next = head2;  
46.         head = head1;   end = end2;}  
47.   
48.     //只有左链表  
49.     else if(end1) {   
50.         end1->next = head;   
51.         end = head; head = head1; }   
52.   
53.     //只有右链表  
54.     else if(head2){   
55.         head->next = head2;  end = end2;}   
56. } 
    

最后

以上就是有魅力墨镜为你收集整理的用快排思想实现单链表的全部内容，希望文章能够帮你解决用快排思想实现单链表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。