剑指offer 面试题5：从尾到头打印链表

题目：输入一个单链表的头结点，从尾到头反过来打印出每个结点的值。

链表结点定义如下：

struct ListNode
{
    int m_nKey;
    ListNode * m_pNext;
};

思路分析：

将链表从头到尾输出比较容易，遍历即可。但是从尾到头的话，我们可能会想到将链表结点的指针反转过来，改变链表的方向，然后再从头到尾打印。但是这会改变链表本来的结构，所以这时候我们需要和面试官沟通，询问清楚链表的结构是否可以改变。

通常打印是一个只读操作，我们不希望打印时修改内容。所以我们假设这个题目不能改变链表的结构。

要打印链表，我们肯定要遍历链表。遍历单链表只能从头到尾，但是输出结点的顺序却是从尾到头。也就是说第一个遍历的结点最后一个输出，而最后一个遍历的结点第一个输出——这就是典型的“后进先出”。所以，我们可以借用栈来实现。

每遍历一个结点，将该结点放入栈中，遍历完链表后，再从栈顶开始逐个输出结点的值。

代码：

#include <iostream>
#include <stack>
using namespace std;

struct ListNode{
int m_nKey;
ListNode * m_pNext;
ListNode(int x):m_nKey(x), m_pNext(NULL){}
};

void PrintListReverse(ListNode * pHead){//传入的长度是数组string[]的容量
ListNode * pNode = pHead;
if(pNode == NULL) return;

stack< ListNode* > nodes;
while(pNode){
nodes.push(pNode);
pNode = pNode -> m_pNext;
} 
while(!nodes.empty()){
pNode = nodes.top();
cout << pNode -> m_nKey << endl;
nodes.pop();
}
}

ListNode * createList(){
int val;
cin >> val;
ListNode dummy_head(-1);
ListNode *pNode = &dummy_head;
while(val != -1){
ListNode* newNode = new ListNode(val); 
pNode -> m_pNext = newNode;
pNode = pNode -> m_pNext;
cin >> val;
}
return dummy_head.m_pNext;
}

int main(){
ListNode * head = createList();
PrintListReverse(head);
return 0;
}

既然想到了用栈来实现，而递归本质上是就是一个栈结构，我们是否可以用递归实现呢？

我们每访问到一个结点时，先递归输出它后面的结点，再输出该结点自身。

void PrintListReverse(ListNode * pHead){//传入的长度是数组string[]的容量
if (pHead)
{
if(pHead -> m_pNext){
PrintListReverse(pHead -> m_pNext);
}
cout << pHead -> m_nKey << endl;
}
}

虽然递归的代码非常简洁，但是当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。
测试用例：

1、功能测试（输入的链表有多个结点，输入的链表只有一个结点）

2、特殊输入测试（输入的链表头结点指针为NULL）
考点：

1、对单链表的理解和编程能力

2、对循环、递归和栈3个互相关联的概念的理解