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

算法leetcode|92. 反转链表 II(rust重拳出击)


文章目录

  • 92. 反转链表 II:
    • 样例 1:
    • 样例 2:
    • 提示:
    • 进阶:
  • 分析:
  • 题解:
    • rust:
    • go:
    • c++:
    • python:
    • java:


92. 反转链表 II:

给你单链表的头指针 head 和两个整数 leftright ,其中 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

进阶:

  • 你可以使用一趟扫描完成反转吗?
  • 将链表分成3部分,即前面不需要反转的部分,中间需要反转的部分,后面不需要反转的部分。
  • 单向链表只能从一个方向遍历,并且不能随机访问,所以我们只能按照顺序处理,这里就不能有什么好的技巧了。
  • 先处理前面不需要反转的部分,直接遍历跳过即可,这里由于没法随机访问,所以只能按顺序遍历。
  • 接下来处理中间需要反转的部分,想象一下入栈,遍历一个节点就放到头(中间需要遍历部分的头),依次遍历处理,就完成了反转。
  • 最后处理后面不需要遍历的部分,其实这部分不需要做什么处理,所以不需要继续遍历,但是要当心将链表接起来。
  • 这里不得不说由于rust的所有权问题,同一时间只能有一个可修改指针,可能是二当家水平太菜,处理链表有点啰嗦。

分析:

  • 面对这道算法题目,二当家的再次陷入了沉思。

题解:

rust:

