当前位置: 首页 > 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;文章中敏感信息均已做多层打马处理。传播、利用本文章所提供的信息而造成的任何直接或者间接的…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录

ASP.NET Core 是一个跨平台的开源框架&#xff0c;用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录&#xff0c;以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

Linux简单的操作

ls ls 查看当前目录 ll 查看详细内容 ls -a 查看所有的内容 ls --help 查看方法文档 pwd pwd 查看当前路径 cd cd 转路径 cd .. 转上一级路径 cd 名 转换路径 …...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

【HTTP三个基础问题】

面试官您好&#xff01;HTTP是超文本传输协议&#xff0c;是互联网上客户端和服务器之间传输超文本数据&#xff08;比如文字、图片、音频、视频等&#xff09;的核心协议&#xff0c;当前互联网应用最广泛的版本是HTTP1.1&#xff0c;它基于经典的C/S模型&#xff0c;也就是客…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

智能分布式爬虫的数据处理流水线优化:基于深度强化学习的数据质量控制

在数字化浪潮席卷全球的今天&#xff0c;数据已成为企业和研究机构的核心资产。智能分布式爬虫作为高效的数据采集工具&#xff0c;在大规模数据获取中发挥着关键作用。然而&#xff0c;传统的数据处理流水线在面对复杂多变的网络环境和海量异构数据时&#xff0c;常出现数据质…...

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

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

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...