题目

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

示例 1：
输入：head = [1,3,2]
输出：[2,3,1]

限制：
0 <= 链表长度 <= 10000

解题思路

1、遍历反转

从头到尾将链表打印到数组中，返回反转后的结果即可。

复杂度分析：

• 时间复杂度 O(N)： 遍历链表，递归 N 次，遍历结果数组 N 次，反转结果数组 N 次，3N 约等于 N。
• 空间复杂度 O(N)： 系统递归需要使用 O(N) 的栈空间，存储结果数组 要 O(N)，生成的反序数组要 O(N)，3N 约等于 N。

2、递归法

1. 递推阶段： 每次传入 head.next ，以 head == null（即走过链表尾部节点）为递归终止条件，此时直接返回。
2. 回溯阶段： 层层回溯时，将当前节点值加入列表，即tmp.add(head.val)。
3. 最终，将列表 tmp 转化为数组 res ，并返回即可。

复杂度分析：

• 时间复杂度 O(N)： 遍历链表，递归 N 次。
• 空间复杂度 O(N)： 系统递归需要使用 O(N) 的栈空间。

实现

1、遍历反转

仅使用 int 型数组

class Solution {
    public int[] reversePrint(ListNode head) {
        // 判空
        if (head == null) {
            return new int[]{};
        }
        // 链表存储的正序 int 数字
        int[] nums = new int[10000];
        // 记录链表共有多少个结点
        int index = 0;
        // 遍历链表取出值放入 nums
        while (head.next != null) {
            nums[index] = head.val;
            head = head.next;
            index++;
        }
        nums[index] = head.val;
        // 将 nums 的值倒序填入 result
        int[] result = new int[index + 1];
        for (int i = 0; i <= index; i++) {
            result[i] = nums[index - i];
        }
        return result;
    }
}

2、递归法

class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        // 递归获取倒序
        recur(head);
        int[] res = new int[tmp.size()];
        for (int i = 0; i < res.length; i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }
    // 递归获取倒序值
    void recur(ListNode head) {
        if (head == null) {
            return;
        }
        recur(head.next);
        tmp.add(head.val);
    }
}