题解 | #从尾到头打印链表#

解体思路：链表遍历的顺序是从头到尾，可是输出的顺序是从尾到头。也就是说，第一个遍历遍历到的节点最后一个输出，而最后一个遍历的节点第一个输出，这是典型的“后进先出”，所以想到用栈这种数据结构来实现。每遍历一个节点的时候，把该节点入栈；当遍历完整个链表后，再从栈顶开始逐个输出节点的值，此时的节点的顺序已经反过来了。这样就实现了从尾到头打印链表。

时间复杂度：O(n)，n为链表的长度，每个节点仅遍历了一次；

空间复杂度：O(n)，为递归使用栈的大小，为链表长度n；

代码由C++来实现：

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> a;
        stack<int> s;
        //空链表的情况；
        if(head == nullptr){
            return a;
        }
        //如果链表不为空，将链表元素入栈；
        while(head != nullptr){
            s.push(head->val);
            head = head->next;
        }
        //元素出栈的过程就是从尾到头打印链表的结果
        while(!s.empty()){
            int temp = s.top();
            s.pop();
            a.push_back(temp);
        }
        return a;
    }
};

既然可以使用栈来实现，而栈本质上就是一个递归的结构，于是很自然就会想到用递归来实现。但是用递归来实现有一个问题：当链表非常长的时候，就会导致函数调用的层级很深，从而有可能导致函数调用栈溢出。显然用栈基于循环实现的代码的鲁棒性要好一些。