从尾到头打印单链表

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

链表的节点定义如下：

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

分析：

一般情况下，遇到这种问题，首先应该问清楚面试官是否可以改变原有的链表结构，自己再做分析。

void PrintListReversingly_Iteratively(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();
    }
}

void PrintListReversingly_Recursively(ListNode* pHead)
{
    if(pHead != NULL)
    {
        if (pHead->m_pNext != NULL)
        {
            PrintListReversingly_Recursively(pHead->m_pNext);
        }
 
        printf("%d\t", pHead->m_nValue);
    }
}

说明：用递归的代码看起来很简洁，但是如果一个链表非常长，于是递归调用的深度越深，就有可能导致栈溢出，因此利用循环实现的代码的鲁棒性（健壮性）会更好些。