// Definition for singly-linked list.
// #[derive(PartialEq, Eq, Clone, Debug)]
// pub struct ListNode {
//   pub val: i32,
//   pub next: Option<Box<ListNode>>
// }
//
// impl ListNode {
//   #[inline]
//   fn new(val: i32) -> Self {
//     ListNode {
//       next: None,
//       val
//     }
//   }
// }
impl Solution {pub fn reverse_between(head: Option<Box<ListNode>>, left: i32, right: i32) -> Option<Box<ListNode>> {// 来个哑节点方便处理头节点在反转范围内的情况let mut dummy = Option::Some(Box::new(ListNode::new(0)));dummy.as_mut().unwrap().next = head;// 前面不需要反转部分的尾let mut pre = dummy.as_mut().unwrap();// 跳过前面不需要翻转的部分for _ in 0..left - 1 {pre = pre.next.as_mut().unwrap();}// 中间需要反转的部分(同时打断前面不需要反转部分和中间需要反转部分的链接)let mut cur = pre.next.take();// 进行反转for _ in 0..right - left {let mut next = cur.as_mut().unwrap().next.take();cur.as_mut().unwrap().next = next.as_mut().unwrap().next.take();next.as_mut().unwrap().next = pre.next.take();pre.next = next;}// 重新接上while pre.next.is_some() {pre = pre.next.as_mut().unwrap();}pre.next = cur;return dummy.unwrap().next;}
}

go:

/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/
func reverseBetween(head *ListNode, left int, right int) *ListNode {// 来个哑节点方便处理头节点在反转范围内的情况dummy := &ListNode{Val: 0, Next: head}pre := dummyfor i := 0; i < left-1; i++ {pre = pre.Next}cur := pre.Nextfor i := 0; i < right-left; i++ {next := cur.Nextcur.Next = next.Nextnext.Next = pre.Nextpre.Next = next}return dummy.Next
}

c++:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* reverseBetween(ListNode* head, int left, int right) {// 来个哑节点方便处理头节点在反转范围内的情况ListNode *dummy = new ListNode(0);dummy->next = head;ListNode *pre = dummy;for (int i = 0; i < left - 1; ++i) {pre = pre->next;}ListNode *cur = pre->next;ListNode *next;for (int i = 0; i < right - left; ++i) {next = cur->next;cur->next = next->next;next->next = pre->next;pre->next = next;}return dummy->next;}
};

python:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:# 来个哑节点方便处理头节点在反转范围内的情况dummy = ListNode(0)dummy.next = headpre = dummyfor _ in range(left - 1):pre = pre.nextcur = pre.nextfor _ in range(right - left):next = cur.nextcur.next = next.nextnext.next = pre.nextpre.next = nextreturn dummy.next

java:

/*** 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) {// 来个哑节点方便处理头节点在反转范围内的情况ListNode dummy = new ListNode(0);dummy.next = head;ListNode pre = dummy;for (int i = 0; i < left - 1; i++) {pre = pre.next;}ListNode cur = pre.next;ListNode next;for (int i = 0; i < right - left; i++) {next = cur.next;cur.next = next.next;next.next = pre.next;pre.next = next;}return dummy.next;}
}

非常感谢你阅读本文~
欢迎【点赞】【收藏】【评论】三连走一波~
放弃不难,但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子:https://le-yi.blog.csdn.net/ 博客原创~


相关文章:

算法leetcode|92. 反转链表 II(rust重拳出击)

文章目录 92. 反转链表 II&#xff1a;样例 1&#xff1a;样例 2&#xff1a;提示&#xff1a;进阶&#xff1a; 分析&#xff1a;题解&#xff1a;rust&#xff1a;go&#xff1a;c&#xff1a;python&#xff1a;java&#xff1a; 92. 反转链表 II&#xff1a; 给你单链表的…...

Chapter 7 - 3. Congestion Management in Ethernet Storage Networks以太网存储网络的拥塞管理

Pause Threshold for Long Distance Links长途链路的暂停阈值 This section uses the following basic concepts: 本节使用以下基本概念: Bit Time (BT): It is the time taken to transmit one bit. It is the reciprocal of the bit rate. For example, BT of a 10 GbE po…...

优雅玩转实验室服务器(二)传输文件

使用服务器最重要的肯定是传输文件了&#xff0c;我们不仅需要本地的一些资源上传到服务器&#xff0c;好进行实验&#xff0c;也需要将服务器计算得到的实验结果传输到本地&#xff0c;来进行预览或者报告撰写。 首先&#xff0c;由于涉及到服务器操作&#xff0c;我强烈推荐…...

动态面板简介以及ERP原型图案列

动态面板简介以及ERP原型图案列 1.Axure动态面板简介2.使用Axure制作ERP登录界面3.使用Asure完成左侧菜单栏4.使用Axuer完成公告栏5.使用Axuer完成左边侧边栏 1.Axure动态面板简介 在Axure RP中&#xff0c;动态面板是一种强大的交互设计工具&#xff0c;它允许你创建可交互的…...

漏刻有时百度地图API实战开发(12)(切片工具的使用、添加自定义图层TileLayer)

TileLayer向地图中添加自定义图层 var tileLayer new BMap.TileLayer();tileLayer.getTilesUrl function (tileCoord, zoom) {var x tileCoord.x;var y tileCoord.y;return images/tiles/ zoom /tile- x _ y .png;}var lockMap new BMap.MapType(lock_map, tileLaye…...

python 爬虫 m3u8 视频文件 加密解密 整合mp4

文章目录 一、完整代码二、视频分析1. 认识m3u8文件2. 获取密钥&#xff0c;构建解密器3. 下载ts文件4. 合并ts文件为mp4 三、总结 一、完整代码 完整代码如下&#xff1a; import requests from multiprocessing import Pool import re import os from tqdm import tqdm fro…...

mybatis中xml文件容易搞混的属性

目录 第一章、1.1&#xff09;MyBatis中resultMap标签1.2&#xff09;MyBatis的resultType1.3&#xff09;MyBatis的parameterType1.4&#xff09;type属性1.5&#xff09;jdbcType属性1.6&#xff09;javaType属性1.7&#xff09;ofType属性 友情提醒: 先看文章目录&#xff…...

android Retrofit2.0请求 延长超时操作

import okhttp3.OkHttpClient; import retrofit2.Retrofit; import retrofit2.converter.gson.GsonConverterFactory;public class MyApiClient {private static final String BASE_URL "https://api.example.com/";// 创建 OkHttpClient&#xff0c;并设置超时时间…...

Axure之动态面板轮播图

目录 一.介绍 二.好处 三.动态面板轮播图 四.动态面板多方式登录 五.ERP登录 六.ERP的左侧菜单栏 七.ERP的公告栏 今天就到这了哦&#xff01;&#xff01;&#xff01;希望能帮到你了哦&#xff01;&#xff01;&#xff01; 一.介绍 Axure中的动态面板是一个非常有用的组…...

一文读懂算法中的时间复杂度和空间复杂度,O(1)、O(logn)、O(n)、O(n^2)、O(2^n) 附举例说明,常见的时间复杂度,空间复杂度

时间复杂度和空间复杂度是什么 时间复杂度&#xff08;Time Complexity&#xff09;是描述算法运行时间长短的一个度量。空间复杂度&#xff08;Space Complexity&#xff09;是描述算法在运行过程中所需要的存储空间大小的一个度量。 时间复杂度和空间复杂度是衡量算法性能…...

LWIP热插拔功能实现

0 工具准备 1.lwip 1.4.1 2.RTOS&#xff08;本文使用rt-thread&#xff09;1 使能连接变化回调功能 打开lwipopts.h&#xff0c;将宏定义LWIP_NETIF_LINK_CALLBACK的值设为1&#xff0c;如下&#xff1a; #define LWIP_NETIF_LINK_CALLBACK 1这个宏定义被使能后会将…...

android下的app性能测试应主要针对那些方面,如何开展?

如何开展安卓手机下的App性能测试&#xff0c;对于优秀的测试人员而言&#xff0c;除了要懂得性能测试的步骤流程外&#xff0c;还应该懂的性能测试的一些其他知识&#xff0c;比如性能测试指标、各指标的意义&#xff0c;常用的性能测试工具、如何查看结果分析等等知识。所以本…...

【深度学习】注意力机制(二)

本文介绍一些注意力机制的实现&#xff0c;包括EA/MHSA/SK/DA/EPSA。 【深度学习】注意力机制&#xff08;一&#xff09; 【深度学习】注意力机制&#xff08;三&#xff09; 目录 一、EA&#xff08;External Attention&#xff09; 二、Multi Head Self Attention 三、…...

学习黑马vue

项目分析 项目下载地址&#xff1a;vue-admin-template-master: 学习黑马vue 项目下载后没有环境可参考我的篇文章&#xff0c;算是比较详细&#xff1a;vue安装与配置-CSDN博客 安装这两个插件可格式化代码&#xff0c;vscode这个软件是免费的&#xff0c;官网&#xff1a;…...

gdb本地调试版本移植至ARM-Linux系统

移植ncurses库 本文使用的ncurses版本为ncurses-5.9.tar.gz 下载地址&#xff1a;https://ftp.gnu.org/gnu/ncurses/ncurses-5.9.tar.gz 1. 将ncurses压缩包拷贝至Linux主机或使用wget命令下载并解压 tar-zxvf ncurses-5.9.tar.gz 2. 解压后进入到ncurses-5.9目录…...

《Linux C编程实战》笔记:实现自己的ls命令

关键函数的功能及说明 1.void display_attribute(struct stat buf,char *name) 函数功能&#xff1a;打印文件名为name的文件信息&#xff0c;如 含义分别为&#xff1a;文件的类型和访问权限&#xff0c;文件的链接数&#xff0c;文件的所有者&#xff0c;文件所有者所属的组…...

Python个人代码随笔(观看无益,请跳过)

异常抛错&#xff1a;一般来说&#xff0c;在程序中&#xff0c;遇到异常时&#xff0c;会从这一层逐层往外抛错&#xff0c;一直抛到最外层&#xff0c;由最外层把错误显示在用户终端。 try:raise ValueError("A value error...") except ValueError:print("V…...

Unity中实现ShaderToy卡通火(总结篇)

文章目录 前言一、把卡通火修改为后处理效果1、在Shader属性面板定义属性接收帧缓存纹理2、在片元着色器对其纹理采样后&#xff0c;与卡通火相加输出请添加图片描述 二、我们自定义卡通火1、修改 _CUTOFF 使卡通火显示在屏幕两侧2、使火附近屏幕偏红色 前言 在之前的文章中&a…...

等保2.0的变化

1法律地位得到确认 《中华人民共和国网络安全法》第21条规定“国家实行网络安全等级保护制度”&#xff0c;要求“网络运营者应当按照网络安全等级保护制度要求&#xff0c;履行安全保护义务”&#xff1b;第31条规定“对于国家关键信息基础设施&#xff0c;在网络安全等级保护…...

漏洞复现-网神SecGate3600防火墙敏感信息泄露漏洞(附漏洞检测脚本)

免责声明 文章中涉及的漏洞均已修复&#xff0c;敏感信息均已做打码处理&#xff0c;文章仅做经验分享用途&#xff0c;切勿当真&#xff0c;未授权的攻击属于非法行为&#xff01;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直接或者间接的…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

七、数据库的完整性

七、数据库的完整性 主要内容 7.1 数据库的完整性概述 7.2 实体完整性 7.3 参照完整性 7.4 用户定义的完整性 7.5 触发器 7.6 SQL Server中数据库完整性的实现 7.7 小结 7.1 数据库的完整性概述 数据库完整性的含义 正确性 指数据的合法性 有效性 指数据是否属于所定…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

深度学习水论文:mamba+图像增强

&#x1f9c0;当前视觉领域对高效长序列建模需求激增&#xff0c;对Mamba图像增强这方向的研究自然也逐渐火热。原因在于其高效长程建模&#xff0c;以及动态计算优势&#xff0c;在图像质量提升和细节恢复方面有难以替代的作用。 &#x1f9c0;因此短时间内&#xff0c;就有不…...

站群服务器的应用场景都有哪些?

站群服务器主要是为了多个网站的托管和管理所设计的&#xff0c;可以通过集中管理和高效资源的分配&#xff0c;来支持多个独立的网站同时运行&#xff0c;让每一个网站都可以分配到独立的IP地址&#xff0c;避免出现IP关联的风险&#xff0c;用户还可以通过控制面板进行管理功…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

Android写一个捕获全局异常的工具类

项目开发和实际运行过程中难免会遇到异常发生&#xff0c;系统提供了一个可以捕获全局异常的工具Uncaughtexceptionhandler&#xff0c;它是Thread的子类&#xff08;就是package java.lang;里线程的Thread&#xff09;。本文将利用它将设备信息、报错信息以及错误的发生时间都…...