从尾到头打印链表

方法一：递归

思路：

我们都知道链表无法逆序访问，那肯定无法直接遍历链表得到从尾到头的逆序结果。但是我们都知道递归是到达底层后才会往上回溯，因此我们可以考虑递归遍历链表，因此三段式如下：

终止条件： 递归进入链表尾，即节点为空节点时结束递归。

返回值： 每次返回子问题之后的全部输出。

本级任务： 每级子任务递归地进入下一级，等下一级的子问题输出数组返回时，将自己的节点值添加在数组末尾。

具体做法：

step 1：从表头开始往后递归进入每一个节点。

step 2：遇到尾节点后开始返回，每次返回依次添加一个值进入输出数组。

step 3：直到递归返回表头。

代码：

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    void recurision(ListNode* head,vector<int>& res){
        //递归的终止条件：如果向下递归到达了链表的null，则就可以向上返回
        if(head==NULL){
            return;
        }
        //本级任务：
        //1.不断向下递归：将大问题分解成小问题
        //2.每次把当前的节点的值添加到返回的数组的后面
        recurision(head->next,res);
        res.push_back(head->val);
    }
    //读入链表的头结点，返回的是从尾到头的数组
    vector<int> printListFromTailToHead(ListNode* head) {
        //开创一个新的res容器用来存从尾到头的打印的数组
        vector<int> res;
        //递归函数
        recurision(head,res);
        return res;
    }
};

方法二：栈（先进后出）

思路：

1.先将链表中的所有节点的值都存入到栈中

2.再将栈中的所有的值返回，每返回一个值就将那个值存入到vector中

3.返回vector

代码：

class Solution{
    public:
     vector<int> printListFromTailToHead(ListNode* head){
        //用栈写：因为栈是先进后出的额结构：与递归的思想是类似的
         stack<int> node;
         //创建一个容器：用于存逆序的链表的节点的值
        vector<int> now;
        //遍历整个链表，将每个节点的值用push函数放入栈中
        while(head!=NULL){
             node.push(head->val);
             head=head->next;
        }
        //只要栈不为空，就用top()获得栈的头结点，放入vector中
        //再让现在的栈顶元素出栈
        while(!node.empty()){
            now.push_back(node.top());
            node.pop();
        }
         return now;
     }
};