【LeetCode】剑指 Offer 06. 从尾到头打印链表 p58 -- Java Version
题目链接: https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/
1. 题目介绍(06. 从尾到头打印链表)
输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。
【测试用例】:
示例 1:
输入:head = [1,3,2]
输出:[2,3,1]
【条件约束】:
0 <= 链表长度 <= 10000
2. 题解
2.1 辅助栈(后进先出)-- O(n)
时间复杂度:O(n),空间复杂度:O(n)
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public int[] reversePrint(ListNode head) {// 1. 创建一个栈用来从前向后存储链表Stack<ListNode> stack = new Stack<>();// 2. 创建一个ListNode对象,指向head节点ListNode node = head;// 3. 将链表节点依次压栈while (node != null){stack.push(node);// System.out.println(node.val);node = node.next;}// 4. 创建一个int数组,记录从后向前弹出的链表节点值int[] arr = new int[stack.size()];// 5. 弹出并将栈内数据存入数组for (int i = 0; i < arr.length; i++){arr[i] = stack.pop().val;}// 6. 循环结束,返回数组return arr;}
}
2.2 递归 – O(n)
时间复杂度:O(n),空间复杂度:O(n)
代码来自于StackOverflow~在面试题06. 从尾到头打印链表中的Comment.
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {// 1. 定义数组,用于后续的返回int[] res;public int[] reversePrint(ListNode head) {// 2. 递归调用backtrack(head,0);// 6. 返回最终结果return res;}public int backtrack(ListNode node, int length){// 3. 如果当前节点为null,说明走到了最后,创建数组if(node==null){res = new int[length];return 0;}int index = backtrack(node.next,length+1);// 4. 递归到最深层后,依次返回并赋值res[index] = node.val;// 5. 返回索引+1,用于移动当前数组下标return index+1;}
}
2.3 两次暴力遍历 – O(n)
时间复杂度:O(n),空间复杂度:O(n)
代码参考于 TJ. xiong 的 剑指 Offer 06. 从尾到头打印链表.
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/
class Solution {public int[] reversePrint(ListNode head) {// 1. 创建一个ArrayList集合ArrayList<Integer> integers = new ArrayList<>();// 2. 循环遍历,将链表节点值加入集合while (head != null) {integers.add(head.val);head = head.next;}// 3. 创建一个数组int[] ints = new int[integers.size()];// 4. 循环遍历,将ArrayList中的数据倒序存入int数组中for (int i = 0; i < ints.length; i++) {ints [i] = integers.get(ints.length - 1 - i);}// 5. 循环结束,返回数组return ints;}
}
3. 思考
虽然三种方法的时间复杂度和空间复杂度都是O(n),但是还是比较推荐使用栈(Stack)
来实现。使用递归会存在一个问题,那就是:当链表非常长的时候,就会导致函数调用的层级很深,从而有可能导致函数调用栈溢出。
4. 参考资料
[1] Java Stack 类
[2] 面试题06. 从尾到头打印链表
[3] 剑指 Offer 06. 从尾到头打印链表
相关文章:

【LeetCode】剑指 Offer 06. 从尾到头打印链表 p58 -- Java Version
题目链接: https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/ 1. 题目介绍(06. 从尾到头打印链表) 输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。 【测试用例…...

童年回忆--扫雷(包括标记功能和递归展开)--万字讲解让你学会扫雷制作
魔王的介绍:😶🌫️一名双非本科大一小白。魔王的目标:🤯努力赶上周围卷王的脚步。魔王的主页:🔥🔥🔥大魔王.🔥🔥🔥 ❤️…...
【重器】GPS北斗卫星时钟基准与卫星授时服务技术原理
【重器】GPS北斗卫星时钟基准与卫星授时服务技术原理 【重器】GPS北斗卫星时钟基准与卫星授时服务技术原理 1.前言 由计算机网络系统组成的分布式系统,若想协调一致进行:IT行业的“整点开拍”、“秒杀”、“Leader选举”,通信行业的“同步组网…...

软件测试未来发展趋势怎么样
未来,互联网技术是很多企业能够活下去的关键点。互联网技术成为新的基建,互联网“基建”化就决定了软件测试行业的缺口会一直扩大。 并且,软件测试岗位,已不仅局限于互联网企业,现已逐步深入到实体产业,金…...

aws Distro for OpenTelemetry 可观测性workshop记录
参考资料 https://aws-otel.github.io/docs/introductionhttps://aws-otel.github.io/docs/introduction aws distro for opentelemetry 官方提供了不同语言不同使用场景下完善的使用实例和相关配置。 AWS Distro for OpenTelemetrics 由以下部分组成,用于向后端…...
Leetcode力扣秋招刷题路-0068
从0开始的秋招刷题路,记录下所刷每道题的题解,帮助自己回顾总结 68. 文本左右对齐 给定一个单词数组 words 和一个长度 maxWidth ,重新排版单词,使其成为每行恰好有 maxWidth 个字符,且左右两端对齐的文本。 你应该…...

Nginx介绍及安装(windows版,Linux版)
目录 一、Nginx介绍 1、Nginx优势 2、Nginx作用 3、部署静态资源 4、代理 5、负载均衡 二、Nginx安装步骤(windows版) 三、Nginx安装步骤(Linux版) 1、官网下载安装包,下载完之后上传到Linux系统上 2、在Lin…...

Camera | 4.瑞芯微平台MIPI摄像头应用程序编写
前面3篇我们讲解了camera的基础概念,MIPI协议,CSI2,常用命令等,本文带领大家入门,如何用c语言编写应用程序来操作摄像头。 Linux下摄像头驱动都是基于v4l2架构,要基于该架构编写摄像头的应用程序ÿ…...
【1250. 检查「好数组」】
来源:力扣(LeetCode) 描述: 给你一个正整数数组 nums,你需要从中任选一些子集,然后将子集中每一个数乘以一个 任意整数,并求出他们的和。 假如该和结果为 1,那么原数组就是一个「…...

Spring 如何解决循环依赖?
什么是循环依赖 ? 一个或多个对象之间存在直接或间接的依赖关系,这种依赖关系构成一个环形调用,有下面 3 种方式。 我们看一个简单的 Demo,对标“情况 2”。 Service public class Louzai1 {Autowiredprivate Louzai2 louzai2;…...
CocoaPods使用指南
前言 对于大多数软件开发团队来说,依赖管理工具必不可少,它能针对开源和私有依赖进行安装与管理,从而提升开发效率,降低维护成本。针对不同的语言与平台,其依赖管理工具也各有不同,例如 npm 管理 Javascri…...

Kafka 消息队列
目录主流的消息队列消息队列的应用场景缓存/肖锋解耦异步处理KafkaKafka的定义Kafka的底层基础架构Kafka分区如何保证Leader选举Kafka分区如何保证Leader和Follower数据的一致性Kafka 中消费者的消费方式Kafka 高效读写数据的原因(高性能吞吐的原因)&…...
华为OD机试 - 挑选字符串(Python)| 真题+思路+考点+代码+岗位
挑选字符串 题目 给定a-z,26 个英文字母小写字符串组成的字符串A和B, 其中A可能存在重复字母,B不会存在重复字母, 现从字符串A中按规则挑选一些字母可以组成字符串B 挑选规则如下: 同一个位置的字母只能挑选一次, 被挑选字母的相对先后顺序不能被改变, 求最多可以同时…...

对比Hashtable、HashMap、TreeMap有什么不同?
第9讲 | 对比Hashtable、HashMap、TreeMap有什么不同? Map 是广义 Java 集合框架中的另外一部分,HashMap 作为框架中使用频率最高的类型之一,它本身以及相关类型自然也是面试考察的热点。 今天我要问你的问题是,对比 Hashtable、…...

测试新版Android Studio的手机镜像效果
学更好的别人, 做更好的自己。 ——《微卡智享》 本文长度为669字,预计阅读2分钟 前言 春节刚上班,就开始了疯狂出差的节奏,期间发现Android Studio发布新的版本2022.1.1(Electric Eel),里面两个更新的内容蓝牙模拟器和…...

女生可以参加IT培训吗?
2023年了,就不要把性别当作选择专业的前提条件了。虽然这句话说过很多次了,作为IT行业来说,是非常欢迎女生的加入;尤其是整天都是面对一大堆男攻城狮,工作氛围一点都不活跃,反而显得压抑和杂乱,…...

刷题25-重排链表
重排链表 解题思路:通过观察链表可以发现,把链表一分为二,后半段链表反转,然后两个链表穿插连接,当链表的节点总数是奇数时,要保证链表的前半段比后半段多一个节点。 关于把链表一分为二,可以…...

VHDL-延迟模型-惯性延迟与传输延迟
目录 1,惯性延时 2,传输延时 信号通过元件都会有延迟,延迟时间的计算是逻辑仿真的重要功能。考虑延迟信息得到的仿真输出波形可以更精确地反映实际电路的情况。针对元件的延时,人们根据需要建立了一些用的延时模型,这…...

2023年美赛(MCM/ICM)简介
2023年美赛将要如期开赛,这里为了 让大家对今年的美赛有一个直接 客观的了解。对2023年美赛(MCM/ICM)进行一下简要的介绍。相关资料大家可以查看另一篇文章一、竞赛时间February 16-20, 2023开赛时间 北京时间 17号(本周五) 6:00结束时间 北京时间 21号(…...

5min完成linux环境Jenkins的安装
5min搞定linux环境Jenkins的安装安装Jenkinsstep1: 使用wget 命令下载Jenkinsstep2、创建Jenkins日志目录并运行jekinsstep3、访问jenkins并解锁jenkins,安装插件以及创建管理员用户step4、到此,就完成了Finish、以上步骤中遇到的问题1、 jenkins启动不了…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
AtCoder 第409场初级竞赛 A~E题解
A Conflict 【题目链接】 原题链接:A - Conflict 【考点】 枚举 【题目大意】 找到是否有两人都想要的物品。 【解析】 遍历两端字符串,只有在同时为 o 时输出 Yes 并结束程序,否则输出 No。 【难度】 GESP三级 【代码参考】 #i…...

ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...

html-<abbr> 缩写或首字母缩略词
定义与作用 <abbr> 标签用于表示缩写或首字母缩略词,它可以帮助用户更好地理解缩写的含义,尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时,会显示一个提示框。 示例&#x…...

ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题
【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要: 近期,在使用较新版本的OpenSSH客户端连接老旧SSH服务器时,会遇到 "no matching key exchange method found", "n…...