从尾到头打印链表

一、题目描述：

二、解法一：（递归法）
解题思路：不断遍历链表，递归的最里层是将最后一个元素3加到数组ret的最后，倒数第二层是将元素2加到数组ret最后，…，最后得到数组{3,2,1}。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> ret = new ArrayList<>();
    if (listNode != null) {
        ret.addAll(printListFromTailToHead(listNode.next));
        ret.add(listNode.val);
    }
    return ret;
}

三、解法二：（使用头插法）
解题思路：首先，定义一个head节点，将数组的第一个元素连接到head节点后面，然后再将head节点的后一个元素替换剩下数组的第一个元素的后面部分，再连接到head节点，重复上述步骤。。。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    // 头插法构建逆序链表
    ListNode head = new ListNode(-1);
    while (listNode != null) {
        ListNode memo = listNode.next;
        listNode.next = head.next;
        head.next = listNode;
        listNode = memo;
    }
    // 构建 ArrayList
    ArrayList<Integer> ret = new ArrayList<>();
    head = head.next;
    while (head != null) {
        ret.add(head.val);
        head = head.next;
    }
    return ret;
}

三、解法三：（堆栈）
解题思路：按顺序进栈，再按顺序出栈，perfect。

public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    Stack<Integer> stack = new Stack<>();
    while (listNode != null) {
        stack.push(listNode.val);
        listNode = listNode.next;
    }
    ArrayList<Integer> ret = new ArrayList<>();
    while (!stack.isEmpty())
        ret.add(stack.pop());
    return ret;
}