当前位置: 首页 > news >正文

【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

题目链接&#xff1a; https://leetcode.cn/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/ 1. 题目介绍&#xff08;06. 从尾到头打印链表&#xff09; 输入一个链表的头节点&#xff0c;从尾到头反过来返回每个节点的值&#xff08;用数组返回&#xff09;。 【测试用例…...

童年回忆--扫雷(包括标记功能和递归展开)--万字讲解让你学会扫雷制作

魔王的介绍&#xff1a;&#x1f636;‍&#x1f32b;️一名双非本科大一小白。魔王的目标&#xff1a;&#x1f92f;努力赶上周围卷王的脚步。魔王的主页&#xff1a;&#x1f525;&#x1f525;&#x1f525;大魔王.&#x1f525;&#x1f525;&#x1f525; ❤️‍&#x1…...

【重器】GPS北斗卫星时钟基准与卫星授时服务技术原理

【重器】GPS北斗卫星时钟基准与卫星授时服务技术原理 【重器】GPS北斗卫星时钟基准与卫星授时服务技术原理 1.前言 由计算机网络系统组成的分布式系统&#xff0c;若想协调一致进行&#xff1a;IT行业的“整点开拍”、“秒杀”、“Leader选举”&#xff0c;通信行业的“同步组网…...

软件测试未来发展趋势怎么样

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

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 由以下部分组成&#xff0c;用于向后端…...

Leetcode力扣秋招刷题路-0068

从0开始的秋招刷题路&#xff0c;记录下所刷每道题的题解&#xff0c;帮助自己回顾总结 68. 文本左右对齐 给定一个单词数组 words 和一个长度 maxWidth &#xff0c;重新排版单词&#xff0c;使其成为每行恰好有 maxWidth 个字符&#xff0c;且左右两端对齐的文本。 你应该…...

Nginx介绍及安装(windows版,Linux版)

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

Camera | 4.瑞芯微平台MIPI摄像头应用程序编写

前面3篇我们讲解了camera的基础概念&#xff0c;MIPI协议&#xff0c;CSI2&#xff0c;常用命令等&#xff0c;本文带领大家入门&#xff0c;如何用c语言编写应用程序来操作摄像头。 Linux下摄像头驱动都是基于v4l2架构&#xff0c;要基于该架构编写摄像头的应用程序&#xff…...

【1250. 检查「好数组」】

来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个正整数数组 nums&#xff0c;你需要从中任选一些子集&#xff0c;然后将子集中每一个数乘以一个 任意整数&#xff0c;并求出他们的和。 假如该和结果为 1&#xff0c;那么原数组就是一个「…...

Spring 如何解决循环依赖?

什么是循环依赖 &#xff1f; 一个或多个对象之间存在直接或间接的依赖关系&#xff0c;这种依赖关系构成一个环形调用&#xff0c;有下面 3 种方式。 我们看一个简单的 Demo&#xff0c;对标“情况 2”。 Service public class Louzai1 {Autowiredprivate Louzai2 louzai2;…...

CocoaPods使用指南

前言 对于大多数软件开发团队来说&#xff0c;依赖管理工具必不可少&#xff0c;它能针对开源和私有依赖进行安装与管理&#xff0c;从而提升开发效率&#xff0c;降低维护成本。针对不同的语言与平台&#xff0c;其依赖管理工具也各有不同&#xff0c;例如 npm 管理 Javascri…...

Kafka 消息队列

目录主流的消息队列消息队列的应用场景缓存/肖锋解耦异步处理KafkaKafka的定义Kafka的底层基础架构Kafka分区如何保证Leader选举Kafka分区如何保证Leader和Follower数据的一致性Kafka 中消费者的消费方式Kafka 高效读写数据的原因&#xff08;高性能吞吐的原因&#xff09;&…...

华为OD机试 - 挑选字符串(Python)| 真题+思路+考点+代码+岗位

挑选字符串 题目 给定a-z,26 个英文字母小写字符串组成的字符串A和B, 其中A可能存在重复字母,B不会存在重复字母, 现从字符串A中按规则挑选一些字母可以组成字符串B 挑选规则如下: 同一个位置的字母只能挑选一次, 被挑选字母的相对先后顺序不能被改变, 求最多可以同时…...

对比Hashtable、HashMap、TreeMap有什么不同?

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

测试新版Android Studio的手机镜像效果

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

女生可以参加IT培训吗?

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

刷题25-重排链表

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

VHDL-延迟模型-惯性延迟与传输延迟

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

2023年美赛(MCM/ICM)简介

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

5min完成linux环境Jenkins的安装

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

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习

禁止商业或二改转载&#xff0c;仅供自学使用&#xff0c;侵权必究&#xff0c;如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

elementUI点击浏览table所选行数据查看文档

项目场景&#xff1a; table按照要求特定的数据变成按钮可以点击 解决方案&#xff1a; <el-table-columnprop"mlname"label"名称"align"center"width"180"><template slot-scope"scope"><el-buttonv-if&qu…...

大数据治理的常见方式

大数据治理的常见方式 大数据治理是确保数据质量、安全性和可用性的系统性方法&#xff0c;以下是几种常见的治理方式&#xff1a; 1. 数据质量管理 核心方法&#xff1a; 数据校验&#xff1a;建立数据校验规则&#xff08;格式、范围、一致性等&#xff09;数据清洗&…...

rm视觉学习1-自瞄部分

首先先感谢中南大学的开源&#xff0c;提供了很全面的思路&#xff0c;减少了很多基础性的开发研究 我看的阅读的是中南大学FYT战队开源视觉代码 链接&#xff1a;https://github.com/CSU-FYT-Vision/FYT2024_vision.git 1.框架&#xff1a; 代码框架结构&#xff1a;readme有…...