《剑指offer》面试题5—从尾到头打印链表

重要思路：

这个问题肯定要遍历链表，遍历链表的顺序是从头到尾，而要输出的顺序却是从尾到头，典型的“后进先出”，可以用栈实现。

注意stl栈的使用，遍历stack的方法。

 1 #include <iostream>
 2 #include <stack>
 3 using namespace std;
 4 
 5 class Node
 6 {
 7 public:
 8     Node(int v, Node* n)
 9     {val = v;
10     next = n;}
11     ~Node(){}
12     int val;
13     Node* next;
14 };
15 Node * phead = NULL;
16 
17 void AddNode(int val)
18 {
19     Node* pnode = new Node(val,NULL);
20     //Node one_node(val,NULL); 这里有大bug！如果这样写，在函数退出时自动调用析构函数！链表就乱了！
21     if(phead == NULL)
22     {
23         phead = pnode;
24     }
25     else
26     {
27         Node* p = phead;
28         while(p->next != NULL)
29         {
30             p = p->next;
31         }
32         p->next = pnode;
33     }
34     }
35 void PrintLink()
36 {
37     Node* p = phead;
38     while(p != NULL)
39     {
40         int temp = p->val;
41         cout<<temp<<endl;
42         p = p->next;
43     }
44 }
45 void PrintLinkReverse()
46 {
47     stack<Node*> my_s;
48     Node* p = phead;
49     while(p != NULL)
50     {
51         my_s.push(p);
52         p = p->next;
53     }
54     while(!my_s.empty())
55     {
56         Node* temp = my_s.top();   //return the top value
57         cout<<temp->val<<endl;
58         my_s.pop();  //delete the top value, no return
59 
60     }
61 }
62 
63 int main()
64 {
65     //freopen("in.txt","r",stdin);
66     int val;
67     cin>>val;
68     while(val != 0)
69     {
70         AddNode(val);
71         cin>>val;
72     }
73     PrintLink();
74     cout<<"Reverse:"<<endl;
75     PrintLinkReverse();
76     return 0;
77 }

View Code