题目：输入一个链表的头结点，从尾到头反过来打印出每个结点的值。
链表结点定义如下：
struct ListNode { int m_nKey; ListNode *m_pNext; };
解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序，可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出，而最后一个遍历到得结点第一个输出。这就是典型的“后进先出”，可以用栈实现这种顺序。每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。
实现代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void
PrintListReverse(ListNode *pHead)
{
std::stack<ListNode*> nodes;
ListNode *pNode = pHead;
while
(pNode != NULL)
{
nodes.push(pNode);
pNode = pNode->m_pNext;
}
while
(!nodes.empty())
{
pNode = nodes.top();
printf
(
"%d\t"
, pNode->m_nValue);
nodes.pop();
}
}
|
递归在本质上就是一个栈结构，于是很自然地想到用递归来实现。要实现反过来输出链表，每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结构就反过来了。
实现代码如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
void
PrintListReversely(ListNode* pListHead)
{
if
(pListHead != NULL)
{
// Print the next node first
if
(pListHead->m_pNext != NULL)
{
PrintListReversely(pListHead->m_pNext);
}
// Print this node
printf
(
"%d"
, pListHead->m_nKey);
}
}
|
本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3404192.html，如需转载请自行联系原作者
