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

题目的主要信息：

• 输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值
• 返回值保存在vector的数组中

方法一：递归

具体做法：
我们都知道递归到底层后才会往上，因此我们可以递归遍历链表，将填充数组放到递归函数后面，就可以实现遍历到链表最后再逐渐往前将值填到数组中。

class Solution {
public:
    void recursion(ListNode* head, vector<int>& res){ //递归函数
        if(head != NULL){
            recursion(head->next, res); //先往链表深处遍历
            res.push_back(head->val); //再填充到数组就是逆序
        }
    }
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        recursion(head, res); //递归打印
        return res;
    }
};

复杂度分析：

• 时间复杂度：，递归遍历一次链表
• 空间复杂度：，递归栈的空间为链表长度

方法二：栈

具体做法：
递归的思想也可以用栈实现，递归本质上就是用栈实现的。我们可以顺序遍历链表，将链表的值push到栈中，然后再依次弹出栈中的元素，加入到数组中。

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        stack<int> s;
        while(head != NULL){ //正序输出链表到栈中
            s.push(head->val);
            head = head->next;
        }
        while(!s.empty()){ //输出栈中元素到数组中
            res.push_back(s.top());
            s.pop();
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，遍历链表是一个，弹空一个栈需要
• 空间复杂度：，栈空间最大长度是链表的长度

方法三：反转数组

具体做法：
题目只需要最后输出的数组是链表的逆序，那我们可以顺序遍历链表，依次输入到链表中，最后用reverse函数将数组反转即可。

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()); //函数反转数组
        return res;
    }
};

复杂度分析：

• 时间复杂度：，一次遍历，reverse函数复杂度也是
• 空间复杂度：，res属于返回函数必要空间，不属于额外空间

方法四：逆序填充数组

具体做法：
这种方法的思想是输入到数组中的值按照下标的逆序来输入，这样一来我们就要先确定vector数组有多大，可以先遍历一次链表得到链表长度也即是数组长度。然后从数组最后的下标开始按顺序填充链表中的值即可。

class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        int n = 0;
        ListNode* p = head; //遍历的指针
        while(p != NULL){ //统计链表长度
            n++;
            p = p->next;
        }
        vector<int> res(n, 0); //限定返回数组的大小
        p = head;
        while(p != NULL){ //遍历链表
            res[n - 1] = p->val; //数组上逆序记录
            p = p->next; //链表往后
            n--; //下标往前
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，统计长度一次遍历，填充数组一次遍历
• 空间复杂度：，res属于返回函数必要空间，无额外空间使用