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

备战蓝桥杯————递归反转单链表的一部分

        递归反转单链表已经明白了,递归反转单链表的一部分你知道怎么做吗?

一、反转链表Ⅱ

题目描述

        给你单链表的头指针 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

进阶: 你可以使用一趟扫描完成反转吗?

解题思路及代码

 reverseN 递归反转链表的算法,具体的思路如下:

  •         函数 reverseN 用于反转以 head 为起点的前 n 个节点,并返回反转后的新头结点。
  •         当 n 等于 1 时,表示只有一个节点需要反转,那么记录下第 n + 1 个节点(后驱节点         successor),并返回当前节点 head。
  •         当 n 大于 1 时,递归调用 reverseN 函数反转前 n - 1 个节点,得到反转后的新头结点 last。
  •         在反转的过程中,将 head 的下一个节点 head.next 的 next 指针指向 head,实现反转。
  •         将 head 的 next 指针指向记录的后驱节点 successor,保证反转后的链表与后面的节点连接起来。
  •         返回新的头结点 last,作为上一层递归的结果。


 

  •         当 m 不等于 1 时,我们需要将 head 的索引视为 1,并且进行递归处理。此时,我们希望从第 m 个元素开始反转。因此,我们需要将 head.next 的索引视为 1,然后递归地处理head.next,将范围调整为从第 m - 1 个元素开始反转。
  •         具体来说,对于 head.next.next,我们需要将 head.next.next 的索引视为 1。这意味着我们希望从 head.next.next 开始反转。因此,我们将递归地调用 reverseBetween 方法,并将 head.next.next 作为新的头结点,范围调整为从第 m - 2 个元素开始反转。
  •         通过不断地将头结点向后移动,并调整范围,我们可以确保在链表中正确地定位到需要反转的范围,并对其进行处理。这样,无论 m 的值是多少,我们都能在链表中正确地找到需要反转的区间。

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {if(left==1){return reverseN(head,right);}head.next=reverseBetween(head.next,left-1,right-1);return head;}ListNode succetor=null;public ListNode reverseN(ListNode head, int n){if(n==1){succetor=head.next;return head;}ListNode last=reverseN(head.next,n-1);head.next.next=head;head.next=succetor;return last;}
}

结果展示

相关文章:

备战蓝桥杯————递归反转单链表的一部分

递归反转单链表已经明白了&#xff0c;递归反转单链表的一部分你知道怎么做吗&#xff1f; 一、反转链表Ⅱ 题目描述 给你单链表的头指针 head 和两个整数 left 和 right &#xff0c;其中 left < right 。请你反转从位置 left 到位置 right 的链表节点&#xff0c;返回 反…...

rabbitmq知识梳理

一.WorkQueues模型 Work queues&#xff0c;任务模型。简单来说就是让多个消费者绑定到一个队列&#xff0c;共同消费队列中的消息。 当消息处理比较耗时的时候&#xff0c;可能生产消息的速度会远远大于消息的消费速度。长此以往&#xff0c;消息就会堆积越来越多&#xff0c…...

【数据结构与算法】动态规划法解题20240227

动态规划法 一、什么是动态规划二、动态规划的解题步骤三、509. 斐波那契数1、动规五部曲&#xff1a; 四、70. 爬楼梯1、动规五部曲&#xff1a; 五、746. 使用最小花费爬楼梯1、动规五部曲&#xff1a; 一、什么是动态规划 动态规划&#xff0c;英文&#xff1a;Dynamic Pro…...

备战蓝桥杯—— 双指针技巧巧答链表2

对于单链表相关的问题&#xff0c;双指针技巧是一种非常广泛且有效的解决方法。以下是一些常见问题以及使用双指针技巧解决&#xff1a; 合并两个有序链表&#xff1a; 使用两个指针分别指向两个链表的头部&#xff0c;逐一比较节点的值&#xff0c;将较小的节点链接到结果链表…...

半监督节点分类-graph learning

半监督节点分类相当于在一个图当中&#xff0c;用一部分节点的类别上已知的&#xff0c;有另外一部分节点的类别是未知的&#xff0c;目标是使用有标签的节点来推断没有标签的节点 注意 半监督节点分类属于直推式学习&#xff0c;直推式学习相当于出现新节点后&#xff0c;需要…...

软件文档-运维-开发-管理-资质-评审-招投标-验收

开发文档&#xff1a;这类文档主要用于记录软件的开发过程和细节&#xff0c;包括&#xff1a; 《功能要求》&#xff1a;描述了软件应具备的功能&#xff0c;是软件开发的基础。《投标方案》&#xff1a;向潜在的客户或招标方展示公司的技术和项目实施能力。《需求分析》&…...

猫头虎分享已解决Bug || Vue中的TypeError: Cannot read property ‘name‘ of undefined 错误

博主猫头虎的技术世界 &#x1f31f; 欢迎来到猫头虎的博客 — 探索技术的无限可能&#xff01; 专栏链接&#xff1a; &#x1f517; 精选专栏&#xff1a; 《面试题大全》 — 面试准备的宝典&#xff01;《IDEA开发秘籍》 — 提升你的IDEA技能&#xff01;《100天精通鸿蒙》 …...

技术应用:使用Spring Boot、MyBatis Plus和Dynamic DataSource实现多数据源

引言 在现代的软件开发中&#xff0c;许多应用程序需要同时访问多个数据库。例如&#xff0c;一个电子商务平台可能需要访问多个数据库来存储用户信息、产品信息和订单信息等。在这种情况下&#xff0c;使用多数据源是一种常见的解决方案&#xff0c;它允许我们在一个应用程序…...

