剑指 offer 笔记 03 | 从尾到头打印链表

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

分析：
这里的关键点，有从尾到头；从链表返回 list；

「从尾到头」顺序打印，可以联想到一种数据结构，Stack是栈。它的特性是：先进后出(FILO, First In Last Out)。

java 工具包中的 Stack 是继承于「Vector」(矢量队列)的，由于 Vector 是通过数组实现的，这就意味着，Stack也是通过数组实现的，而非链表。

所以最佳思路是利用栈先入后出的特性完成（递归也是可以的）。

步骤：
1）先特殊判断，链表是否为空

2）不为空，则取出链表的数据，存放到 stack 里面，且连接下一个节点

3）创建一个 list

4）判断 stack 是否为空

5）stack 不为空，则取出 stack 的值，存入 list，并把 list 返回；

代码：

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

顺便附上牛客网大咖的递归代码：

public class Solution {
    ArrayList<Integer> arrayList=new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode!=null){
            this.printListFromTailToHead(listNode.next);
            arrayList.add(listNode.val);
        }
        return arrayList;
    }
}  

链接https://www.nowcoder.com/questionTerminal/d0267f7f55b3412ba93bd35cfa8e8035
来源：牛客网

总结：可以反馈学习 Stack 数据结构的特性，以及复习递归更层次的思想。