剑指offer - 从尾到头打印链表

题目

输入一个链表的头节点，从尾到头反过来打印出每个节点的值。链表定义如下：

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》