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

LeetCode 92. Reverse Linked List II【链表,头插法】中等

本文属于「征服LeetCode」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章中,我不仅会讲解多种解题思路及其优化,还会用多种编程语言实现题解,涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件,我还建立了相关的仓库:https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中,你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等,还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解,还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动,欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

示例 1:

输入:head = [1,2,3,4,5], left = 2, right = 4
输出:[1,4,3,2,5]

示例 2:

输入:head = [5], left = 1, right = 1
输出:[5]

提示:

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500
  • 1 <= left <= right <= n

进阶: 你可以使用一趟扫描完成反转吗?


解法 一次遍历「穿针引线」反转链表


下面具体解释如何实现。使用指针变量来记录反转的过程中需要的变量,它们的意义如下:

  • curr :指向待反转区域的第一个节点
  • next永远指向 curr 的下一个节点,循环过程中,curr 变化以后 next 会变化;
  • p0 :永远指向待反转区域的第一个节点 left 的前一个节点,在循环过程中不变
  • prev :永远指向已反转区域的上个节点,紧邻在 curr 左侧。

操作步骤:

  1. 找到 p0 ,令 prev = nullptr, curr = p0->next
  2. 进入循环:
    1. 先将 curr 的下一个节点记录为 next
    2. 执行操作 ①:把 curr.next 指向上一个节点 prev
    3. 执行操作 ②:把 prev 指向当前节点 curr
    4. 执行操作 ③:把 curr 移动到下个节点 next
  3. 超出待反转区域后,p0->next 指向已反转区域的尾部,设置 p0->next->nextcurr ,再设置 p0->nextprev
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {// 设置 dummy 是此类问题的一般做法ListNode* dummy = new ListNode(0, head), *p0 = dummy;for (int i = 0; i < left - 1; ++i) p0 = p0->next;ListNode *prev = nullptr, *curr = p0->next;for (int i = 0; i < right - left + 1; ++i) {ListNode *next = curr->next;curr->next = prev;prev = curr;curr = next;}p0->next->next = curr;p0->next = prev;return dummy->next;}
};

复杂度分析:

  • 时间复杂度: O ( n ) \mathcal{O}(n) O(n) ,其中 n n n 为链表节点个数。
  • 空间复杂度: O ( 1 ) \mathcal{O}(1) O(1) ,仅用到若干额外变量。

相关文章:

LeetCode 92. Reverse Linked List II【链表,头插法】中等

本文属于「征服LeetCode」系列文章之一&#xff0c;这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁&#xff0c;本系列将至少持续到刷完所有无锁题之日为止&#xff1b;由于LeetCode还在不断地创建新题&#xff0c;本系列的终止日期可能是永远。在这一系列刷题文章…...

【图论】Floyd

算法提高课笔记&#xff09; 文章目录 例题牛的旅行题意思路代码 排序题意思路代码 观光之旅题意思路代码 例题 牛的旅行 原题链接 农民John的农场里有很多牧区&#xff0c;有的路径连接一些特定的牧区。 一片所有连通的牧区称为一个牧场。 但是就目前而言&#xff0c;你…...

SpringCloudAlibaba Gateway(三)-整合Sentinel功能路由维度、API维度进行流控

Gateway整合Sentinel ​ 前面使用过Sentinel组件对服务提供者、服务消费者进行流控、限流等操作。除此之外&#xff0c;Sentinel还支持对Gateway、Zuul等主流网关进行限流。 ​ 自sentinel1.6.0版开始&#xff0c;Sentinel提供了Gateway的适配模块&#xff0c;能针对路由(rou…...

【笔试强训选择题】Day38.习题(错题)解析

作者简介&#xff1a;大家好&#xff0c;我是未央&#xff1b; 博客首页&#xff1a;未央.303 系列专栏&#xff1a;笔试强训选择题 每日一句&#xff1a;人的一生&#xff0c;可以有所作为的时机只有一次&#xff0c;那就是现在&#xff01;&#xff01; 文章目录 前言一、Day…...

DAY08_MyBatisPlus——入门案例标准数据层开发CRUD-Lombok-分页功能DQL编程控制DML编程控制乐观锁快速开发-代码生成器

