單鏈表的逆轉
帶頭結點的單鏈表
一種方法是判斷是否沒有數據節點、只有一個數據節點。這種情況不翻轉，在翻轉循環里還要判斷是否只有是第一個結點，如果是則將該結點的 next 置為 0。
一種效率更好的方式是：
void reverse(Node* head)
{
Node* p1, *p2, *p3;
p1 = p2 = 0;
p3 = head->next;
while (p3 != 0)
{
p2 = p3;
p3 = p3->next;
p2->next = p1;
p1 = p2;
}
head->next = p2;
}
這種方式即包括了沒有數據節點、只有一個數據節點的情況，也可以處理將第一個結點的 next 置為 0 的情況。
所以這種方式既明確效率也更高。
1 #include <iostream>
2 using namespace std;
3
4 template <typename T>
5 class Link
6 {
7 public:
8 template <typename T>
9 struct Node
10 {
11 T data;
12 Node<T>* next;
13 };
14 private:
15 Node<T>* head;
16 public:
17 Link()
18 {
19 head = new Node<T>;
20 head->next = 0;
21 }
22 ~Link()
23 {
24 Node<T>* p = head->next, *q = 0;
25 while (p != 0)
26 {
27 q = p->next;
28 delete p;
29 p = q;
30 }
31 delete head;
32 }
33 Node<T>* Head()
34 {
35 return head;
36 }
37 void insert(T item, Node<T>* p)
38 {
39 Node<T>* q = new Node<T>;
40 q->next = p->next;
41 q->data = item;
42 p->next = q;
43 }
44
45 void reverse()
46 {
47 Node<T>* p1, *p2, *p3;
48 p1 = p2 = 0;
49 p3 = head->next;
50 while (p3 != 0)
51 {
52 p2 = p3;
53 p3 = p3->next;
54 p2->next = p1;
55 p1 = p2;
56 }
57 head->next = p2;
58 }
59
60 // friend template <typename T> ostream& operator <<(ostream& out, Link<T>& link);
61 };
62
63 template <typename T>
64 ostream& operator <<(ostream& out, Link<T>& link)
65 {
66 const Link<T>::Node<T>* p = link.Head()->next;
67 while (p)
68 {
69 out << p->data << ' ';
70 p = p->next;
71 }
72 return out;
73 }
74
75 int main()
76 {
77 Link<int> link;
78 for (int i = 0; i < 10; ++i)
79 {
80 link.insert(i, link.Head());
81 }
82 cout << link << endl;
83
84 link.reverse();
85
86 cout << link << endl;
87 }
posted on 2011-04-29 00:13
unixfy 閱讀(303)
評論(0) 編輯 收藏 引用