[链表]从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

首先是最好写的方法

java的ArrayList可以直接向头部添加新的项
时间复杂度O(n)，因为就是遍历一遍，不需要除了输出空间以外额外的空间

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        //新建一个ArrayList来保存结果
        ArrayList<Integer> res = new ArrayList<Integer>();
        //遍历链表
        while(listNode != null){
            //add(index, E element)，向arraylist的第index位插入内容
            res.add(0, listNode.val);
            listNode = listNode.next;
        }
        return res;
    }
}

但是ArrayList向头部存储，会产生重新申请空间，重新分配空间等操作，并不是最优的。
网友说法vector在头部插入，可能需要多次重新分配空间，复制很多次数组

如果程序使用C++编写，还可以使用另一个库：reverse

首先将链表顺序存储进vector，然后使用reverse(vector.begin(), vector.end())来逆序排列
时间复杂度O(n)，也是遍历一遍，不需要额外空间

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;
    }
};

如果不依赖库呢？也是两种实现方式

一：使用栈

先将链表顺序入栈
全部入栈后，再全部弹栈并存储
时间复杂度O(n)，入栈+出栈 = n + n，需要额外的O(n)的栈空间

import java.util.ArrayList;
import java.util.Stack;
//引入额外的包Stack
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        Stack<Integer> stack = new Stack<Integer>();
        
        //入栈
        while(listNode != null){
            stack.push(listNode.val);
            listNode = listNode.next;
        }
        
        //弹栈
        while(!stack.empty()){
            res.add(stack.pop());
        }
        return res;
    }
}

二：使用递归

递归的特点是你可以控制，是顺序加入队列还是逆序（由递归调用的子函数和插入位置决定）

import java.util.ArrayList;
public class Solution {
    private ArrayList<Integer> res = new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode != null){
            //由于是递归调用，因此可能调用到null节点
            printListFromTailToHead(listNode.next);   //1
            res.add(listNode.val);                    //2
            //1和2的顺序，决定了res最终是顺序还是逆序，想想为什么？
        }
        return res;
    }
}