目录 一 MyBatisPlus简介1. 入门案例问题导入1.1 SpringBoot整合MyBatisPlus入门程序①&#xff1a;创建新模块&#xff0c;选择Spring初始化&#xff0c;并配置模块相关基础信息②&#xff1a;选择当前模块需要使用的技术集&#xff08;仅保留JDBC&#xff09;③&#xff1a;手…...

分光棱镜BS、PB、NPBS的区别

BS&#xff08;分光棱镜&#xff09;&#xff1a;对入射偏振敏感&#xff0c;线偏振角度会影响分光比。若入射的是自然光或圆偏振光&#xff0c;则按50&#xff1a;50分光。分束的时候只管分能量&#xff0c;理想器件下出射的两路光偏振态还是原来的样子&#xff0c;实际工艺缺…...

人工智能论文通用创新点(一)——ACMIX 卷积与注意力融合、GCnet(全局特征融合)、Coordinate_attention、SPD(可替换下采样)

1.ACMIX 卷积与注意力融合 论文地址:https://arxiv.org/pdf/2111.14556.pdf 为了实现卷积与注意力的融合,我们让特征图经过两个路径,一个路径经过卷积,另外一个路径经过Transformer,但是,现在有一个问题,卷积路径比较快,Transformer比较慢。因此,我们让Q,K,V通过1*1的…...

您的计算机已被[new_day@torguard.tg].faust 勒索病毒感染?恢复您的数据的方法在这里!

导言&#xff1a; 随着科技的迅速发展&#xff0c;网络空间也变得越来越危险&#xff0c;而勒索病毒则是网络威胁中的一个严重问题。 [ new_daytorguard.tg ].faust 勒索病毒是最新的威胁之一&#xff0c;采用高度复杂的加密技术&#xff0c;将受害者的数据文件锁定&#xff0c…...

18--Elasticsearch

一 Elasticsearch介绍 1 全文检索 Elasticsearch是一个全文检索服务器 全文检索是一种非结构化数据的搜索方式 结构化数据&#xff1a;指具有固定格式固定长度的数据&#xff0c;如数据库中的字段。 非结构化数据&#xff1a;指格式和长度不固定的数据&#xff0c;如电商网站…...

代码随想录算法训练营 day59|503.下一个更大元素II、42. 接雨水

一、503.下一个更大元素II 力扣题目链接 可以不扩充nums&#xff0c;在遍历的过程中模拟走两边nums class Solution { public:vector<int> nextGreaterElements(vector<int>& nums) {vector<int> result(nums.size(), -1);if (nums.size() 0) return…...

MyBatis数据库操作

文章目录 前言一、MyBatis的各种查询功能1.查询一个实体类对象2.查询一个List集合3.查询单个数据4.查询一条数据为map集合5.查询多条数据为map集合方法一方法二 6.测试类 二、特殊SQL的执行1.模糊查询2.批量删除3.动态设置表名5.添加功能获取自增的主键6.测试类 三、自定义映射…...

python flask框架 debug功能

从今天开始&#xff0c;准备整理一些基础知识&#xff0c;分享给需要的人吧 先整理个flask的debug功能&#xff0c;首先列举一下debug加与不加的区别&#xff0c;然后再上代码和图看看差异 区别&#xff1a; &#xff08;1&#xff09;加了debug后&#xff0c;修改js&#xf…...

《深入浅出OCR》第六章:OCR数据集与评价指标

一、OCR技术流程 在介绍OCR数据集开始&#xff0c;我将带领大家和回顾下OCR技术流程&#xff0c;典型的OCR技术pipline如下图所示&#xff0c;其中&#xff0c;文本检测和识别是OCR技术的两个重要核心技术。 1.1 图像预处理&#xff1a; 图像预处理是OCR流程的第一步&#xf…...

15. 线性代数 - 克拉默法则

文章目录 克拉默法则矩阵运算Hi,大家好。我是茶桁。 上节课我们在最后提到了一个概念「克拉默法则」,本节课,我们就来看看到底什么是克拉默法则。 克拉默法则 之前的课程我们一直在强调,矩阵是线性方程组抽象的来的。那么既然我们抽象出来了,有没有一种比较好的办法高效…...

