题目：输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。
练习地址
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;
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：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);
}
}
}
复杂度分析
- 时间复杂度：O(n)。
- 空间复杂度：O(n)。
