7.12 能自己 A 出来

题目描述

原题链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

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

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

解题思路：递归回溯

K神题解：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/solution/

递归回溯的方法体怎么写：

• 最开始写的是递归的终止条件，然后返回 return 即可。
• 接下来就是递归体现：调用递归方法。
• 最后就是回溯时要干什么。

递归回溯 递归回溯，先递归再回溯，但最开始要写上递归的终止条件。

// 把ArrayList 放外面，递归方法才可以使用
List<Integer> tmp = new ArrayList<>();
public int[] reversePrint(ListNode head) {
    // 注意是放 head 不是 head.next
    recur(head);
    int[] res = new int[tmp.size()];
    for(int i = 0; i < res.length; i++) {
        res[i] = tmp.get(i);
    }
    return res;
}
public void recur(ListNode head) {
    if(head == null) return;
    recur(head.next);
    tmp.add(head.val);
}