【LeetCode】剑指 Offer <二刷>(6)

目录 题目&#xff1a;剑指 Offer 12. 矩阵中的路径 - 力扣&#xff08;LeetCode&#xff09; 题目的接口&#xff1a; 解题思路&#xff1a; 代码&#xff1a; 过啦&#xff01;&#xff01;&#xff01; 题目&#xff1a;剑指 Offer 13. 机器人的运动范围 - 力扣&#…...

jsp页面出现“String cannot be resolved to a type”错误解决办法

篇首语&#xff1a;小编为大家整理&#xff0c;主要介绍了jsp页面出现“String cannot be resolved to a type”错误解决办法相关的知识&#xff0c;希望对你有一定的参考价值。 jsp页面出现“String cannot be resolved to a type”错误解决办法 解决办法&#xff1a; 右键项目…...

【go-zero】使用自带Redis方法

yaml配置文件 RedisS:Host: Type: Pass: config增加 RedisS struct {Host stringType stringPass string}svc文件 type * struct {RedisClient *redis.Redis } func *(c config.Config) * {sqlConn : sqlx.NewMysql(c.DB.DataSource)return &*{RedisClient: redis.New(c…...

离线数仓同步数据3

业务数据_增量表数据同步 1&#xff09;Flume配置概述2&#xff09;Flume配置实操3&#xff09;通道测试4&#xff09;编写Flume启停脚本 1&#xff09;Flume配置概述 Flume需要将Kafka中topic_db主题的数据传输到HDFS&#xff0c;故其需选用KafkaSource以及HDFSSink&#xff…...

Prometheus+Grafana 搭建应用监控系统

一、背景 完善的监控系统可以提高应用的可用性和可靠性&#xff0c;在提供更优质服务的前提下&#xff0c;降低运维的投入和工作量&#xff0c;为用户带来更多的商业利益和客户体验。下面就带大家彻底搞懂监控系统&#xff0c;使用Prometheus Grafana搭建完整的应用监控系统。 …...

Spring Boot整合Log4j2.xml的问题

文章目录 问题解决参考 问题 Spring Boot整合Log4j2.xml的时候返回以下错误&#xff1a; Caused by: org.apache.logging.log4j.LoggingException: log4j-slf4j-impl cannot be present with log4j-to-slf4j 进行了解决。 解决 Spring Boot整合Log4j2.xml经过以下操作&#…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

pam_env.so模块配置解析

在PAM&#xff08;Pluggable Authentication Modules&#xff09;配置中&#xff0c; /etc/pam.d/su 文件相关配置含义如下&#xff1a; 配置解析 auth required pam_env.so1. 字段分解 字段值说明模块类型auth认证类模块&#xff0c;负责验证用户身份&am…...

HTML 列表、表格、表单

1 列表标签 作用&#xff1a;布局内容排列整齐的区域 列表分类&#xff1a;无序列表、有序列表、定义列表。 例如&#xff1a; 1.1 无序列表 标签&#xff1a;ul 嵌套 li&#xff0c;ul是无序列表&#xff0c;li是列表条目。 注意事项&#xff1a; ul 标签里面只能包裹 li…...

服务器硬防的应用场景都有哪些?

服务器硬防是指一种通过硬件设备层面的安全措施来防御服务器系统受到网络攻击的方式&#xff0c;避免服务器受到各种恶意攻击和网络威胁&#xff0c;那么&#xff0c;服务器硬防通常都会应用在哪些场景当中呢&#xff1f; 硬防服务器中一般会配备入侵检测系统和预防系统&#x…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

今日科技热点速览

&#x1f525; 今日科技热点速览 &#x1f3ae; 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售&#xff0c;主打更强图形性能与沉浸式体验&#xff0c;支持多模态交互&#xff0c;受到全球玩家热捧 。 &#x1f916; 人工智能持续突破 DeepSeek-R1&…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

C++.OpenGL (20/64)混合(Blending)

混合(Blending) 透明效果核心原理 #mermaid-svg-SWG0UzVfJms7Sm3e {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-icon{fill:#552222;}#mermaid-svg-SWG0UzVfJms7Sm3e .error-text{fill…...