"程序员面试题31：链表从尾到头反向输出实现方法总结"

程序员面试题精选：从尾到头遍历链表 题目描述： 输入一个链表的头结点，从尾到头反过来输出每个结点的值。链表结点定义如下： struct ListNode{ int m_nKey; ListNode* m_pNext; }; 分析： 这是一道很有意思的面试题，该题以及它的变体经常出现在各大公司的面试、笔试题中。我们需要找到一种方法来逆序输出链表的值。 我们可以先考虑从头到尾输出链表，这个相对简单。只需要遍历链表，依次输出每个结点的值即可。但是要实现从尾到头输出，需要想到一种更巧妙的方法。 一种常见的方法是，通过改变链表中链接结点的指针方向，将链表方向进行反转。这样就可以从头到尾输出了。反转链表的算法可以参考本人面试题精选系列的第19题。但是这种方法需要额外的操作，应该还有更好的方法。 另一种思路是，从头到尾遍历链表，每经过一个结点的时候，将该结点放到一个栈中。当遍历完整个链表后，再从栈顶开始输出结点的值，此时输出的结点的顺序已经反转过来了。这种方法需要维护一个额外的栈，实现起来比较麻烦。 既然想到了栈来实现这个函数，我们可以再进一步思考，递归本质上就是一个栈结构。因此，我们可以通过递归来实现从尾到头遍历链表。 具体实现： 为了实现从尾到头遍历链表，每当访问到一个结点时，我们先递归输出它后面的结点，再输出该结点自身。这样就可以输出链表的值的逆序结果。 下面是具体的代码实现： void ReversePrint(ListNode* pHead){ if(pHead != NULL){ if(pHead->m_pNext != NULL){ ReversePrint(pHead->m_pNext); } cout<<pHead->m_nKey<<endl; } } 这段代码首先判断结点是否为空，如果不为空，则判断该结点的下一个结点是否为空。如果下一个结点不为空，就递归输出下一个结点。然后，在输出当前结点的值。 这种方法通过递归实现，非常简洁且易于理解。它遵循了递归的原则：解决一个大规模问题可以先解决一个规模较小的问题，然后将大问题转化为小问题的解决。 总结： 这道题是程序员面试中经常出现的题目之一，在解决实际问题中是非常有用的。通过反向输出链表的值，我们能够更好地理解链表的结构和指针的使用。 在考虑解决问题的时候，我们可以尝试不同的思路和方法，综合考虑它们的优缺点。比较不同的解决方案，选择最优的方法去解决问题。 以上是对程序员面试题精选中“从尾到头遍历链表”这个题目的总结，通过递归的方式实现了链表值的逆序输出。这个题目考察了对链表结构和递归思想的理解与运用。它帮助我们更好地掌握面试中常见的问题和解决方法，提升自身的编程能力和面试水平。