[zz]链表倒序

  1 　　#include <stack>
  2 
  3 　　#include <string>
  4 
  5 　　#include <iostream>
  6 
  7 　　using namespace std;
  8 
  9 　　class OutFromEnd
 10 
 11 　　{
 12 
 13 　　public:
 14 
 15 　　typedef struct node1
 16 
 17 　　{
 18 
 19 　　int data;
 20 
 21 　　node1* next;
 22 
 23 　　node1(int d):data(d),next(NULL){}
 24 
 25 　　} node;
 26 
 27 　　OutFromEnd()

 28 
 29 　　{
 30 
 31 　　head=cur=new node(-1);
 32 
 33 　　}
 34 
 35 　　void add(int data)
 36 
 37 　　{
 38 
 39 　　node* tmp=new node(data);
 40 
 41 　　cur->next=tmp;
 42 
 43 　　cur=tmp;
 44 
 45 　　}
 46 
 47 　　//借用栈倒序输出链表
 48 
 49 　　//因为栈是先进后出，把链表中的元素存进栈中，链表前面的元素在栈底，后面的元素在栈顶，链表后面的元素先出栈
 50 
 51 　　void stackMethod()
 52 
 53 　　{
 54 
 55 　　if(NULL==head || NULL==head->next)
 56 
 57 　　{
 58 
 59 　　return;
 60 
 61 　　}
 62 
 63 　　node* tmp=head->next;
 64 
 65 　　stack<int> s;
 66 
 67 　　while(tmp!=NULL)
 68 
 69 　　{
 70 
 71 　　s.push(tmp->data);
 72 
 73 　　tmp=tmp->next;
 74 
 75 　　}
 76 
 77 　　while(!s.empty())
 78 
 79 　　{
 80 
 81 　　cout<<s.top()<<"\t";
 82 
 83 　　s.pop();
 84 
 85 　　}
 86 
 87 　　}
 88 
 89 　　
 90 
 91 　　void reverse()
 92 
 93 　　{
 94 
 95 　　if(NULL==head || NULL==head->next)
 96 
 97 　　{
 98 
 99 　　return;
100 
101 　　}
102 
103 　　cur=head->next;
104 
105 　　node* prev=NULL;
106 
107 　　node* pcur=head->next;
108 
109 　　node* next;
110 
111 　　while(pcur!=NULL)
112 
113 　　{
114 
115 　　if(pcur->next==NULL)
116 
117 　　{
118 
119 　　pcur->next=prev;
120 
121 　　break;
122 
123 　　}
124 
125 　　next=pcur->next;
126 
127 　　pcur->next=prev;
128 
129 　　prev=pcur;
130 
131 　　pcur=next;
132 
133 　　}
134 
135 　　head->next=pcur;
136 
137 　　node* tmp=head->next;
138 
139 　　while(tmp!=NULL)
140 
141 　　{
142 
143 　　cout<<tmp->data<<"\t";
144 
145 　　tmp=tmp->next;
146 
147 　　}
148 
149 　　}
150 
151 　　void print3()
152 
153 　　{
154 
155 　　recursion(head->next);
156 
157 　　}
158 
159 　　//用递归实现
160 
161 　　//很诚实的说盗用了别人的思想，真的太妙了，完全能看出你是否真的体会了递归的原理
162 
163 　　//正如那位哥们所说，递归就是一个进栈出栈的过程，链表前面的元素先进栈，在栈底，后面的元素后进栈，在栈顶，先出栈，哈哈。。。
164 
165 　　void recursion(node* head)
166 
167 　　{
168 
169 　　if(NULL==head)
170 
171 　　{
172 
173 　　return;
174 
175 　　}
176 
177 　　if(head->next!=NULL)
178 
179 　　{
180 
181 　　recursion(head->next);
182 
183 　　}
184 
185 　　//如果把这句放在第二个if前面，那就是从头到尾输出链表，曾经的你或许是用while或者用for循环输出链表，现在你又多了一种方式
186 
187 　　cout<<head->data<<"\t";
188 
189 　　}
190 
191 　　//借用数组实现
192 
193 　　void print4()
194 
195 　　{
196 
197 　　node* tmp=head->next;
198 
199 　　int len=0;
200 
201 　　while(tmp!=NULL)
202 
203 　　{
204 
205 　　++len;
206 
207 　　tmp=tmp->next;
208 
209 　　}
210 
211 　　tmp=head->next;
212 
213 　　int* A=new int[len] ;
214 
215 　　for(int i=len-1;i>=0;i--)
216 
217 　　{
218 
219 　　A[i]=tmp->data;
220 
221 　　tmp=tmp->next;
222 
223 　　}
224 
225 　　for(int i=0;i<len;i++)
226 
227 　　{
228 
229 　　cout<<A[i]<<"\t";
230 
231 　　}
232 
233 　　delete [] A;
234 
235 　　}
236 
237 　　private :
238 
239 　　node *head,*cur;
240 
241 　　};