当前位置: 首页 > 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…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

1688商品列表API与其他数据源的对接思路

将1688商品列表API与其他数据源对接时&#xff0c;需结合业务场景设计数据流转链路&#xff0c;重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点&#xff1a; 一、核心对接场景与目标 商品数据同步 场景&#xff1a;将1688商品信息…...

【Oracle】分区表

个人主页&#xff1a;Guiat 归属专栏&#xff1a;Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...

有限自动机到正规文法转换器v1.0

1 项目简介 这是一个功能强大的有限自动机&#xff08;Finite Automaton, FA&#xff09;到正规文法&#xff08;Regular Grammar&#xff09;转换器&#xff0c;它配备了一个直观且完整的图形用户界面&#xff0c;使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

Windows安装Miniconda

一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...