剑指offer004 逆向打印链表

Problem:

从尾到头反过来打印出链表中每个结点的值。

Intuition:

所有逆序的操作都应该想到 stack 这个先进后出的数据结构

1.建立一个辅助栈 stack 和一个存储结构 ArrayList
2.将 原来链表中的值 一个个 push到 stack中
3.将 stack中存储的值 一个个 pop 到 ArrayList

Solution:

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