【数据结构】单链表—从尾到头输出单链表 — 栈 / 递归

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

思路一：遍历的顺序是从头到尾，而输出的顺序是从尾到头，也就是说第一个遍历的最后一个输出，最后一个遍历的第一个输出，这是先进后出，我们可以借助栈，遍历链表将每一个节点放入栈中，然后再从栈顶逐个输出节点的值。此时输出的顺序已经反过来了。

思路二：可以用栈实现我们就可以想到递归。我们每访问一个结点时，先递归输出后面结点的值，然后再输出自身的值，这样链表的输出顺序就反过来了。

代码如下：

template<class T>
struct ListNode
{
    T _value;
    ListNode<T>* _next;

    ListNode(const T& value)
        :_value(value),_next(NULL)
    {}
};

template<class T>
class List
{
public:
    List()
        :_head(NULL)
    {}
    bool PushBack();
   void ReversePrintStack()//从尾到头打印单链表，不改变链表结构，借助栈
    {
        if(_head == NULL)
            return;
        if(_head->_next == NULL)
        {
            Print();
            return;
        }
        stack<T> s;
        ListNode<T>* cur = _head;

        while(cur != NULL)
        {
            s.push(cur->_value);
            cur = cur->_next;
        }
        while(!s.empty())
        {
            cout<<s.top()<<"->";
            s.pop();
        }
        cout<<"NULL"<<endl;
    }

    void ReversePrintR()//从尾到头打印单链表，不改变链表结构，递归
    {
        if(_head == NULL)
            return;
        if(_head->_next == NULL)
        {
            Print();
            return;
        }
        _ReversePrintR(_head);
        cout<<"NULL"<<endl;
    }

    void _ReversePrintR(ListNode<T>* node)
    {
        if(node == NULL)
            return;
        if(node != NULL)
        {
            _ReversePrintR(node->_next);
        }
        cout<<node->_value<<"->";
    }
private:
    ListNode<T>* _head;
};