【leetcode热题100】反转链表 II
给你单链表的头指针 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 <= 5001 <= left <= right <= n
解法一
首先找到 m 的位置,记录两端的节点 left1 和 left2 。
然后每遍历一个节点,就倒置一个节点。
到 n 的位置后,利用之前的 left1 和 left2 完成连接。
为了完成链表的倒置需要两个指针 pre 和 head。为了少考虑边界条件,例如 m = 1 的倒置。加一个哨兵节点 dummy。
m = 2, n = 41 2 3 4 5 加入哨兵节点 d,pre 简写 p,head 简写 h0 1 2 3 4 5 往后遍历
^ ^
d h
p0 1 2 3 4 5 此时 h 指向 m 的位置,记录 p 和 h 为 l1 和 l2
^ ^ ^
d p h0 1 2 3 4 5 然后继续遍历
^ ^ ^
d p hl1 l20 1 2 3 4 5 开始倒置链表,使得 h 指向 p
^ ^ ^ ^
d l1 p hl2
当前状态用图形描述

倒转链表,将 h 的 next 指向 p,并且后移 p 和 h。

然后上边一步会重复多次,直到 h 到达 n 的位置。当然这道题比较特殊,上图 h 已经到达了 n 的位置。
此时,我们需要将 h 指向 p,同时将 l1 指向 h,l2 指向 h.next,使得链表接起来。

