题目描述
输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
思路
1、非递归
listNode 是链表,只能从头遍历到尾,但是输出却要求从尾到头,这是典型的”先进后出”,我们可以想到栈!ArrayList 中有个方法是 add(index,value),可以指定 index 位置插入 value 值所以我们在遍历 listNode 的同时将每个遇到的值插入到 list 的 0 位置,最后输出 listNode 即可得到逆序链表。
- 时间复杂度:O(n2)
空间复杂度:O(n)
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> list = new ArrayList<Integer>();
ListNode temp = listNode;
while(temp != null) {
list.add(0,temp.val);
temp = temp.next;
}
return list;
}
}
2、递归实现
时间复杂度:O(n)
- 空间复杂度:O(n)
import java.util.ArrayList;
public class Solution {
ArrayList<Integer> list = new ArrayList<Integer>();
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if(listNode != null) {
printListFromTailToHead(listNode.next);
list.add(listNode.val);
}
return list;
}
}