剑指offer3：从尾到头打印链表每个节点的值

1. 题目描述

　　输入一个链表，从尾到头打印链表每个节点的值。

2. 思路和方法

2.1 推荐的方法

　　（1）栈，循环

　　后进先出，我们可以用栈实现这种顺序。每经过一个结点的时候，把该节点放到一个栈里面，当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。

2.2 不推荐的方法

　　（1）直接修改输入数据

　　如果可以修改原来链表的结构，那么把链表中链接结点的指针反转过来，改变链表的方向，然后就可以从头到尾输出了。

但是，打印通常是一个只读操作，我们不希望打印时修改内容，所以就得想别的办法。

　　（2）递归

　　递归在本质上就是一个栈结构，于是很自然地又想到了用递归来实现。每访问到一个结点的时候，先递归输出它后面的节点，再输出该节点自身，这样链表的输出结果就反过来了。

3. 核心代码

 1 class Solution {
 2 public:
 3     vector<int> printListFromTailToHead(ListNode* head) {
 4         vector<int> result;
 5         stack<int> nodes;
 6 
 7         ListNode* pNode = head;
 8         while (pNode != NULL){
 9             nodes.push(pNode->val);
10             pNode = pNode->next;
11         }
12         while (!nodes.empty()){
13             result.push_back(nodes.top());
14             nodes.pop();
15         }
16         return result;
17     }
18 };

View Code

4. C++完整测试

 1 #include<iostream>
 2 #include<string>
 3 #include <vector>
 4 #include<stack>
 5 
 6 using namespace std;
 7 
 8 struct ListNode
 9 {
10     char val;
11     ListNode* next;
12 };
13 
14 void createlist(ListNode *&head)
15 {
16     ListNode *p = head;
17     while (1)
18     {
19         char s;
20         cin >> s;
21         if (s != '#')
22         {
23             ListNode *newnode = new ListNode;
24             newnode->val = s;
25             newnode->next = NULL;
26             if (head == NULL)
27             {
28                 head = newnode;
29                 p = head;
30             }
31             else
32             {
33                 p->next = newnode;//往p后面添加新节点
34                 p = newnode;//最后一个节点变成新节点
35             }
36         }
37         else
38         {
39             break;
40         }
41     }
42 }
43 
44 class Solution {
45 public:
46     vector<int> printListFromTailToHead(ListNode* head) {
47         vector<int> result;
48         stack<int> nodes;
49 
50         ListNode* pNode = head;
51         while (pNode != NULL){
52             nodes.push(pNode->val);
53             pNode = pNode->next;
54         }
55         while (!nodes.empty()){
56             result.push_back(nodes.top());  // pop是弹出栈顶元素，top是获得栈顶元素，不弹出
57             nodes.pop();
58         }
59         return result;
60     }
61 };
62 
63 
64 int main()
65 {
66     Solution a;
67     ListNode *head = NULL;
68     createlist(head);
69     cout << "---------打印原始字符串序列！----------" << endl;
70     ListNode * p = head;
71     while (p != NULL)
72     {
73         //    if (p == head)
74         //        cout << p->val;
75         //    else
76         //        cout << " " << p->val;
77         cout << p->val;
78         p = p->next;
79     }
80     cout << endl;
81     cout << "--------打印原始字符串序列！----------" << endl;
82 
83     cout << "--------逆序打印----------" << endl;
84     vector<int> res;
85     res = a.printListFromTailToHead(head);
86 
87     //输出全部元素
88     vector<int>::iterator it;
89     for (it = res.begin(); it != res.end(); it++)
90     {
91         cout << (char)*it << " "; //vector int 转换为 char类型
92     }
93     cout << endl;
94     system("pause");
95     return 0;
96 }

View Code

参考资料

https://blog.csdn.net/u011475210/article/details/78106191

https://blog.csdn.net/u011275956/article/details/51321028

https://blog.csdn.net/slandarer/article/details/91863177（链表详解）