操作完成,将 dummy.next 返回即可。
public ListNode reverseBetween(ListNode head, int m, int n) {if (m == n) {return head;}ListNode dummy = new ListNode(0);dummy.next = head;int count = 0;ListNode left1 = null;ListNode left2 = null;ListNode pre = dummy;while (head != null) {count++;//到达 m,保存 l1 和 l2if (count == m) {left1 = pre;left2 = head;}// m 和 n 之间,倒转链表if (count > m && count < n) {ListNode temp = head.next;head.next = pre;pre = head;head = temp;continue;}//到达 nif (count == n) {left2.next = head.next;head.next = pre;left1.next = head;break;}//两个指针后移head = head.next;pre = pre.next;}return dummy.next;
}
时间复杂度:O(n)。
空间复杂度:O(1)。
相关文章:
【leetcode热题100】反转链表 II
给你单链表的头指针 head 和两个整数 left 和 right ,其中 left < right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。 示例 1: 输入:head [1,2,3,4,5], left 2, right 4 输出:[1,4,3,2…...
谷歌 DeepMind 联合斯坦福推出了主从式遥操作双臂机器人系统增强版ALOHA 2
谷歌 DeepMind 联合斯坦福推出了 ALOHA 的增强版本 ——ALOHA 2。与一代相比,ALOHA 2 具有更强的性能、人体工程学设计和稳健性,且成本还不到 20 万元人民币。并且,为了加速大规模双手操作的研究,ALOHA 2 相关的所有硬件设计全部开…...
金融行业专题|证券超融合架构转型与场景探索合集(2023版)
更新内容 更新 SmartX 超融合在证券行业的覆盖范围、部署规模与应用场景。新增操作系统信创转型、Nutanix 国产化替代、网络与安全等场景实践。更多超融合金融核心生产业务场景实践,欢迎阅读文末电子书。 在金融行业如火如荼的数字化转型大潮中,传统架…...
【C语言】C的整理记录
前言 该笔记是建立在已经系统学习过C语言的基础上,笔者对C语言的知识和注意事项进行整理记录,便于后期查阅,反复琢磨。C语言是一种面向过程的编程语言。 原想在此阐述一下C语言的作用,然而发觉这些是编程语言所共通的作用&#…...
C/C++模板初阶
目录 1. 泛型编程 2. 函数模板 2.1 函数模板概念 2.1 函数模板格式 2.3 函数模板的原理 2.4 函数模板的实例化 2.5 模板参数的匹配原则 3. 类模板 3.1 类模板的定义格式 3.2 类模板的实例化 1. 泛型编程 如何实现一个通用的交换函数呢? void Swap(int&…...
linux系统下vscode portable版本的c++/Cmake环境搭建001
linux系统下vscode portable版本的Cmake环境搭建 vscode portable 安装安装基本工具安装 build-essential安装 CMake final script code安装插件CMake Tools & cmakeC/C Extension Pack Testsettings,jsonCMakeLists.txt调试和运行工具 CG 目的:希望在获得一个新…...
【QT+QGIS跨平台编译】之三十一:【FreeXL+Qt跨平台编译】(一套代码、一套框架,跨平台编译)
文章目录 一、FreeXL介绍二、文件下载三、文件分析四、pro文件五、编译实践一、FreeXL介绍 【FreeXL跨平台编译】:Windows环境下编译成果(支撑QGIS跨平台编译,以及二次研发) 【FreeXL跨平台编译】:Linux环境下编译成果(支撑QGIS跨平台编译,以及二次研发) 【FreeXL跨平台…...
2024年 前端JavaScript入门到精通 第一天
主要讲解JavaScript核心知识,包含最新ES6语法,从基础到API再到高级。让你一边学习一边练习,重点知识及时实践,同时每天安排大量作业,加深记忆,巩固学习成果。 1.1 基本软件与准备工作 1.2 JavaScript 案例 …...
155基于matlab 的形态学权重自适应图像去噪
基于matlab 的形态学权重自适应图像去噪;通过串并联的滤波降噪对比图,说明并联降噪的优越性。输出降噪前后图像和不同方法的降噪情况的信噪比。程序已调通,可直接运行。 155matlab 自适应图像降噪 串并联降噪 (xiaohongshu.com)...
操作系统——内存管理(附带Leetcode算法题LRU)
目录 1.内存管理主要用来干什么? 2.什么是内存碎片? 3.虚拟内存 3.1传统存储管理方式的缺点? 3.2局部性原理 3.3什么是虚拟内存?有什么用? 3.3.1段式分配 3.3.2页式分配 3.3.2.1换页机制 3.3.2.2页面置换算法…...
I/O多路复用简记
IO多路复用(服务器如何处理多个socket的同时数据传输):1、select。2、poll。3、epoll。 select使用bitmap存socket文件描述符,由bitmap槽位的每一位为0或1决定对应序的socket连接是否有数据到来。由单线程(多线程处理每…...
SPECCPU2017操作说明
1、依赖包下载 yum install gcc* gfortran* 2、将软件包放至被测机器 3、增加权限 chmod X install.sh 4、运行安装 ./install.sh 5、运行 引入编译时所需的环境变量和相关库文件 source shrc 进入/spec2017,执行 ./runcpu -c ../config/Example-gcc-linux-ar…...
openresty (nginx)快速开始
文章目录 一、什么是openresty?二、openresty编译安装1. 编译安装命令1.1 编译完成后路径1.2 常用编译选项解释 2. nginx配置文件配置2.1 nginx.conf模板 3. nginx常见配置一个站点配置多个域名nginx配置中location匹配规则 三、OpenResty工作原理OpenResty工作原理…...
相机图像质量研究(11)常见问题总结:光学结构对成像的影响--像差
系列文章目录 相机图像质量研究(1)Camera成像流程介绍 相机图像质量研究(2)ISP专用平台调优介绍 相机图像质量研究(3)图像质量测试介绍 相机图像质量研究(4)常见问题总结:光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结:光学结构对成…...
【深度学习】基于多层感知机的手写数字识别
案例2:构建自己的多层感知机: MNIST手写数字识别 相关知识点: numpy科学计算包,如向量化操作,广播机制等 1 任务目标 1.1 数据集简介 MNIST手写数字识别数据集是图像分类领域最常用的数据集之一,它包含60,000张训练图片&am…...
给定n,m(200),构造一个n*m的矩阵a,使得每个4*4的子矩阵,左上角2*2的子矩阵的异或和等于右下角的,左下角的异或和等于右上角的
题目 #include <bits/stdc.h> using namespace std; #define int long long #define pb push_back #define fi first #define se second #define lson p << 1 #define rson p << 1 | 1 const int maxn 1e6 5, inf 1e18 5, maxm 4e4 5, mod 998244353…...
【开源】基于JAVA+Vue+SpringBoot的假日旅社管理系统
目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统介绍2.2 QA 问答 三、系统展示四、核心代码4.1 查询民宿4.2 新增民宿评论4.3 查询民宿新闻4.4 新建民宿预订单4.5 查询我的民宿预订单 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的假日旅社…...
kafka 文件存储机制
文章目录 1. 思考四个问题:1.1 topic中partition存储分布:1.2 partiton中文件存储方式:1.3 partiton中segment文件存储结构:1.4 在partition中如何通过offset查找message: 2. kafka日志存储参数配置 Topic是逻辑上的概念ÿ…...
引入BertTokenizer出现OSError: Can‘t load tokenizer for ‘bert-base-uncased‘.
今天在跑一个模型的时候出现该报错,完整报错为: OSError: Cant load tokenizer for bert-base-uncased. If you were trying to load it from https://huggingface.co/models, make sure you dont have a local directory with the same name. Otherwis…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力
引言: 在人工智能快速发展的浪潮中,快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型(LLM)。该模型代表着该领域的重大突破,通过独特方式融合思考与非思考…...
linux arm系统烧录
1、打开瑞芯微程序 2、按住linux arm 的 recover按键 插入电源 3、当瑞芯微检测到有设备 4、松开recover按键 5、选择升级固件 6、点击固件选择本地刷机的linux arm 镜像 7、点击升级 (忘了有没有这步了 估计有) 刷机程序 和 镜像 就不提供了。要刷的时…...
如何在看板中有效管理突发紧急任务
在看板中有效管理突发紧急任务需要:设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP(Work-in-Progress)弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中,设立专门的紧急任务通道尤为重要,这能…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
均衡后的SNRSINR
本文主要摘自参考文献中的前两篇,相关文献中经常会出现MIMO检测后的SINR不过一直没有找到相关数学推到过程,其中文献[1]中给出了相关原理在此仅做记录。 1. 系统模型 复信道模型 n t n_t nt 根发送天线, n r n_r nr 根接收天线的 MIMO 系…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
Springboot社区养老保险系统小程序
一、前言 随着我国经济迅速发展,人们对手机的需求越来越大,各种手机软件也都在被广泛应用,但是对于手机进行数据信息管理,对于手机的各种软件也是备受用户的喜爱,社区养老保险系统小程序被用户普遍使用,为方…...
毫米波雷达基础理论(3D+4D)
3D、4D毫米波雷达基础知识及厂商选型 PreView : https://mp.weixin.qq.com/s/bQkju4r6med7I3TBGJI_bQ 1. FMCW毫米波雷达基础知识 主要参考博文: 一文入门汽车毫米波雷达基本原理 :https://mp.weixin.qq.com/s/_EN7A5lKcz2Eh8dLnjE19w 毫米波雷达基础…...
在树莓派上添加音频输入设备的几种方法
在树莓派上添加音频输入设备可以通过以下步骤完成,具体方法取决于设备类型(如USB麦克风、3.5mm接口麦克风或HDMI音频输入)。以下是详细指南: 1. 连接音频输入设备 USB麦克风/声卡:直接插入树莓派的USB接口。3.5mm麦克…...