C# Onnx 使用onnxruntime部署实时视频帧插值

目录 介绍 效果 模型信息 项目 代码 下载 C# Onnx 使用onnxruntime部署实时视频帧插值 介绍 github地址&#xff1a;https://github.com/google-research/frame-interpolation FILM: Frame Interpolation for Large Motion, In ECCV 2022. The official Tensorflow 2…...

编程笔记 Golang基础 016 数据类型:数字类型

编程笔记 Golang基础 016 数据类型&#xff1a;数字类型 1. 整数类型&#xff08;Integer Types&#xff09;a) 固定长度整数&#xff1a;b) 变长整数&#xff1a; 2. 浮点数类型&#xff08;Floating-Point Types&#xff09;3. 复数类型&#xff08;Complex Number Types&…...

一周学会Django5 Python Web开发-会话管理(CookiesSession)

锋哥原创的Python Web开发 Django5视频教程&#xff1a; 2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili2024版 Django5 Python web开发 视频教程(无废话版) 玩命更新中~共计26条视频&#xff0c;包括&#xff1a;2024版 Django5 Python we…...

QT之QString.arg输出固定位数

问题描述 我需要用QString输出一个固定位数的数字字符串。起初我的代码是这样&#xff1a; int img_num 1 auto new_name QString("%1.png").arg((int)img_num, 3, 10, 0); //最后一个参数用u0也是一样的 qDebug() << "new_name:" << new…...

Linux下各种压缩包的压缩与解压

tar 归档&#xff0c;不压缩&#xff0c;常见后缀 .tar # 将文件夹归档成为一个包 tar cf rootfs.tar rootfs # 将归档包还原为文件夹 tar xf rootfs.tar # 将归档包还原到路径 a/b/c tar xf rootfs.tar -C a/b/cgzip压缩&#xff0c; 常见后缀 .tar.gz .tgz # 压缩 tar czf …...

【ctfshow—web】——信息搜集篇1(web1~20详解)

ctfshow—web题解 web1web2web3web4web5web6web7web8web9web10web11web12web13web14web15web16web17web18web19web20 web1 题目提示 开发注释未及时删除 那就找开发注释咯&#xff0c;可以用F12来查看&#xff0c;也可以CtrlU直接查看源代码呢 就拿到flag了 web2 题目提示 j…...

GEE入门篇|遥感专业术语(实践操作4):光谱分辨率(Spectral Resolution)

目录 光谱分辨率&#xff08;Spectral Resolution&#xff09; 1.MODIS 2.EO-1 光谱分辨率&#xff08;Spectral Resolution&#xff09; 光谱分辨率是指传感器进行测量的光谱带的数量和宽度。 您可以将光谱带的宽度视为每个波段的波长间隔&#xff0c;在多个波段测量辐射亮…...

c++中模板的注意事项

1. 模板定义时&#xff0c;<>中的虚拟类型参数不能为空。(因为我们使用模板就是希望使用模拟类型代替其它的类型&#xff0c;如果我们不定义就没有意义了) 2. 无论是定义函数模板还是类模板&#xff0c;其实template定义与后面使用虚拟类型的类或者函数&#xff0c;是…...

【代码随想录python笔记整理】第十三课 · 链表的基础操作 1

前言:本笔记仅仅只是对内容的整理和自行消化,并不是完整内容,如有侵权,联系立删。 一、链表 在之前的学习中,我们接触到了字符串和数组(列表)这两种结构,它们具有着以下的共同点:1、元素按照一定的顺序来排列。2、可以通过索引来访问数组中的元素和字符串中的字符。由此,…...

JAVA工程师面试专题-《Mysql》篇

目录 一、基础 1、mysql可以使用多少列创建索引&#xff1f; 2、mysql常用的存储引擎有哪些 3、MySQL 存储引擎&#xff0c;两者区别 4、mysql默认的隔离级别 5、数据库三范式 6、drop、delete 与 truncate 区别&#xff1f; 7、IN与EXISTS的区别 二、索引 1、索引及索…...

@ 代码随想录算法训练营第4周(C语言)|Day22(二叉树)

代码随想录算法训练营第4周&#xff08;C语言&#xff09;|Day22&#xff08;二叉树&#xff09; Day22、二叉树&#xff08;包含题目 ● 235. 二叉搜索树的最近公共祖先 ● 701.二叉搜索树中的插入操作 ● 450.删除二叉搜索树中的节点 &#xff09; 235. 二叉搜索树的最近公…...

福特锐界2021plus 汽车保养手册

福特锐界2021plus汽车保养手册两页&#xff0c;零部件保养要求&#xff0c;电子版放这里方便查询&#xff1a;...

RocketMQ延迟消息机制

两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数&#xff0c;对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后&#xf…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

leetcodeSQL解题:3564. 季节性销售分析

leetcodeSQL解题&#xff1a;3564. 季节性销售分析 题目&#xff1a; 表&#xff1a;sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...

C语言中提供的第三方库之哈希表实现

一. 简介 前面一篇文章简单学习了C语言中第三方库&#xff08;uthash库&#xff09;提供对哈希表的操作&#xff0c;文章如下&#xff1a; C语言中提供的第三方库uthash常用接口-CSDN博客 本文简单学习一下第三方库 uthash库对哈希表的操作。 二. uthash库哈希表操作示例 u…...

【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录

#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...

Selenium 查找页面元素的方式

Selenium 查找页面元素的方式 Selenium 提供了多种方法来查找网页中的元素&#xff0c;以下是主要的定位方式&#xff1a; 基本定位方式 通过ID定位 driver.find_element(By.ID, "element_id")通过Name定位 driver.find_element(By.NAME, "element_name"…...