单链表

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

  1 #ifndef LINKEDLIST_H
  2 #define LINKEDLIST_H
  3 #define DEBUG
  4 
  5 #include<iostream>
  6 using namespace std;
  7 
  8 template <typename T>
  9 class LinkedList
 10 {
 11 public:
 12     template<typename T>
 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<T>* _head;
 23 public:
 24     LinkedList(void)
 25     {
 26         _head=0;
 27     }
 28 
 29     ~LinkedList(void)
 30     {
 31         Node<T>* p=_head;
 32         while(p){
 33             _head=_head->next;
 34             delete p;
 35             p=_head;
 36         }
 37     }
 38 
 39     Node<T>* getHead()const{
 40         return _head;
 41     }
 42 
 43     void insertInFront(T newData){
 44         _head=new Node<T>(newData,_head);
 45     }
 46 
 47     void show(){
 48         Node<T>* cur=_head;
 49         while(cur){
 50             cout<<cur->data<<' ';
 51             cur=cur->next;
 52         }
 53         cout<<endl;
 54     }
 55 
 56     void reverse(){
 57         Node<T>*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<T>* deleteMe){
 68         //assert(deleteMe!=0);
 69         if(!deleteMe)
 70             return false;
 71 
 72         /*Node<T>* cur=_head;
 73         if(cur==deleteMe){
 74             _head=deleteMe->next;
 75 #ifdef DEBUG
 76             cout<<deleteMe->data<<" is deleted."<<endl;
 77 #endif
 78             delete deleteMe;
 79             return true;
 80         }
 81         else{
 82             while(cur){
 83                 if(cur->next==deleteMe){
 84                     cur->next=deleteMe->next;
 85 #ifdef DEBUG
 86                     cout<<deleteMe->data<<" is deleted."<<endl;
 87 #endif
 88                     delete deleteMe;
 89                     return true;
 90                 }
 91                 cur=cur->next;
 92             }
 93             return false;
 94         }*/
 95         Node<T>* 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             else
104                 pre->next=cur->next;
105             delete cur;
106             return true;
107         }
108         return false;
109     }
110 
111     Node<T>* search(T data){
112         Node<T>* 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<T>*pre=0;
121         Node<T>*cur=_head;
122         while(cur&&cur->data!=data){
123             pre=cur;
124             cur=cur->next;
125         }
126         if(cur){
127             if(!pre){//delete head
128                 _head=cur->next;
129             }
130             else{
131                 pre->next=cur->next;
132             }
133             delete cur;
134         }
135 
136         /*Node<T>* cur=_head;
137 
138         if(cur&&cur->data==data){
139             _head=cur->next;
140             delete cur;
141             return;
142         }
143 
144         Node<T>* 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<T>* 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     }

159 };
160 
161 #endif//LINKEDLIST_H