[数据结构与算法]剑指 Offer 06. 从尾到头打印链表

每日简短一刷，保持手感系列

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

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

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

题目要求从尾到头开始打印数组，看到这个很轻松的就想能想到栈的特性，即先进后出。

顺序遍历一遍数组，将元素都塞入到栈中，然后遍历栈，把元素放入一个新数组中，此时新数组的顺序就是尾部到头部的顺序了。

我们来看一下答案：

class Solution {
    public int[] reversePrint(ListNode head) {
          Deque<ListNode> stack = new ArrayDeque();
          while (head != null) {
            stack.addLast(head);
            head = head.next;
          }
          int size = stack.size();
          int[] ret = new int[size];
          for (int i = 0; i < size; i++) {
            ret[i] = stack.removeLast().val;
          }
          return ret;
    }
}

时间复杂度 O(n)
空间复杂度 O(n)

当然，还有能想到的就是递归了，递归也是利用调用栈嘛，一样的思路。

class Solution {
    ArrayList<Integer> list= new ArrayList();
    public int[] reversePrint(ListNode head) {
        recursive(head); //利用递归把元素倒序都塞入到列表中。
        int[] res = new int[list.size()];
        for(int i = 0; i < res.length; i++) {
            res[i] = list.get(i);
        }
        return res;
    }
    void recursive(ListNode head) {
        if(head == null) {
            return;
        } 
        recursive(head.next);
        list.add(head.val);
    }
}

时间复杂度 O(n)
空间复杂度 O(n)

一道简单题，地址如下：
https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/