剑指 offer 面试题精选图解 06 . 从尾到头打印链表

in 剑指Offer with 0 comment

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 06 . 从尾到头打印链表

题目链接:https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/

一、题目描述

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

示例 1:

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

限制:

二、题目解析

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

具有 先入后出 特点的数据结构,那就是

具体操作如下:

三、动画描述

四、图片描述

面试题06. 从尾到头打印链表.001

面试题06. 从尾到头打印链表.002

面试题06. 从尾到头打印链表.003

面试题06. 从尾到头打印链表.004

面试题06. 从尾到头打印链表.005

面试题06. 从尾到头打印链表.006

面试题06. 从尾到头打印链表.007

面试题06. 从尾到头打印链表.008

面试题06. 从尾到头打印链表.009

面试题06. 从尾到头打印链表.010

面试题06. 从尾到头打印链表.011

面试题06. 从尾到头打印链表.012

面试题06. 从尾到头打印链表.013

面试题06. 从尾到头打印链表.014

面试题06. 从尾到头打印链表.015

面试题06. 从尾到头打印链表.016

面试题06. 从尾到头打印链表.017

面试题06. 从尾到头打印链表.018

五、参考代码

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) 的额外空间。

七、相关标签