剑指 Offer 06. 从尾到头打印链表

剑指 Offer 06. 从尾到头打印链表

方法一

顺序添加，再翻转。

class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode h = head;
        List<Integer> res = new ArrayList<>();
        while(h != null){
            res.add(h.val);
            h = h.next;
        }
        Collections.reverse(res);
        return res.stream().mapToInt(x -> x).toArray();
    }
}

方法二

利用栈后进先出的特性。

class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode h = head;
        Deque<Integer> stack = new ArrayDeque<>();
        while(h != null){
            stack.push(h.val);
            h = h.next;
        }
        int[] res = new int[stack.size()];
        int k = 0;
        while(!stack.isEmpty()){
            res[k++] = stack.pop();
        }

        return res;
    }
}

方法三

递归

class Solution {
    List<Integer> res = new ArrayList<>();

    public int[] reversePrint(ListNode head) {
        dfs(head);
        return res.stream().mapToInt(x -> x).toArray();
    }

    void dfs(ListNode head){
        if(head == null) return;
        dfs(head.next);
        res.add(head.val);
    }
}