当前位置: 首页 > 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 参数选择行动空间奖励函数 环境及软件…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》

引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

对WWDC 2025 Keynote 内容的预测

借助我们以往对苹果公司发展路径的深入研究经验&#xff0c;以及大语言模型的分析能力&#xff0c;我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际&#xff0c;我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测&#xff0c;聊作存档。等到明…...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

React19源码系列之 事件插件系统

事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

Linux离线(zip方式)安装docker

目录 基础信息操作系统信息docker信息 安装实例安装步骤示例 遇到的问题问题1&#xff1a;修改默认工作路径启动失败问题2 找不到对应组 基础信息 操作系统信息 OS版本&#xff1a;CentOS 7 64位 内核版本&#xff1a;3.10.0 相关命令&#xff1a; uname -rcat /etc/os-rele…...