单链表-白红宇

单链表

阅读量：4341 次

发布时间：2019-06-07

本文共 3087 字，大约阅读时间需要 10 分钟。

写了一个单链表的模板，欢迎大家批评指正。

1 #ifndef LINKEDLIST_H  2 #define LINKEDLIST_H  3 #define DEBUG  4   5 #include
     
        6 using namespace std;  7   8 template 
      
         9 class LinkedList 10 { 11 public: 12     template
       
         13     struct Node 14     { 15         T data; 16         Node* next; 17  18         Node(T data,Node* next):data(data),next(next){} 19         Node(T data):data(data),next(0){} 20     }; 21 private: 22     Node
        
         * _head; 23 public: 24     LinkedList(void) 25     { 26         _head=0; 27     } 28  29     ~LinkedList(void) 30     { 31         Node
         
          * p=_head; 32         while(p){ 33             _head=_head->next; 34             delete p; 35             p=_head; 36         } 37     } 38  39     Node
          
           * getHead()const{ 40 return _head; 41 } 42 43 void insertInFront(T newData){ 44 _head=new Node
           
            (newData,_head); 45 } 46 47 void show(){ 48 Node
            
             * cur=_head; 49 while(cur){ 50 cout<
             
              data<<' '; 51 cur=cur->next; 52 } 53 cout<
              
               *cur=_head,*next; 58 _head=0; 59 while(cur){ 60 next=cur->next; 61 cur->next=_head; 62 _head=cur; 63 cur=next; 64 } 65 } 66 67 bool remove(Node
               
                * deleteMe){ 68 //assert(deleteMe!=0); 69 if(!deleteMe) 70 return false; 71 72 /*Node
                
                 * cur=_head; 73 if(cur==deleteMe){ 74 _head=deleteMe->next; 75 #ifdef DEBUG 76 cout<
                 
                  data<<" is deleted."<
                  
                   next==deleteMe){ 84 cur->next=deleteMe->next; 85 #ifdef DEBUG 86 cout<
                   
                    data<<" is deleted."<
                    
                     next; 92 } 93 return false; 94 }*/ 95 Node
                     
                      * pre=0,*cur=_head; 96 while(cur&&cur!=deleteMe){ 97 pre=cur; 98 cur=cur->next; 99 }100 if(cur){101 if(!pre)102 _head=cur->next;103 else104 pre->next=cur->next;105 delete cur;106 return true;107 }108 return false;109 }110 111 Node
                      
                       * search(T data){112 Node
                       
                        * cur=_head;113 while(cur&&cur->data!=data){114 cur=cur->next;115 }116 return cur;117 }118 119 void remove(T data){120 Node
                        
                         *pre=0;121 Node
                         
                          *cur=_head;122 while(cur&&cur->data!=data){123 pre=cur;124 cur=cur->next;125 }126 if(cur){127 if(!pre){ //delete head128 _head=cur->next;129 }130 else{131 pre->next=cur->next;132 }133 delete cur;134 }135 136 /*Node
                          
                           * cur=_head;137 138 if(cur&&cur->data==data){139 _head=cur->next;140 delete cur;141 return;142 }143 144 Node
                           
                            * pre=cur;145 while(pre){146 cur=pre->next;147 if(cur&&cur->data==data){148 pre->next=cur->next;149 delete cur;150 return;151 }152 pre=cur;153 }*/154 }155 156 bool isEmpty(){157 return _head==0;158 }

1 /*Takes a pointer to the head of a linked list and determines if the list ends 2     *in a cycle or is NULL terminated. 3     */ 4     bool hasCycle(){ 5         Node
      
       * slow,*fast; 6         slow=fast=_head; 7         while(true){ 8             if(!fast||!fast->next) 9                 return false;10             else if(fast->next==slow||fast->next->next==slow)11                 return true;12             else{13                 slow=slow->next;14                 fast=fast->next->next;15             }16         }17     }