从尾到头打印链表

链表结点定义如下：

解决这个问题肯定要遍历链表。遍历的顺序是从头到尾的顺序，可输出的顺序却是从尾到头。也就是说第一个遍历到的结点最后一个输出，而最后一个遍历到得结点第一个输出。这就是典型的“后进先出”，可以用栈实现这种顺序。每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了。

实现代码如下：

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

<code>void</code> <code>PrintListReverse(ListNode *pHead)</code>

<code>{</code>

<code>    </code><code>std::stack&lt;ListNode*&gt; nodes;</code>

<code>    </code><code>ListNode *pNode = pHead;</code>

<code>    </code><code>while</code><code>(pNode != NULL)</code>

<code>    </code><code>{</code>

<code>        </code><code>nodes.push(pNode);</code>

<code>        </code><code>pNode = pNode-&gt;m_pNext;</code>

<code>    </code><code>}</code>

<code>    </code><code>while</code><code>(!nodes.empty())</code>

<code>        </code><code>pNode = nodes.top();</code>

<code>        </code><code>printf</code><code>(</code><code>"%d\t"</code> <code>, pNode-&gt;m_nValue);</code>

<code>        </code><code>nodes.pop();</code>

<code>}</code>

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

<code>void</code> <code>PrintListReversely(ListNode* pListHead)</code>

<code>      </code><code>if</code><code>(pListHead != NULL)</code>

<code>      </code><code>{</code>

<code>            </code><code>// Print the next node first</code>

<code>            </code><code>if</code> <code>(pListHead-&gt;m_pNext != NULL)</code>

<code>            </code><code>{</code>

<code>                  </code><code>PrintListReversely(pListHead-&gt;m_pNext);</code>

<code>            </code><code>}</code>

<code>            </code><code>// Print this node</code>

<code>            </code><code>printf</code><code>(</code><code>"%d"</code><code>, pListHead-&gt;m_nKey);</code>

<code>      </code><code>}</code>

本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3404192.html，如需转载请自行联系原作者