《剑指offer》05： 从尾到头打印链表

❝首先学习计算机科学及理论。接着形成自己编程的风格。然后把这一切都忘掉，尽管改程序就是了。—— 小浩❞

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

解法一【推荐】
遍历链表，每个链表结点值 push 进栈，最后将栈中元素依次 pop 到 list 中。

/***    public class ListNode {*        int val;*        ListNode next = null;**        ListNode(int val) {*            this.val = val;*        }*    }**/import java.util.ArrayList;import java.util.Stack;public class Solution {    /**     * 从尾到头打印链表     * @param listNode 链表头节点     * @return list     */    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {        ArrayList<Integer> res = new ArrayList<>();        if (listNode == null) {            return res;        }        Stack<Integer> stack = new Stack<>();        while (listNode != null) {            stack.push(listNode.val);            listNode = listNode.next;        }        while (!stack.isEmpty()) {            res.add(stack.pop());        }        return res;    }}

解法二【不推荐】
利用递归方式：

若不是链表尾结点，继续递归；
若是，添加到 list 中。
这种方式不推荐，当递归层数过多时，容易发生 Stack Overflow。

/***    public class ListNode {*        int val;*        ListNode next = null;**        ListNode(int val) {*            this.val = val;*        }*    }**/import java.util.ArrayList;import java.util.Stack;/** * @author bingo * @since 2018/10/28 */public class Solution {    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {        ArrayList<Integer> res = new ArrayList<>();        if (listNode == null) {            return res;        }        addElement(listNode, res);        return res;    }    private void addElement(ListNode listNode, ArrayList<Integer> res) {        if (listNode.next != null) {            // 递归调用            addElement(listNode.next, res);        }        res.add(listNode.val);    }}

1. 功能测试（输入的链表有多个结点；输入的链表只有一个结点）；
2. 特殊输入测试（输入的链表结点指针为空）。本题考点

   
   我把我写的所有题解整理成了一本电子书放在了 github 上，三天内冲击到 github 排行榜榜首！近 5w 人下载阅读！要获取的话，直接进入下方链接就可以了（记得给我点个 star）：

https://github.com/geekxh/hello-algorithm