剑指Offer刷题记录，第六题。

方法一：暴力法

思路：直接遍历一遍链表，并使用ArrayList记录链表元素。再新建返回数组arrs，反向遍历ArrayList并将值存入arrs返回即可。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public int[] reversePrint(ListNode head) {
   
        ArrayList arr = new ArrayList();
        // ListNode hummyNode = new ListNode(-1);
        // hummyNode.next = head;
        while (head != null) {
   
            arr.add(head.val);
            head = head.next;
        }
        
        
        int[] arrs = new int[arr.size()];
        int idx = 0;
        for(int i = arr.size() - 1; i >= 0; i--) {
   
            arrs[idx++] = (int)arr.get(i);
        }
        return arrs;
    }
}

时间复杂度： O(N), 因为需要正向遍历一遍链表。
空间复杂度： O(N), 需要额外使用一个ArrayList来存放链表元素。

方法二：辅助栈

思路：没想到这一点，入栈和出栈顺序刚好符合本题要求。具体来说：从链表的头节点开始，依次将每个节点压入栈内，然后依次弹出栈内的元素并存储在数组中。

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
class Solution {
   
    public int[] reversePrint(ListNode head) {
   
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
   
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
   
            print[i] = stack.pop().val;
        }
        return print;
    }
}

时间复杂度： O(N), 因为需要正向遍历一遍链表。
空间复杂度： O(N), 需要额外使用一个Stack来存放链表元素。

方法三：递归法

思路：其实有想到递归，但没想到如何将链表末端元素放入列表中（原来是回溯）。具体来说：利用递归，先走到链表末端，回溯时依次将节点值加入列表，这样就可以实现链表值的倒序输出。图源自.

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */
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);
    }
}

时间复杂度： O(N), 递归N次。
空间复杂度： O(N), 系统栈大小为递归次数。
总结：本题最开始做以为会使用很多指针，没想到最后解法却是最朴素的解法，这给自己启迪是：开始做题容易想到暴力解就赶紧写出来一个暴力解，通过了再去考虑代码的优化。