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

【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 <= 500
  • 1 <= 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 &#xff0c;其中 left < right 。请你反转从位置 left 到位置 right 的链表节点&#xff0c;返回 反转后的链表 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5], left 2, right 4 输出&#xff1a;[1,4,3,2…...

谷歌 DeepMind 联合斯坦福推出了主从式遥操作双臂机器人系统增强版ALOHA 2

谷歌 DeepMind 联合斯坦福推出了 ALOHA 的增强版本 ——ALOHA 2。与一代相比&#xff0c;ALOHA 2 具有更强的性能、人体工程学设计和稳健性&#xff0c;且成本还不到 20 万元人民币。并且&#xff0c;为了加速大规模双手操作的研究&#xff0c;ALOHA 2 相关的所有硬件设计全部开…...

金融行业专题|证券超融合架构转型与场景探索合集(2023版)

更新内容 更新 SmartX 超融合在证券行业的覆盖范围、部署规模与应用场景。新增操作系统信创转型、Nutanix 国产化替代、网络与安全等场景实践。更多超融合金融核心生产业务场景实践&#xff0c;欢迎阅读文末电子书。 在金融行业如火如荼的数字化转型大潮中&#xff0c;传统架…...

【C语言】C的整理记录

前言 该笔记是建立在已经系统学习过C语言的基础上&#xff0c;笔者对C语言的知识和注意事项进行整理记录&#xff0c;便于后期查阅&#xff0c;反复琢磨。C语言是一种面向过程的编程语言。 原想在此阐述一下C语言的作用&#xff0c;然而发觉这些是编程语言所共通的作用&#…...

使用STM32Cubemx创建一个工程并且给出每一步的含义

...

C/C++模板初阶

目录 1. 泛型编程 2. 函数模板 2.1 函数模板概念 2.1 函数模板格式 2.3 函数模板的原理 2.4 函数模板的实例化 2.5 模板参数的匹配原则 3. 类模板 3.1 类模板的定义格式 3.2 类模板的实例化 1. 泛型编程 如何实现一个通用的交换函数呢&#xff1f; 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 目的&#xff1a;希望在获得一个新…...

【QT+QGIS跨平台编译】之三十一:【FreeXL+Qt跨平台编译】(一套代码、一套框架,跨平台编译)

文章目录 一、FreeXL介绍二、文件下载三、文件分析四、pro文件五、编译实践一、FreeXL介绍 【FreeXL跨平台编译】:Windows环境下编译成果(支撑QGIS跨平台编译,以及二次研发) 【FreeXL跨平台编译】:Linux环境下编译成果(支撑QGIS跨平台编译,以及二次研发) 【FreeXL跨平台…...

2024年 前端JavaScript入门到精通 第一天

主要讲解JavaScript核心知识&#xff0c;包含最新ES6语法&#xff0c;从基础到API再到高级。让你一边学习一边练习&#xff0c;重点知识及时实践&#xff0c;同时每天安排大量作业&#xff0c;加深记忆&#xff0c;巩固学习成果。 1.1 基本软件与准备工作 1.2 JavaScript 案例 …...

155基于matlab 的形态学权重自适应图像去噪

基于matlab 的形态学权重自适应图像去噪&#xff1b;通过串并联的滤波降噪对比图&#xff0c;说明并联降噪的优越性。输出降噪前后图像和不同方法的降噪情况的信噪比。程序已调通&#xff0c;可直接运行。 155matlab 自适应图像降噪 串并联降噪 (xiaohongshu.com)...

操作系统——内存管理(附带Leetcode算法题LRU)

目录 1.内存管理主要用来干什么&#xff1f; 2.什么是内存碎片&#xff1f; 3.虚拟内存 3.1传统存储管理方式的缺点&#xff1f; 3.2局部性原理 3.3什么是虚拟内存&#xff1f;有什么用&#xff1f; 3.3.1段式分配 3.3.2页式分配 3.3.2.1换页机制 3.3.2.2页面置换算法…...

I/O多路复用简记

IO多路复用&#xff08;服务器如何处理多个socket的同时数据传输&#xff09;&#xff1a;1、select。2、poll。3、epoll。 select使用bitmap存socket文件描述符&#xff0c;由bitmap槽位的每一位为0或1决定对应序的socket连接是否有数据到来。由单线程&#xff08;多线程处理每…...

SPECCPU2017操作说明

1、依赖包下载 yum install gcc* gfortran* 2、将软件包放至被测机器 3、增加权限 chmod X install.sh 4、运行安装 ./install.sh 5、运行 引入编译时所需的环境变量和相关库文件 source shrc 进入/spec2017&#xff0c;执行 ./runcpu -c ../config/Example-gcc-linux-ar…...

openresty (nginx)快速开始

文章目录 一、什么是openresty&#xff1f;二、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)常见问题总结&#xff1a;光学结构对成像的影响--焦距 相机图像质量研究(5)常见问题总结&#xff1a;光学结构对成…...

【深度学习】基于多层感知机的手写数字识别

案例2&#xff1a;构建自己的多层感知机: MNIST手写数字识别 相关知识点: numpy科学计算包&#xff0c;如向量化操作&#xff0c;广播机制等 1 任务目标 1.1 数据集简介 ​ MNIST手写数字识别数据集是图像分类领域最常用的数据集之一&#xff0c;它包含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. 思考四个问题&#xff1a;1.1 topic中partition存储分布&#xff1a;1.2 partiton中文件存储方式&#xff1a;1.3 partiton中segment文件存储结构&#xff1a;1.4 在partition中如何通过offset查找message: 2. kafka日志存储参数配置 Topic是逻辑上的概念&#xff…...

引入BertTokenizer出现OSError: Can‘t load tokenizer for ‘bert-base-uncased‘.

今天在跑一个模型的时候出现该报错&#xff0c;完整报错为&#xff1a; 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…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

什么?连接服务器也能可视化显示界面?:基于X11 Forwarding + CentOS + MobaXterm实战指南

文章目录 什么是X11?环境准备实战步骤1️⃣ 服务器端配置(CentOS)2️⃣ 客户端配置(MobaXterm)3️⃣ 验证X11 Forwarding4️⃣ 运行自定义GUI程序(Python示例)5️⃣ 成功效果![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/55aefaea8a9f477e86d065227851fe3d.pn…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

MySQL用户和授权

开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...

C++.OpenGL (14/64)多光源(Multiple Lights)

多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

git: early EOF

macOS报错&#xff1a; Initialized empty Git repository in /usr/local/Homebrew/Library/Taps/homebrew/homebrew-core/.git/ remote: Enumerating objects: 2691797, done. remote: Counting objects: 100% (1760/1760), done. remote: Compressing objects: 100% (636/636…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...