题目
输入一个链表的头节点, 从尾到头反过来打印出每个节点的值. 链表定义如下:
- struct ListNode {
- int m_nValue;
- ListNode *m_pNext;
- };
分析
遍历的顺序是从头到尾, 可输出的顺序却是从尾到头. 也就是说, 第一个遍历到的节点最后一个输出, 而最后一个遍历到的节点第一个输出. 这就是典型的 "后进先出", 所以可以使用栈实现这种顺序.
040012296093679.jpg
每经过一个节点的时候, 就把该节点放到一个栈中, 当遍历完整个链表后, 再从栈顶开始逐个输出节点的值, 此时输出的节点已经反过来了.
- #include <iostream>
- #include <stack>
- using namespace std;
- void printListReverse(ListNode *pHead)
- {
- stack<ListNode *>nodes; // 创建一个栈
- ListNode *pNode = pHead; // 引用头指针
- while (pNode != nullptr) { // 节点不为空, 那么进行入栈, 并获取下一个节点
- nodes.push(pNode);
- pNode = pNode->m_pNext;
- }
- while (!nodes.empty()) { // 栈是否为空
- pNode = nodes.top(); // 获取栈顶节点
- printf("%d\t", pNode->m_nValue); // 打印数据
- nodes.pop(); // 出栈
- }
- }
既然想到了用栈实现这个函数, 而递归在本质上就是一个栈结构, 也是自然地又想到了用递归来实现. 要实现反过来输出链表, 我们每访问到一个节点的时候, 先递归输出它后面的节点, 再输出自身, 这样链表的输出结果就反过来了.
- void printListReverseRecursive(ListNode *pHead)
- {
- if (pHead != nullptr) {
- if (pHead->m_pNext != nullptr)
- {
- printListReverseRecursive(pHead->m_pNext);
- }
- printf("%d\t", pHead->m_nValue);
- }
- }
上面的基于递归的代码看起来很简洁, 但是有一个问题: 当链表非常长的时候, 就会导致函数调用的层级很深, 从而有可能导致函数调用栈溢出. 显然用栈基于循环的实现的代码的鲁棒性要好一些.
参考
《剑指 offer》
来源: http://www.jianshu.com/p/1cc28261c8ec