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

1. 题目

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

2. 描述

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

示例 1：

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

输出： [2,3,1]

限制：

0 <= 链表长度 <= 10000

3. 实现方法

3.1 方法 1

3.1.1 思路

借助栈的特点，先进后出，我们只需要将链表的元素存入栈中，然后从栈中取出元素，此时取出的顺序就是按照链表元素存入的反序；

此时将栈中取出的元素存入列表中返回即可；

主要进行取出链表元素并入栈，此时时间复杂度为 O ( n ) O(n)O(n)，n nn 为链表元素个数；

然后进行出栈并存入操作，此时时间复杂度为 O ( n ) O(n)O(n);

最终的时间复杂度为 O ( n ) + O ( n ) = 2 O ( n ) O(n) + O(n) = 2O(n)O(n)+O(n)=2O(n)，即 O ( n ) O(n)O(n)；

3.1.2 实现

public int[] reversePrint(ListNode head) {
    // 利用栈来存储链表元素，由于是先进后出的数据结构，所以从头到尾存储链表元素，最后出栈时即为从尾到头打印链表元素
    Stack<Integer> stack = new Stack<>();
    // 入栈
    while (head != null) {
        stack.push(head.val);
        head = head.next;
    }
    int[] ans = new int[stack.size()];
    // 出栈并存储到数组中
    for (int i = 0; i < ans.length; i++) {
        ans[i] = stack.pop();
    }
    return ans;
}