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

面试热题(反转链表)

给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

       链表的题,大部分都可以用指针或者递归可以做,指针如果做不出来的话,建议多声明几个指针就可以做的出来了

方法一:

       因为链表中的头结点也有可能进行反转操作,所以我们为了不失一般性,创建一个虚拟头结点进行操作

       我们需要旋转[left,right]区间内的链表结点,所以我们就必须要知道left的上一个结点是谁,所以我们可以使用快慢指针进行操作,slow慢指针指向我们left的上一个结点,对区间内的节点进行反转,过程如下:

 源代码如下:

 public ListNode reverseBetween(ListNode head, int left, int right) {//如果头结点为空或者是头结点的后继点为空的话直接返回headif(head==null||head.next==null){return head;}//创建一个虚拟头结点ListNode dummyHead=new ListNode(0);dummyHead.next=head;//设置两个指针ListNode slow=dummyHead;//慢指针-->指向left指针指向节点的上一个节点ListNode fast=dummyHead.next;//快指针  将left指针与right指针中的节点加到left指针前面(包括right指针)//进行移动,将slow指针移向left指针的前一个节点for (int i = 1; i <left; i++) {slow=slow.next;fast=fast.next;}//将left和right指针中的节点移向left节点前(包括right指针对应的节点)for (int i = 0; i <right-left; i++) {ListNode removeNode=fast.next;fast.next=fast.next.next;removeNode.next=slow.next;slow.next=removeNode;}//返回头结点后的链表长度return dummyHead.next;}

方法二:

在以前学习得到过程中我们已经学过了链表翻转(必会)

//这几行代码必须得会,链表题最多的就是翻转,你可以直接当一个api去用
public ListNode reverse(ListNode root){if(root==null||root.next==null){return root;}//前扑ListNode pre=null;ListNode cur=root;//后继ListNode next=null;while(cur!=null){next=cur.next;cur.next=pre;pre=cur;cur=next;}//返回的是翻转后的头结点return pre;}

       现在我们只需要找到需要翻转链表区间的前扑后继,然后通过前扑的next指向翻转后的头结点,让反转后的尾结点指向后继,这道题就解出来了

 

源代码如下(这种方法比较推荐,比较容易理解):

 public ListNode reverseBetween(ListNode head, int left, int right) {if(head==null||left>=right){return head;}//找到left的前驱节点,因为会设计头结点的操作,所以要创建一个虚拟头结点ListNode dummyNode=new ListNode(0,head);ListNode pre=dummyNode;//找到对应的前驱节点for (int i =1; i <left; i++) {pre=pre.next;}//未反转链表的头结点ListNode leftNode=pre.next;ListNode rightNode=leftNode;pre.next=null;//找到未反转链表的尾结点for (int i = 1; i <=right-left; i++) {rightNode=rightNode.next;}//找到后继ListNode end=rightNode.next;rightNode.next=null;ListNode newStartNode=reverse(leftNode);pre.next=newStartNode;leftNode.next=end;return dummyNode.next;}//反转链表public ListNode reverse(ListNode root){if(root==null||root.next==null){return root;}ListNode pre=null;ListNode cur=root;ListNode next=null;while(cur!=null){next=cur.next;cur.next=pre;pre=cur;cur=next;}return pre;}

 

相关文章:

面试热题(反转链表)

给你单链表的头指针 head 和两个整数 left 和 right &#xff0c;其中 left < right 。请你反转从位置 left 到位置 right 的链表节点&#xff0c;返回 反转后的链表 。 链表的题&#xff0c;大部分都可以用指针或者递归可以做&#xff0c;指针如果做不出来的话&#xff0c;…...

竞赛项目 深度学习的水果识别 opencv python

文章目录 0 前言2 开发简介3 识别原理3.1 传统图像识别原理3.2 深度学习水果识别 4 数据集5 部分关键代码5.1 处理训练集的数据结构5.2 模型网络结构5.3 训练模型 6 识别效果7 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; 深度学习…...

Java项目部署云windows细节

springboot项目 pom文件中必须要有这个插件&#xff08;正常其实都有就是我手贱以前不小心删除了&#xff09; 他的作用是查找主类 <build><plugins><plugin><groupId>org.springframework.boot</groupId><artifactId>spring-boot-maven-…...

软件功能测试有什么注意事项?功能测试报告起到什么作用?

软件功能测试是软件开发过程中至关重要的一环&#xff0c;它用于评估软件功能的质量和稳定性&#xff0c;并确保软件能够按照预期进行工作。然而&#xff0c;在进行功能测试时&#xff0c;有一些注意事项需要特别关注&#xff0c;以确保测试的准确性和有效性。 一、软件功能测…...

Kubernetes 调度 约束

调度约束 Kubernetes 是通过 List-Watch 的机制进行每个组件的协作&#xff0c;保持数据同步的&#xff0c;每个组件之间的设计实现了解耦。 用户是通过 kubectl 根据配置文件&#xff0c;向 APIServer 发送命令&#xff0c;在 Node 节点上面建立 Pod 和 Container。 APIServer…...

Grafana技术文档-概念-《十分钟扫盲》

Grafana官网链接 Grafana: The open observability platform | Grafana Labs 基本概念 Grafana是一个开源的度量分析和可视化套件&#xff0c;常用于对大量数据进行实时分析和可视化。以下是Grafana的基本概念&#xff1a; 数据源&#xff08;Data Source&#xff09;&#…...

【JavaEE进阶】Spring 更简单的读取和存储对象

文章目录 一. 存储Bean对象1. 配置扫描路径2. 添加注解存储 Bean 对象2.1 使用五大类注解存储Bean2.2 为什么要有五大类注解&#xff1f;2.3 有关获取Bean参数的命名规则 3. 使用方法注解储存 Bean 对象3.1 方法注解储存对象的用法3.2 Bean的重命名3.3 同⼀类型多个 Bean 报错 …...

KafKa集群搭建和知识点

一、KafKa概述 1.1 定义 KafKa是一个分布式的基于发布/订阅模式的消息队列&#xff0c;主要应用于大数据试试处理领域 是一个分布式、支持分区的&#xff08;partition&#xff09;、多副本的&#xff08;replica&#xff09;&#xff0c;基于zookeeper协调的分布式消息系统&a…...

剑指 Offer 56 - I. 数组中数字出现的次数题解

题目描述&#xff1a;剑指 Offer 56 - I. 数组中数字出现的次数 - 力扣&#xff08;LeetCode&#xff09; 一个整型数组 nums 里除两个数字之外&#xff0c;其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)&#xff0c;空间复杂度是O(1)。 示…...

CSDN付费专栏写作协议

一、总则 1.1、欢迎您选用CSDN付费专栏服务&#xff08;“本服务”&#xff09;。以下所述条款和条件即构成您与CSDN就使用本服务所达成的协议&#xff08;“本协议&#xff09;。本协议被视为《CSDN用户服务条款》&#xff08;链接&#xff1a;https://passport.csdn.net/ser…...

[保研/考研机试] KY30 进制转换-大整数转二进制 清华大学复试上机题 C++实现

描述 将一个长度最多为30位数字的十进制非负整数转换为二进制数输出。 输入描述&#xff1a; 多组数据&#xff0c;每行为一个长度不超过30位的十进制非负整数。 &#xff08;注意是10进制数字的个数可能有30个&#xff0c;而非30bits的整数&#xff09; 输出描述&#xff…...

vue3多条件搜索功能

搜索功能在后台管理页面中非常常见&#xff0c;本篇就着重讲一下vue3-admin-element框架中如何实现一个顶部多条件搜索功能 一、首先需要在vue页面的<template></template>中写入对应的结构 <!-- 搜索 --><div style"display: flex; justify-content…...

C++20协程

目录 协程原理&#xff1a; 进程、线程和协程的区别和联系​编辑 协程在IO多路复用中 协程的目的&#xff1a; 协程的优势&#xff1a; ​ 协程原理&#xff1a; &#xff08;学习来源&#xff1a;幼麟实验室&#xff09; 线程是进程中的执行体&#xff0c;拥有一个…...

Zabbix 6.0 监控其他

文章目录 一、Zabbix 监控 Windows 系统1&#xff09;下载 Windows 客户端 Zabbix agent 22&#xff09;安装客户端&#xff0c;配置3&#xff09;在服务端 Web 页面添加主机&#xff0c;关联模板 二、Zabbix 监控 java 应用1&#xff09;客户端开启 java jmxremote 远程监控功…...

Django rest_framework Serializer中的create、Views中的create/perform_create的区别

Django rest_framework Serializer中的create、Views中的create/perform_create的区别 对于后端来说&#xff0c;前后端分离的方式能让前后端的开发都爽。和所有的爽一样&#xff0c;每爽一次都要付出一定的代价。而前后端分离的代价&#xff0c;就是后端要面对巨量的模块化的功…...

差异性分析傻瓜版

path1输入你的第一个Excel path2输入你的第二个Excel DEG.dig <- function(path1,path2) { require(xlsx) require(tidyverse) require(limma) require(edgeR) E<- read.xlsx (path1,sheetIndex 1,header 1) %>% column_to_rownames(var &…...

Keystone Automotive EDI 需求分析

Keystone Automotive 是一家知名的汽车零部件销售卖场&#xff0c;自创立以来&#xff0c;在汽车行业取得了卓越的成就。作为一家专业的汽车零部件供应商&#xff0c;Keystone Automotive 致力于为客户提供优质的产品和卓越的服务。公司的经营范围涵盖广泛&#xff0c;涉及多个…...

jmeter创建一个压测项目

1.jemeter新建一个项目&#xff1a; 2.接下来对Thread进行描述&#xff0c;也可以先使用默认的Thread进行操作。 3.添加http请求头的信息。按照如图所示操作 4.在请求头里面添加必要的字段&#xff0c;可以只填必要字段就可以 5.添加Http请求信息&#xff0c;如下图&#xff…...

CEC2013(MATLAB):淘金优化算法GRO求解CEC2013的28个函数

一、淘金优化算法GRO 淘金优化算法&#xff08;Gold rush optimizer&#xff0c;GRO&#xff09;由Kamran Zolf于2023年提出&#xff0c;其灵感来自淘金热&#xff0c;模拟淘金者进行黄金勘探行为。淘金优化算法&#xff08;Gold rush optimizer&#xff0c;GRO&#xff09;提…...

AI Deep Reinforcement Learning Autonomous Driving(深度强化学习自动驾驶)

AI Deep Reinforcement Learning Autonomous Driving&#xff08;深度强化学习自动驾驶&#xff09; 背景介绍研究背景研究目的及意义项目设计内容算法介绍马尔可夫链及马尔可夫决策过程强化学习神经网络 仿真平台OpenAI gymTorcs配置GTA5 参数选择行动空间奖励函数 环境及软件…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

电脑插入多块移动硬盘后经常出现卡顿和蓝屏

当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时&#xff0c;可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案&#xff1a; 1. 检查电源供电问题 问题原因&#xff1a;多块移动硬盘同时运行可能导致USB接口供电不足&#x…...

解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错

出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上&#xff0c;所以报错&#xff0c;到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本&#xff0c;cu、torch、cp 的版本一定要对…...

Android Bitmap治理全解析:从加载优化到泄漏防控的全生命周期管理

引言 Bitmap&#xff08;位图&#xff09;是Android应用内存占用的“头号杀手”。一张1080P&#xff08;1920x1080&#xff09;的图片以ARGB_8888格式加载时&#xff0c;内存占用高达8MB&#xff08;192010804字节&#xff09;。据统计&#xff0c;超过60%的应用OOM崩溃与Bitm…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...