題目：輸入一個鏈表琼牧，按鏈表值從尾到頭的順序返回一個ArrayList寇荧。
練習(xí)地址
https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035
https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
方法1：棧
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> result = new ArrayList<>();
if (listNode == null) {
return result;
}
ArrayList<Integer> stack = new ArrayList<>();
while (listNode != null) {
stack.add(listNode.val);
listNode = listNode.next;
}
for (int i = stack.size() - 1; i >= 0; i--) {
result.add(stack.get(i));
}
return result;
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(n)敞贡。
- 空間復(fù)雜度：O(n)稍走。
方法2：遞歸
/**
* public class ListNode {
* int val;
* ListNode next = null;
*
* ListNode(int val) {
* this.val = val;
* }
* }
*
*/
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ArrayList<Integer> result = new ArrayList<>();
if (listNode == null) {
return result;
}
addList(listNode, result);
return result;
}
private void addList(ListNode listNode, ArrayList<Integer> list) {
if (listNode != null) {
addList(listNode.next, list);
list.add(listNode.val);
}
}
}
復(fù)雜度分析
- 時間復(fù)雜度：O(n)皂林。
- 空間復(fù)雜度：O(n)原探。
