刷题之Leetcode206题(超级详细)

206.反转链表

力扣题目链接(opens new window)icon-default.png?t=N7T8https://leetcode.cn/problems/reverse-linked-list/

题意:反转一个单链表。

示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

思路

如果再定义一个新的链表,实现链表元素的反转,其实这是对内存空间的浪费。

其实只需要改变链表的next指针的指向,直接将链表反转 ,而不用重新定义一个新的链表,如图所示:

206_反转链表

之前链表的头节点是元素1, 反转之后头结点就是元素5 ,这里并没有添加或者删除节点,仅仅是改变next指针的方向。

那么接下来看一看是如何反转的呢?

我们拿有示例中的链表来举例,如动画所示:(纠正:动画应该是先移动pre,在移动cur)

首先定义一个cur指针,指向头结点,再定义一个pre指针,初始化为null。

然后就要开始反转了,首先要把 cur->next 节点用tmp指针保存一下,也就是保存一下这个节点。

为什么要保存一下这个节点呢,因为接下来要改变 cur->next 的指向了,将cur->next 指向pre ,此时已经反转了第一个节点了。

接下来,就是循环走如下代码逻辑了,继续移动pre和cur指针。

最后,cur 指针已经指向了null,循环结束,链表也反转完毕了。 此时我们return pre指针就可以了,pre指针就指向了新的头结点。

双指针法

// 双指针
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;// 保存下一个节点
            cur.next = prev;
            prev = cur;
            cur = temp;
        }
        return prev;
    }
}
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

递归法

递归法相对抽象一些,但是其实和双指针法是一样的逻辑,同样是当cur为空的时候循环结束,不断将cur指向pre的过程。

关键是初始化的地方,可能有的同学会不理解, 可以看到双指针法中初始化 cur = head,pre = NULL,在递归法中可以从如下代码看出初始化的逻辑也是一样的,只不过写法变了。

具体可以看代码(已经详细注释),双指针法写出来之后,理解如下递归写法就不难了,代码逻辑都是一样的。

// 递归 
class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }
}
  • 时间复杂度: O(n), 要递归处理链表的每个节点
  • 空间复杂度: O(n), 递归调用了 n 层栈空间

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/543662.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Linux文本编辑器vim使用和分析—2

目录 1.对vim的简单理解: 2.看待vim的视角: 3.命令模式: 3.1vim被打开后默认的模式: 3.2命令模式切换插入模式: 3.3其他模式回到命令模式: 3.4光标定位: 4.插入模式(编辑模式)&#xff1…

赋能未来:AI技术革新中的创业契机

目录 前言 一、行业解决方案 1、行业参考说明 2、操作步骤建议 二、智能产品和服务 1、行业参考说明 2、操作步骤建议 三、教育和培训 1、行业参考说明 2、操作步骤建议 总结 前言 随着人工智能(AI)技术的快速发展,越来越多的创业…

【Java】新手一步一步安装 Java 语言开发环境

