單鏈表的逆轉，關鍵在于三個輔助指針，前兩個指針用于逆轉，最后一個用于記錄剩下來的節點，不然鏈表就丟失了。
這里是用的帶頭結點的鏈表，考慮鏈表中沒有節點和只有一個節點的情況就不用逆轉了。
1 #include <iostream>
2 using namespace std;
3
4 struct node
5 {
6 int data;
7 node * next;
8 };
9
10 node * init()
11 {
12 node * head = new node;
13 if (head == 0)
14 {
15 exit(1);
16 }
17 head->next = 0;
18 return head;
19 }
20
21 node * insert(int item, node * pre)
22 {
23 node * tmp = new node;
24 if (tmp == 0)
25 {
26 exit(1);
27 }
28 tmp->data = item;
29 tmp->next = pre->next;
30 pre->next = tmp;
31 return tmp;
32 }
33
34 node * create(node * head)
35 {
36 for (int i = 0; i < 10; ++i)
37 {
38 insert(i, head);
39 }
40 return head;
41 }
42
43 node * reverse(node * head)
44 {
45 node * p1 = head->next;
46 if (p1 == 0)
47 {
48 return head;
49 }
50
51 node * p2 = p1->next;
52 if (p2 == 0)
53 {
54 return head;
55 }
56
57 node * p3;
58
59 while (p2 != 0)
60 {
61 p3 = p2->next;
62 p2->next = p1;
63 if (p1 == head->next)
64 {
65 p1->next = 0;
66 }
67 p1 = p2;
68 p2 = p3;
69 }
70 head->next = p1;
71 return head;
72 }
73
74 void clear_(node * head)
75 {
76 node * p = head->next, * q;
77 while (p != 0)
78 {
79 q = p->next;
80 delete p;
81 p = q;
82 }
83 head->next = 0;
84 }
85
86 void clear(node * head)
87 {
88 clear_(head);
89 delete head;
90 }
91
92 node * copy(node * des, node * src)
93 {
94 clear_(des);
95 node * p = src->next, * q, * d = des;
96 while (p != 0)
97 {
98 q = new node;
99 q->data = p->data;
100 q->next = 0;
101 d->next = q;
102 d = q;
103 p = p->next;
104 }
105 return des;
106 }
107
108 void print(node * head)
109 {
110 node * p = head->next;
111 while (p != 0)
112 {
113 cout << p->data << ' ';
114 p = p->next;
115 }
116 cout << endl;
117 }
118
119 int main()
120 {
121 node * t1 = init();
122 create(t1);
123 print(t1);
124
125 node * t2 = init();
126 copy(t2, t1);
127 print(t2);
128 reverse(t2);
129 print(t2);
130
131 return 0;
132 }
posted on 2011-04-27 13:48
unixfy 閱讀(488)
評論(0) 編輯 收藏 引用