学弟学妹们，别瞎学算法了，跟着师兄来看懂这道链表题！

雨点打透心脏的1/2处 2023-01-22 04:52 14阅读 0赞

### 一、题目描述 ###

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

**示例 1：**

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

**限制：**

*  0 <= 链表长度 <= 10000

### 二、题目解析 ###

链表都是从头读到尾依次访问每个节点，题目要求我们 **从尾到头** 打印链表，这种逆序的操作很显然可以考虑使用

具有 **先入后出** 特点的数据结构，那就是 **栈**。

具体操作如下：

*  **入栈：** 遍历链表，将各节点值 `push` 入栈。
 *  **出栈：** 将各个节点值 `pop` 出栈，存储于数组并返回。

### 三、动画描述 ###

[https://www.algomooc.com/146.html][https_www.algomooc.com_146.html]

### 四、图片描述 ###

![面试题06. 从尾到头打印链表.001][06. _.001]

![面试题06. 从尾到头打印链表.002][06. _.002]

![面试题06. 从尾到头打印链表.003][06. _.003]

![面试题06. 从尾到头打印链表.004][06. _.004]

![面试题06. 从尾到头打印链表.005][06. _.005]

![面试题06. 从尾到头打印链表.006][06. _.006]

![面试题06. 从尾到头打印链表.007][06. _.007]

![面试题06. 从尾到头打印链表.008][06. _.008]

![面试题06. 从尾到头打印链表.009][06. _.009]

![面试题06. 从尾到头打印链表.010][06. _.010]

![面试题06. 从尾到头打印链表.011][06. _.011]

![面试题06. 从尾到头打印链表.012][06. _.012]

![面试题06. 从尾到头打印链表.013][06. _.013]

![面试题06. 从尾到头打印链表.014][06. _.014]

![面试题06. 从尾到头打印链表.015][06. _.015]

![面试题06. 从尾到头打印链表.016][06. _.016]

![面试题06. 从尾到头打印链表.017][06. _.017]

![面试题06. 从尾到头打印链表.018][06. _.018]

### 五、视频讲解 ###

[https://www.algomooc.com/146.html][https_www.algomooc.com_146.html]

### 六、参考代码 ###

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

### 七、复杂度分析 ###

#### 时间复杂度 ####

时间复杂度为 O(N)，入栈和出栈共使用 O(N) 时间

#### 空间复杂度 ####

空间复杂度为 O(N)，辅助栈 `stack` 和数组 `res` 共使用 O(N) 的额外空间。

### 八、相关标签 ###

*  链表
 *  栈

### 九、总结 ###

[跟着师兄一起刷题][Link 1]

[https_www.algomooc.com_146.html]: https://www.algomooc.com/146.html
[06. _.001]: /images/20221020/101b5ecfff984f8db282cc4895537da1.png
[06. _.002]: /images/20221020/b93c7f1837764bd9a3f5ede156002dc8.png
[06. _.003]: /images/20221020/065094fd8ab44dcda698d85d5bdc213d.png
[06. _.004]: /images/20221020/a6b8b9a020384e4fa98f92ba2002da5a.png
[06. _.005]: /images/20221020/479f0adf5383451f9e0ee132bd837b91.png
[06. _.006]: /images/20221020/47e164081c5047a5bb20795073087fa9.png
[06. _.007]: /images/20221020/ec630d89d8514b26a50b36f0bdee526e.png
[06. _.008]: /images/20221020/70eb25e816be48eabe194ed9dc7a8af2.png
[06. _.009]: /images/20221020/7b3ef81b35034dbfa85453f58cd7b71e.png
[06. _.010]: /images/20221020/ca83c2e741fa43f1806c2a7760243483.png
[06. _.011]: /images/20221020/44b3846d5a9947bea3b7cdbca50f354d.png
[06. _.012]: /images/20221020/1f3c06e336314c5ea004d00010ba9b15.png
[06. _.013]: /images/20221020/6ddfb74012c44a94b1f9ad04aa58ed22.png
[06. _.014]: /images/20221020/d9b46b730ce5407aa19de316f8b7eced.png
[06. _.015]: /images/20221020/8a13a2b2b1884ddfb11dc81a94f404d5.png
[06. _.016]: /images/20221020/3b2afc0ce7064440a659d82bf58bf5f9.png
[06. _.017]: /images/20221020/9a8f3c906c7943479213a0b6f21ff697.png
[06. _.018]: /images/20221020/d3dcccfb6d624425a435e18605d56088.png
[Link 1]: https://mp.weixin.qq.com/s/cc5HYmYqS0_PJHNlqtobHg