算法系列-力扣876-求链表的中间节点
# 求链表中间节点,如果有两个中间节点取后面那个
链表定义
```
// @lc code=start
/**
* 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; }
* }
*/
```
方法一:计数取一半
解题方法:
先计算链表一共有多少个节点n
n/2,得到中间节点的下标(从0开始)
1 -> 2 -> 3 -> 4 -> 5
坐标节点就是链表的中间节点
时间复杂度:O(n)
空间复杂度:O(1)
```
public ListNode middleNode(ListNode head) {
/**
* 先计算链表一共有多少个节点n
* n/2,得到中间节点的下标(从0开始)
* 1 -> 2 -> 3 -> 4 -> 5
* 坐标节点就是链表的中间节点
* */
int n=0;
ListNode p=head;
while (p!=null){
n++;
p=p.next;
}
int mid=n/2;
ListNode midNode=head;
for (int i = 0; i < mid; i++) {
midNode=midNode.next;
}
return midNode;
}
```
方法二:双指针
解题方法:
定义快慢两个指针,快指针每次移动2步,慢指针每次移动1步
注意:指针需要从头节点前开始移动,因此需要定义一个哑结点,快指针和慢指针都从哑节点开始
当快指针移动了2k步后,慢指针移动了k步
假设2k=n,k=n/2
当n为偶数时,慢指针的后续节点就是中间节点
当n为奇数时,慢指针就是中间节点
是否是偶数节点看快指针每次是否都能移动两步
时间复杂度:O(n)
空间复杂度:O(1)
```
public ListNode middleNode(ListNode head) {
/**
* 定义快慢两个指针,快指针每次移动2步,慢指针每次移动1步
* 注意:指针需要从头节点前开始移动,因此需要定义一个哑结点,快指针和慢指针都从哑节点开始
* 当快指针移动了2k步后,慢指针移动了k步
* 假设2k=n,k=n/2
* 当n为偶数时,慢指针的后续节点就是中间节点
* 当n为奇数时,慢指针就是中间节点
* 是否是偶数节点看快指针每次是否都能移动两步
* -1 -> 1 -> 2 -> 3 -> 4 -> 5 -> null
* -1 -> 1 -> 2 -> 3 -> 4 -> null
* */
if(head == null){
return null;
}
ListNode dummy = new ListNode(-1);
dummy.next=head;
ListNode slow=dummy;
ListNode fast=dummy;
ListNode midNode=null;
Boolean isEvent=true;
while (fast.next!=null){
slow=slow.next;
if(fast.next.next!=null) {
fast = fast.next.next;
} else{
fast=fast.next;
isEvent=false;
}
}
midNode = isEvent ? slow.next : slow;
return midNode;
}
```
方法三:双指针优化
解题方法:
定义快慢两个指针,快指针每次移动2步,慢指针每次移动1步
快指针和慢指针都从头节点开始移动
当快指针移动到链尾时,慢指针移动了k步,n>1
当n为偶数时,n-1必然是奇数
即快指针移动了2(k-1)+1步
此时快慢指针距离原点距离
快2(k-1)+1+1 简化 2k
慢k+1
即慢指针正好处于链表中间位置。
当n为奇数时,n-1必然是偶数
,快指针移动了2k步
此时快慢指针距离原点距离
2k+1
k+1
即慢指针正好处于链表中间位置
时间复杂度:O(n)
空间复杂度:O(1)
方法二的本质是下面的公式:
偶数
快2k
慢k
中间k+1
奇数
快2k-1
慢k
中间k
即快慢指针的初始位置+1就把公式统一了。
```
public ListNode middleNode(ListNode head) {
if(head == null){
return null;
}
ListNode slow=head;
ListNode fast=head;
while (fast!=null && fast.next!=null){
slow=slow.next;
fast = fast.next.next;
}
return slow;
}
```
相关文章:
算法系列-力扣876-求链表的中间节点
# 求链表中间节点,如果有两个中间节点取后面那个 链表定义 // lc codestart /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * …...
SpringBoot集成Redis、Redisson保姆教程【附源码】
1. SpringBoot集成Redis 关于Redis的安装,这里就不重复介绍了,需要的朋友可以看我之前的博文Redis多系统安装(Windows、Linux、Ubuntu) Redis原生命令大全,作者整理的很详细,大部分命令转化为java命令基本也是关键词 Redis 命令参考 接下来开始我们的正题,一起学习下…...
c++多线程中常用的使用方法
1)promise(保证)和future的联合使用,实现两个线程的数据传递 #include <iostream> #include<thread> #include<future>using namespace std;//promise用法:可以给线程一个值,而从另一个线程读出该值 // 实现了两个线程的数…...
【dart】dart基础学习使用(一):变量、操作符、注释和库操作
前言 学习dart语言。 注释 Dart 支持单行注释、多行注释和文档注释。 单行注释 单行注释以 // 开头。Dart 编译器将忽略从 // 到行尾之间的所有内容。 void main() {// 这是单行注释print(Welcome to my Llama farm!); }多行注释 多行注释以 /* 开始,以 / 结…...
element-plus 设置 el-date-picker 弹出框位置
前言 概述:el-date-picker 组件会自动根据空间范围进行选择比较好的弹出位置,但特定情况下,它自动计算出的弹出位置并不符合我们的实际需求,故需要我们手动设置。 存在的问题:element-plus 中 el-date-picker 文档中并…...
C++day7(auto关键字、lambda表达式、C++中的数据类型转换、C++标准模板库(STL)、list、文件操作)
一、Xmind整理: 关键词总结: 二、上课笔记整理: 1.auto关键字 #include <iostream>using namespace std;int fun(int a, int b, float *c, char d, double *e,int f) {return 12; }int main() {//定义一个函数指针,指向fu…...
纽扣电池/锂电池UN38.3安全检测报告
根据规章要求,航空公司和机场货物收运部门应对锂电池进行运输文件审查,重要的是每种型号的锂电池UN38.3安全检测报告。该报告可由的三方检测机构。如不能提供此项检测报告,将禁止锂电池进行航空运输. UN38.3包含产品:1、 锂电池2…...
K8S:K8S自动化运维容器Docker集群
文章目录 一.k8s概述1.k8s是什么2.为什么要用K8S3.作用及功能4.k8s容器集群管理系统 二.K8S的特性1.弹性伸缩2.自我修复3.服务发现和复制均衡4.自动发布和回滚5.集中化配置管理和秘钥管理6.存储编排7.任务批量处理运行 三.K8S的集群架构四.K8S的核心组件1.Master组件࿰…...
Java的guava 限流写法
第一步先引入 maven <dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>32.0.1-jre</version> </dependency> 然后上方法 private final double rateLimiter10 1.0 / 10.0; // 每…...
[uniapp] scroll-view 简单实现 u-tabbar效果
文章目录 方案踩坑1.scroll-view 横向失败2.点击item不滚动?3. scrollLeft从哪里来? 效果图 方案 官方scroll-view 进行封装 配合属性 scroll-left Number/String 设置横向滚动条位置 即可 scroll-into-view 属性尝试过,方案较难实现 踩坑 1.scroll-view 横向失败 安装…...
vue常见问题汇总
来源:https://www.fly63.com/ Q1:安装超时(install timeout) 方案有这么些: cnpm : 国内对npm的镜像版本/*cnpm website: https://npm.taobao.org/*/npm install -g cnpm --registryhttps://registry.npm.taobao.org// cnpm 的大多命令跟 npm 的是一致的…...
GPT-3在化学中进行低数据发现是否足够?
今天介绍一份洛桑联邦理工学院进行的工作,这份工作被发表在化学期刊预印本网站上。 对于这份工作,有兴趣的朋友可以通过我们的国内ChatGPT镜像站进行测试使用,我们的站点并没有针对特定任务进行建设,是通用性质的。 化学领域进行…...
gitlab升级
1.下载需要的版本 wget -c https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el7/gitlab-ce-15.7.6-ce.0.el7.x86_64.rpm --no-check-certificate gitlab-ce-15.4.6-ce.0.el7.x86_64.rpm gitlab-ce-15.7.6-ce.0.el7.x86_64.rpm gitlab-ce-15.9.7-ce.0.el7.x86_64.rpm g…...
Matlab图像处理-灰度插值法
最近邻法 最近邻法是一种最简单的插值算法,输出像素的值为输入图像中与其最邻近的采样点的像素值。是将(u0,v0)(u_0,v_0)点最近的整数坐标u,v(u,v)点的灰度值取为(u0,v0)(u_0,v_0)点的灰度值。 在(u0,v0)(u_0,v_0)点各相邻像素间灰度变化较小时,这种方…...
axios 或 fetch 如何实现对发出的请求的终止?
终止 HTTP 请求是一个重要的功能,特别是在需要优化性能、避免不必要的请求或在某些事件发生时(例如用户点击取消)中断正在进行的请求时。以下是如何使用 axios 和 fetch 实现请求终止的方法: 1. axios axios 使用了 CancelToken…...
ChatGPT Prompting开发实战(四)
一、chaining prompts应用解析及输出文本的设定 由于输入和输出都是字符串形式的自然语言,为了方便输入和输出信息与系统设定使用的JSON格式之间进行转换,接下来定义从输入字符串转为JSON list的方法: 定义从JSON list转为输出字符串的方法&…...
Windows和Linux环境中安装Zookeeper具体操作
1.Windows环境中安装Zookeeper 1.1 下载Zookeeper安装包 ZooKeeper官网下载地址 建议下载稳定版本的 下载后进行解压后得到如下文件: 1.2 修改本地配置文件 进入解压后的目录,将zoo_example.cfg复制一份并重命名为zoo.cfg,如图所示: 打…...
41、Flink之Hive 方言介绍及详细示例
Flink 系列文章 1、Flink 部署、概念介绍、source、transformation、sink使用示例、四大基石介绍和示例等系列综合文章链接 13、Flink 的table api与sql的基本概念、通用api介绍及入门示例 14、Flink 的table api与sql之数据类型: 内置数据类型以及它们的属性 15、Flink 的ta…...
docker环境安装软件、更换镜像源以及E: Unable to locate package xxx解决
docker环境安装vim、ifconfig、ping、更换镜像源以及E: Unable to locate package vim 一. E: Unable to locate package vim 问题解决一、问题分析二、解决方案三、再次安装四. 此镜像源已失效 二. 解决 “E: 仓库xx没有 Release 文件。N: 无法安全地用该源进行更新࿰…...
夸克扫描王App用上了AI大模型 让扫描更清楚、提取文字更方便
对上班族来说,找到一个好用的工具类APP,绝对可以提升工作效率。比如最常见的扫描文件,公司的扫描仪虽然好用但是很难进行深度编辑且不能外出使用;很多手机App也有扫描功能,但技术能力总是差一点,当面对复杂…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
Python:操作 Excel 折叠
💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...
(二)原型模式
原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
面向无人机海岸带生态系统监测的语义分割基准数据集
描述:海岸带生态系统的监测是维护生态平衡和可持续发展的重要任务。语义分割技术在遥感影像中的应用为海岸带生态系统的精准监测提供了有效手段。然而,目前该领域仍面临一个挑战,即缺乏公开的专门面向海岸带生态系统的语义分割基准数据集。受…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
NPOI Excel用OLE对象的形式插入文件附件以及插入图片
static void Main(string[] args) {XlsWithObjData();Console.WriteLine("输出完成"); }static void XlsWithObjData() {// 创建工作簿和单元格,只有HSSFWorkbook,XSSFWorkbook不可以HSSFWorkbook workbook new HSSFWorkbook();HSSFSheet sheet (HSSFSheet)workboo…...
