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

  思路：有两种方法。一种是借助栈的后进先出特性来实现；另一种是采用递归，递归的本质也是一个栈结构。

  测试用例：

  代码：

栈：

#include
    
     #include
     
      #include
      
       using namespace std;struct ListNode{    int                 m_nValue;    ListNode*           m_pNext;};ListNode* CreateListNode(int value){    ListNode* node = new ListNode();    node->m_nValue = value;    node->m_pNext = NULL;    return node;}void ConnectListNodes(ListNode* node1, ListNode* node2){    if (node1 != NULL && node2 != NULL)    {        node1->m_pNext = node2;    }}void PrintListNode(ListNode* pHead){    if (pHead == NULL)    {        cout << NULL;    }    while (pHead != NULL)    {        cout << pHead->m_nValue << " ";        pHead = pHead->m_pNext;    }    cout << endl;}void DestroyList(ListNode* pHead){    ListNode* node = pHead;    while (node != NULL)    {        pHead = pHead->m_pNext;        delete node;        node = pHead;    }}void PrintListTailToHead(ListNode* pHead){    stack
       
         nodes;    while (pHead != NULL)    {        nodes.push(pHead);        pHead = pHead->m_pNext;    }    while (!nodes.empty())    {        ListNode* node = nodes.top();        cout << node->m_nValue << " ";        nodes.pop();    }    cout << endl;}int main(){    ListNode* pNode1 = CreateListNode(1);    ListNode* pNode2 = CreateListNode(2);    ListNode* pNode3 = CreateListNode(3);    ListNode* pNode4 = CreateListNode(4);    ListNode* pNode5 = CreateListNode(5);    ConnectListNodes(pNode1, pNode2);    ConnectListNodes(pNode2, pNode3);    ConnectListNodes(pNode3, pNode4);    ConnectListNodes(pNode4, pNode5);    PrintListTailToHead(pNode1);    DestroyList(pNode1);    return 0;}
       
      
     
    

递归：

#include
    
     #include
     
      #include
      
       using namespace std;struct ListNode{    int                 m_nValue;    ListNode*           m_pNext;};ListNode* CreateListNode(int value){    ListNode* node = new ListNode();    node->m_nValue = value;    node->m_pNext = NULL;    return node;}void ConnectListNodes(ListNode* node1, ListNode* node2){    if (node1 != NULL && node2 != NULL)    {        node1->m_pNext = node2;    }}void DestroyList(ListNode* pHead){    ListNode* node = pHead;    while (node != NULL)    {        pHead = pHead->m_pNext;        delete node;        node = pHead;    }}void PrintListRecursion(ListNode* pHead){    if (pHead != NULL)    {        if (pHead->m_pNext != NULL)        {            PrintListRecursion(pHead->m_pNext);        }    }    cout << pHead->m_nValue << " ";}int main(){    ListNode* pNode1 = CreateListNode(1);    ListNode* pNode2 = CreateListNode(2);    ListNode* pNode3 = CreateListNode(3);    ListNode* pNode4 = CreateListNode(4);    ListNode* pNode5 = CreateListNode(5);    ConnectListNodes(pNode1, pNode2);    ConnectListNodes(pNode2, pNode3);    ConnectListNodes(pNode3, pNode4);    ConnectListNodes(pNode4, pNode5);    PrintListRecursion(pNode1);    DestroyList(pNode1);    return 0;}
      
     
    

  递归的代码虽然简洁，但是当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。显式用栈基于循环实现的代码的鲁棒性要好一些。