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

    1. struct ListNode{
    2.     int m_nKey;
    3.     struct ListNode *m_pNext;
    4. };
    • 在面试中如果我们打算修改输入的数据，最好先问面试官是不是允许做修改。

    • 通常打印是一个只读操作，我们不希望打印时修改内容。假设面试官也要求这个题目不能改变链表的结构。

    • 第一个遍历到的结点最后一个输出，而最后一个遍历到的结点第一个输出。这就是典型的“后进先出”，我们可以用栈实现这种顺序。

    • 每经过一个结点的时候，把该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始逐个输出结点的值，此时输出的结点的顺序已经反转过来了

      1. /*
      2. * PrintListReversingly_Interatively 打印逆转的list 相互作用
      3. */
      4. void PrintListReversingly_Interatively(ListNode* pHead)
      5. {
      6.   std::stack<ListNode*> nodes;
      7.   ListNode* pNode = pHead;
      8.   while(pNode != NULL)
      9.   {
      10.       nodes.push(pNode);        // 压栈
      11.       pNode = pNode->m_pNext;
      12.   }
      13.   while(!nodes.empty())
      14.   {
      15.       pNode = nodes.top();
      16.       printf("%d\t", pNode->m_nValue);
      17.       nodes.pop();            // 出栈
      18.   }
      19. }

    • 递归在本质上就是一个栈结构，于是很自然地又想到了用递归来实现

    • 每访问到一个结点的时候，先递归输出它后面的结点，再输出该结点自身，这样链表的输出结果就反过来了

      1. void PrintListReversingly_Recursively(ListNode* pHead)
      2. {
      3.   if(pHead != NULL)
      4.   {
      5.       if(pHead->m_pNext != NULL)
      6.       {
      7.           PrintListReversingly_Recursively(pHead->m_pNext);
      8.       }
      9.       printf("%d\t",pHead->m_nValue);
      10.   }
      11. }

    • 当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出

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