单链表的逆转
带头结点的单链表
一种方法是判断是否没有数据节点、只有一个数据节点。这种情况不翻转，在翻转循环里还要判断是否只有是第一个结点，如果是则将该结点的 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 阅读(284)
评论(0) 编辑 收藏 引用