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
左侧。
操作步骤:
- 找到
p0
,令prev = nullptr, curr = p0->next
。 - 进入循环:
- 先将
curr
的下一个节点记录为next
; - 执行操作 ①:把
curr.next
指向上一个节点prev
; - 执行操作 ②:把
prev
指向当前节点curr
; - 执行操作 ③:把
curr
移动到下个节点next
。
- 先将
- 超出待反转区域后,
p0->next
指向已反转区域的尾部,设置p0->next->next
为curr
,再设置p0->next
为prev
。
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」系列文章之一,这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁,本系列将至少持续到刷完所有无锁题之日为止;由于LeetCode还在不断地创建新题,本系列的终止日期可能是永远。在这一系列刷题文章…...

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

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

【笔试强训选择题】Day38.习题(错题)解析
作者简介:大家好,我是未央; 博客首页:未央.303 系列专栏:笔试强训选择题 每日一句:人的一生,可以有所作为的时机只有一次,那就是现在!! 文章目录 前言一、Day…...

DAY08_MyBatisPlus——入门案例标准数据层开发CRUD-Lombok-分页功能DQL编程控制DML编程控制乐观锁快速开发-代码生成器
目录 一 MyBatisPlus简介1. 入门案例问题导入1.1 SpringBoot整合MyBatisPlus入门程序①:创建新模块,选择Spring初始化,并配置模块相关基础信息②:选择当前模块需要使用的技术集(仅保留JDBC)③:手…...
分光棱镜BS、PB、NPBS的区别
BS(分光棱镜):对入射偏振敏感,线偏振角度会影响分光比。若入射的是自然光或圆偏振光,则按50:50分光。分束的时候只管分能量,理想器件下出射的两路光偏振态还是原来的样子,实际工艺缺…...

人工智能论文通用创新点(一)——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 勒索病毒感染?恢复您的数据的方法在这里!
导言: 随着科技的迅速发展,网络空间也变得越来越危险,而勒索病毒则是网络威胁中的一个严重问题。 [ new_daytorguard.tg ].faust 勒索病毒是最新的威胁之一,采用高度复杂的加密技术,将受害者的数据文件锁定,…...

18--Elasticsearch
一 Elasticsearch介绍 1 全文检索 Elasticsearch是一个全文检索服务器 全文检索是一种非结构化数据的搜索方式 结构化数据:指具有固定格式固定长度的数据,如数据库中的字段。 非结构化数据:指格式和长度不固定的数据,如电商网站…...
代码随想录算法训练营 day59|503.下一个更大元素II、42. 接雨水
一、503.下一个更大元素II 力扣题目链接 可以不扩充nums,在遍历的过程中模拟走两边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功能
从今天开始,准备整理一些基础知识,分享给需要的人吧 先整理个flask的debug功能,首先列举一下debug加与不加的区别,然后再上代码和图看看差异 区别: (1)加了debug后,修改js…...

《深入浅出OCR》第六章:OCR数据集与评价指标
一、OCR技术流程 在介绍OCR数据集开始,我将带领大家和回顾下OCR技术流程,典型的OCR技术pipline如下图所示,其中,文本检测和识别是OCR技术的两个重要核心技术。 1.1 图像预处理: 图像预处理是OCR流程的第一步…...

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

【LeetCode】剑指 Offer <二刷>(6)
目录 题目:剑指 Offer 12. 矩阵中的路径 - 力扣(LeetCode) 题目的接口: 解题思路: 代码: 过啦!!! 题目:剑指 Offer 13. 机器人的运动范围 - 力扣&#…...

jsp页面出现“String cannot be resolved to a type”错误解决办法
篇首语:小编为大家整理,主要介绍了jsp页面出现“String cannot be resolved to a type”错误解决办法相关的知识,希望对你有一定的参考价值。 jsp页面出现“String cannot be resolved to a type”错误解决办法 解决办法: 右键项目…...
【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)Flume配置概述2)Flume配置实操3)通道测试4)编写Flume启停脚本 1)Flume配置概述 Flume需要将Kafka中topic_db主题的数据传输到HDFS,故其需选用KafkaSource以及HDFSSinkÿ…...

Prometheus+Grafana 搭建应用监控系统
一、背景 完善的监控系统可以提高应用的可用性和可靠性,在提供更优质服务的前提下,降低运维的投入和工作量,为用户带来更多的商业利益和客户体验。下面就带大家彻底搞懂监控系统,使用Prometheus Grafana搭建完整的应用监控系统。 …...
Spring Boot整合Log4j2.xml的问题
文章目录 问题解决参考 问题 Spring Boot整合Log4j2.xml的时候返回以下错误: Caused by: org.apache.logging.log4j.LoggingException: log4j-slf4j-impl cannot be present with log4j-to-slf4j 进行了解决。 解决 Spring Boot整合Log4j2.xml经过以下操作&#…...
Java 语言特性(面试系列2)
一、SQL 基础 1. 复杂查询 (1)连接查询(JOIN) 内连接(INNER JOIN):返回两表匹配的记录。 SELECT e.name, d.dept_name FROM employees e INNER JOIN departments d ON e.dept_id d.dept_id; 左…...
rknn优化教程(二)
文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK,开始写第二篇的内容了。这篇博客主要能写一下: 如何给一些三方库按照xmake方式进行封装,供调用如何按…...
在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能
下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能,包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...
Java入门学习详细版(一)
大家好,Java 学习是一个系统学习的过程,核心原则就是“理论 实践 坚持”,并且需循序渐进,不可过于着急,本篇文章推出的这份详细入门学习资料将带大家从零基础开始,逐步掌握 Java 的核心概念和编程技能。 …...

什么是Ansible Jinja2
理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具,可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板,允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板,并通…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf
FTP 客服管理系统 实现kefu123登录,不允许匿名访问,kefu只能访问/data/kefu目录,不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化
缓存架构 代码结构 代码详情 功能点: 多级缓存,先查本地缓存,再查Redis,最后才查数据库热点数据重建逻辑使用分布式锁,二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing
Muffin 论文 现有方法 CRADLE 和 LEMON,依赖模型推理阶段输出进行差分测试,但在训练阶段是不可行的,因为训练阶段直到最后才有固定输出,中间过程是不断变化的。API 库覆盖低,因为各个 API 都是在各种具体场景下使用。…...