当前位置: 首页 > 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经过以下操作&#…...

Java 语言特性(面试系列2)

一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 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&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

在鸿蒙HarmonyOS 5中实现抖音风格的点赞功能

下面我将详细介绍如何使用HarmonyOS SDK在HarmonyOS 5中实现类似抖音的点赞功能&#xff0c;包括动画效果、数据同步和交互优化。 1. 基础点赞功能实现 1.1 创建数据模型 // VideoModel.ets export class VideoModel {id: string "";title: string ""…...

Java入门学习详细版(一)

大家好&#xff0c;Java 学习是一个系统学习的过程&#xff0c;核心原则就是“理论 实践 坚持”&#xff0c;并且需循序渐进&#xff0c;不可过于着急&#xff0c;本篇文章推出的这份详细入门学习资料将带大家从零基础开始&#xff0c;逐步掌握 Java 的核心概念和编程技能。 …...

什么是Ansible Jinja2

理解 Ansible Jinja2 模板 Ansible 是一款功能强大的开源自动化工具&#xff0c;可让您无缝地管理和配置系统。Ansible 的一大亮点是它使用 Jinja2 模板&#xff0c;允许您根据变量数据动态生成文件、配置设置和脚本。本文将向您介绍 Ansible 中的 Jinja2 模板&#xff0c;并通…...

Python ROS2【机器人中间件框架】 简介

销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

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

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐&#xff1a;「storms…...

论文阅读笔记——Muffin: Testing Deep Learning Libraries via Neural Architecture Fuzzing

Muffin 论文 现有方法 CRADLE 和 LEMON&#xff0c;依赖模型推理阶段输出进行差分测试&#xff0c;但在训练阶段是不可行的&#xff0c;因为训练阶段直到最后才有固定输出&#xff0c;中间过程是不断变化的。API 库覆盖低&#xff0c;因为各个 API 都是在各种具体场景下使用。…...