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

题目链接
方法1：递归
给不太能懂递归的朋友图解一下
递归的方法是，我们从头指针开始搜索，然后从尾指针开始回溯的时候返回链表的逆序序列
首先这是最初状态，我们从头指针开始

然后我们发现当前不是尾指针，于是先递归下去

继续递归

我们发现，当前指针的next是不存在的，所以这是尾指针了，开始回溯，回溯的时候记录序列即可



具体代码如下
时间复杂度：每个点都遍历了一遍，是O(n)
空间复杂度：每个点都遍历了一遍，开了一个数组来存，是O(n)

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;//记录答案数组
        if (head == NULL) return res;//当我们发现当前节点不存在的时候，直接返回空数组
        if (head->next == NULL) {//发现是尾指针，记录当前值并开始回溯
            res.push_back(head->val);
            return res;
        }
        res = printListFromTailToHead(head->next);//这里是递归下去，把返回的值先复制过来
        res.push_back(head->val);//然后把当前值加入到序列中
        return res;//返回答案
    }
};

方法2：利用vector的性质
我们知道vector有一个reverse函数，就是将序列倒序，于是我们可以顺序遍历链表，存在vector里面，然后倒序输出即可
时间复杂度：每个点都遍历了一遍，是O(n)
空间复杂度：一个数组记录答案，是O(n)

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;//记录答案的数组
        while (head != NULL) {//顺序遍历链表
            res.push_back(head->val);
            head = head->next;
        }
        reverse(res.begin(), res.end());//最后反转vector即可
        return res;
    }
};