题目
输入一个链表的头节点，从尾到头反过来打印出每个节点的值。链表定义如下：
struct ListNode {
int m_nValue;
ListNode *m_pNext;
};
分析
遍历的顺序是从头到尾，可输出的顺序却是从尾到头。也就是说，第一个遍历到的节点最后一个输出，而最后一个遍历到的节点第一个输出。这就是典型的“后进先出”，所以可以使用栈实现这种顺序。
040012296093679.jpg
每经过一个节点的时候，就把该节点放到一个栈中，当遍历完整个链表后，再从栈顶开始逐个输出节点的值，此时输出的节点已经反过来了。
#include <iostream>
#include <stack>
using namespace std;
void printListReverse(ListNode *pHead)
{
stack<ListNode *>nodes; // 创建一个栈
ListNode *pNode = pHead; // 引用头指针
while (pNode != nullptr) { // 节点不为空，那么进行入栈，并获取下一个节点
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while (!nodes.empty()) { // 栈是否为空
pNode = nodes.top(); // 获取栈顶节点
printf("%d\t", pNode->m_nValue); // 打印数据
nodes.pop(); // 出栈
}
}
既然想到了用栈实现这个函数，而递归在本质上就是一个栈结构，也是自然地又想到了用递归来实现。要实现反过来输出链表，我们每访问到一个节点的时候，先递归输出它后面的节点，再输出自身，这样链表的输出结果就反过来了。
void printListReverseRecursive(ListNode *pHead)
{
if (pHead != nullptr) {
if (pHead->m_pNext != nullptr)
{
printListReverseRecursive(pHead->m_pNext);
}
printf("%d\t", pHead->m_nValue);
}
}
上面的基于递归的代码看起来很简洁，但是有一个问题：当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。显然用栈基于循环的实现的代码的鲁棒性要好一些。
参考
《剑指offer》
