题目描述:
输入一个链表,按链表值从尾到头的顺序返回一个ArrayList。
思路与代码:
-> 从尾到头输出 -> 先进后出 -> 栈的结构
两种方法:
- 递归的方法
- 有可能链表过长会导致栈溢出
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> arrayList = new ArrayList<>();
if (listNode != null) {
printListFromTailToHead(listNode.next);
arrayList.add(listNode.val);
/*** 先递归再add->倒序存入
* 牛逼!
*/
}
return arrayList;
}
- 利用栈的结构特性——先进后出
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> resList = new ArrayList<>();
Stack<Integer> stack = new Stack<>();
while (listNode != null) {
stack.push(listNode.val);
listNode = listNode.next;
}
while (!stack.isEmpty()) {
resList.add(stack.pop());
}
return resList;
}