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

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

1. 题目描述

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

2. 思路和方法

2.1 推荐的方法

（1）栈，循环

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

2.2 不推荐的方法

（1）直接修改输入数据

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

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

（2）递归

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

3. 核心代码

class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
stack<int> nodes; ListNode* pNode = head;
while (pNode != NULL){
nodes.push(pNode->val);
pNode = pNode->next;
}
while (!nodes.empty()){
result.push_back(nodes.top());
nodes.pop();
}
return result;
}
};

4. C++完整测试

#include<iostream>
#include<string>
#include <vector>
#include<stack> using namespace std; struct ListNode
{
char val;
ListNode* next;
}; void createlist(ListNode *&head)
{
ListNode *p = head;
while ()
{
char s;
cin >> s;
if (s != '#')
{
ListNode *newnode = new ListNode;
newnode->val = s;
newnode->next = NULL;
if (head == NULL)
{
head = newnode;
p = head;
}
else
{
p->next = newnode;//往p后面添加新节点
p = newnode;//最后一个节点变成新节点
}
}
else
{
break;
}
}
} class Solution {
public:
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
stack<int> nodes; ListNode* pNode = head;
while (pNode != NULL){
nodes.push(pNode->val);
pNode = pNode->next;
}
while (!nodes.empty()){
result.push_back(nodes.top()); // pop是弹出栈顶元素，top是获得栈顶元素，不弹出
nodes.pop();
}
return result;
}
}; int main()
{
Solution a;
ListNode *head = NULL;
createlist(head);
cout << "---------打印原始字符串序列！----------" << endl;
ListNode * p = head;
while (p != NULL)
{
// if (p == head)
// cout << p->val;
// else
// cout << " " << p->val;
cout << p->val;
p = p->next;
}
cout << endl;
cout << "--------打印原始字符串序列！----------" << endl; cout << "--------逆序打印----------" << endl;
vector<int> res;
res = a.printListFromTailToHead(head); //输出全部元素
vector<int>::iterator it;
for (it = res.begin(); it != res.end(); it++)
{
cout << (char)*it << " "; //vector int 转换为 char类型
}
cout << endl;
system("pause");
return ;
}