單鏈表有兩種版本，分別是帶有頭結點和不帶有頭結點。
各自的翻轉如下。
不帶有頭結點的：
1 #include <iostream>
2 using namespace std;
3
4 struct node
5 {
6 int item;
7 node* next;
8 };
9
10 void insert(int i, node*& p)
11 {
12 node* q = new node;
13 if (q == 0)
14 {
15 exit(1);
16 }
17 q->item = i;
18 q->next = p;
19 p = q;
20 }
21
22 void print(node* p)
23 {
24 while (p != 0)
25 {
26 cout << p->item << ' ';
27 p = p->next;
28 }
29 cout << endl;
30 }
31
32 void clear(node*& p)
33 {
34 node* q;
35 while (p != 0)
36 {
37 q = p->next;
38 delete p;
39 p = q;
40 }
41 p = 0;
42 }
43
44 void reverse(node*& p)
45 {
46 node* p1, *p2, *p3;
47 p2 = p;
48 p1 = 0;
49 p3 = 0;
50 while (p2 != 0)
51 {
52 p3 = p2->next;
53 p2->next = p1;
54 p1 = p2;
55 p2 = p3;
56 }
57 p = p1;
58 }
59
60 int main()
61 {
62 node* p = 0;
63 for (int i = 0; i < 10; ++i)
64 {
65 insert(i, p);
66 }
67 print(p);
68 reverse(p);
69 print(p);
70 clear(p);
71 print(p);
72 return 0;
73 }
帶有頭結點的：
1 #include <iostream>
2 using namespace std;
3
4 struct node
5 {
6 int item;
7 node* next;
8 };
9
10 void init(node*& p)
11 {
12 p = new node;
13 p->next = 0;
14 }
15
16 void insert(int i, node* p)
17 {
18 node* q = new node;
19 q->item = i;
20 q->next = p->next;
21 p->next = q;
22 }
23
24 void print(node* p)
25 {
26 p = p->next;
27 while (p != 0)
28 {
29 cout << p->item << ' ';
30 p = p->next;
31 }
32 cout << endl;
33 }
34
35 void clear(node* p)
36 {
37 node* q = p->next;
38 p->next = 0;
39 while (q != 0)
40 {
41 p = q->next;
42 delete q;
43 q = p;
44 }
45 }
46
47 void destroy(node*& p)
48 {
49 clear(p);
50 delete p;
51 p = 0;
52 }
53
54 void reverse(node* p)
55 {
56 node* p1, *p2, *p3;
57 p2 = p->next;
58 p1 = 0;
59 p3 = 0;
60 while (p2 != 0)
61 {
62 p3 = p2->next;
63 p2->next = p1;
64 p1 = p2;
65 p2 = p3;
66 }
67 p->next = p1;
68 }
69
70 int main()
71 {
72 node* p;
73 init(p);
74 for (int i = 0; i < 10; ++i)
75 {
76 insert(i, p);
77 }
78 print(p);
79 reverse(p);
80 print(p);
81 clear(p);
82 print(p);
83 destroy(p);
84 return 0;
85 }
posted on 2011-05-15 19:31
unixfy 閱讀(297)
評論(0) 編輯 收藏 引用