文章目录 一、Windows 10 系统 安装 JDK8二、 Mac 系统 安装 JDK8三、IDEA安装 一、Windows 10 系统 安装 JDK8 (1)打开 JDK下载网站,根据系统配置选择版本,这里选择windows 64位的版本,点击下载(这里需要…

音频变速python版

音频变速 如何能在不改变音频其他特点的情况下,只改变语速呢? 有几个python的库可以实现该功能,下面一一介绍。 pydub库 首先,确保安装了pydub和ffmpeg。 下面是一个简单的Python脚本,展示如何改变音频的播放速度&a…

《手把手教你》系列基础篇(八十五)-java+ selenium自动化测试-框架设计基础-TestNG自定义日志-下篇(详解教程)

1.简介 TestNG为日志记录和报告提供的不同选项。现在,宏哥讲解分享如何开始使用它们。首先,我们将编写一个示例程序,在该程序中我们将使用 ITestListener方法进行日志记录。 2.TestNG自定义日志 2.1创建测试用例类 1.按照宏哥前边的方法&…

论文笔记:Teach LLMs to Phish: Stealing Private Information from Language Models

iclr 2024 reviewer 评分 588 1 intro 提出了一种“神经网络钓鱼攻击” 一种新的针对在敏感用户数据上训练或finetune的LLMs的攻击向量攻击者将看似无害的投毒数据插入到模型的训练数据集中,以“教会LLMs进行钓鱼”,即诱导模型记住他人的个人身份信息&…

DAY9|28. 实现 strStr()、459.重复的子字符串

28.实现 strStr()、459重复的子字符串 28. 实现 strStr()减一版next数组时间复杂度分析前缀表统一减一 C代码实现前缀表(不减一)C实现 459.重复的子字符串移动匹配KMP前缀表统一减一前缀表(不减一)的C代码实…

从零自制docker-10-【cgroup进行容器资源限制】

文章目录 目的导入包的相关公开原则当前进程的挂载信息deferfor scanner.Scan()判断字符串包含新建的cgroup的默认文件cpu相关配置对应到ubuntu 22.04版本的cpu相关配置top注意查看你可使用的cpu注意坑启动后的top查看显示进程使用的cpu序号代码结果 目的 启动容器时通过-mem、…

Day23_学点儿JSON_定义、数据格式、和XML比较、插件

1 JSON定义 定义&#xff1a;是一种轻量级的数据交换格式 JSON是JavaScript Object Notation缩写 特点&#xff1a; 易于程序员阅读和编写。易于计算机解析和生成。其实是javascript的子集&#xff1a;原生javascript支持JSON <script type"text/javascript">…

带头节点单向非循环链表的基本操作(c语言实现)

头节点 头节点是数据结构中的一个概念&#xff0c;特别是在链表结构中。 它通常被设置为链表的第一个节点之前的一个节点&#xff0c;其数据域一般不存储链表中的实际数据&#xff0c;而它的指针域则存储指向链表中第一个实际节点的指针。 头节点的主要作用如下&#xff1a;…

Pandas相比Excel的优势是哪些?

熟悉Pandas的同学会知道&#xff0c;Pandas相当于Python中的Excel&#xff0c;都是基于二维表的进行数据处理分析&#xff0c;不同的是&#xff0c;Pandas基于代码操作数据&#xff0c;Excel是图形化的分析工具。 不少人会问Excel比Pandas更简单&#xff0c;为什么还要学习Pan…

【NLP】大语言模型基础之Transformer结构

大语言模型基础之Transformer结构 1. Transformer结构总览2. 嵌入表示层2. 注意力层3. 前馈层4. 残差连接与层归一化5. 编码器和解码器结构参考文献 Transformer是一种深度学习模型架构&#xff0c;由Vaswani等人于2017年在论文《Attention is All You Need》中首次提出。它在自…

消除 BEV 空间中的跨模态冲突,实现 LiDAR 相机 3D 目标检测

Eliminating Cross-modal Conflicts in BEV Space for LiDAR-Camera 3D Object Detection 消除 BEV 空间中的跨模态冲突&#xff0c;实现 LiDAR 相机 3D 目标检测 摘要Introduction本文方法Single-Modal BEV Feature ExtractionSemantic-guided Flow-based AlignmentDissolved…

vue控制台报错Duplicate keys detected: ‘xxxxx‘. This may cause an update error.解决方案

截图报错&#xff1a; 错误分析&#xff1a; 1、提示 Duplicate keys detected &#xff0c;翻译为&#xff1a;检测到重复的密钥 2、检查 v-for 代码&#xff0c;具体如下&#xff1a; 发现问题&#xff1a;v-for中的key是一个相同的值 解决问题 因此处使用的是测试数据&…

【示例】MySQL-4类SQL语言-DDL-DML-DQL-DCL

前言 本文主要讲述MySQL中4中SQL语言的使用及各自特点。 SQL语言总共分四类&#xff1a;DDL、DML、DQL、DCL。 SQL-DDL | Data Definition Language 数据定义语言&#xff1a;用来定义/更改数据库对象&#xff08;数据库、表、字段&#xff09; 用途 | 操作数据库 # 查询所…

MATLAB 计算点投影到平面上的坐标(59)

MATLAB 计算点投影到平面上的坐标(59) 一、算法介绍二、算法实现1.代码2.结果一、算法介绍 点投影到平面,计算投影点的坐标,下面提供MATLAB版本的计算程序,直接运行即可,内有验证数据,具体看代码即可。 二、算法实现 1.代码 代码如下(示例): % 平面上的三个点分…

力扣--图论/Prim1584.连接所有点的最小费用

思路分析&#xff1a; 初始化&#xff1a;获取点的数量&#xff0c;并创建两个辅助数组 adjvex 和 lowcost&#xff0c;分别用于记录最小生成树的边信息和每个顶点到最小生成树的距离。Prim算法循环&#xff1a;在每一次循环中&#xff0c;选择一个未加入最小生成树的顶点 k&a…

登陆qq,经常收到qq游戏中心的推送信息,关闭推送信息

手动关闭推送信息的步骤&#xff1a; 1.点开左侧游戏中心 2、在打开界面&#xff0c;点击左下角自己的头像 3、打开设置中心&#xff0c;关闭所有的推送 4、完成关闭&#xff0c;不会推送了

使用 Prometheus 在 KubeSphere 上监控 KubeEdge 边缘节点(Jetson) CPU、GPU 状态

作者&#xff1a;朱亚光&#xff0c;之江实验室工程师&#xff0c;云原生/开源爱好者。 KubeSphere 边缘节点的可观测性 在边缘计算场景下&#xff0c;KubeSphere 基于 KubeEdge 实现应用与工作负载在云端与边缘节点的统一分发与管理&#xff0c;解决在海量边、端设备上完成应…

基于SSM+Jsp+Mysql的旅游网站设计与实现

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…