题目描述:
输入一个链表,按链表值从尾到头的顺序返回一个ArrayList
思路及实现:
解法一:借助栈先进后出的性质,创建一个辅助栈,逐个压栈再逐个弹出至数组即可。
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
Stack <Integer> stack = new Stack<>(); //创建辅助栈
while(listNode != null) //将链表压栈
{
stack.push(listNode.val);
listNode = listNode.next;
}
ArrayList<Integer> list = new ArrayList<>(); //创建动态数组
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;
}
}