深圳方维网站建设/免费个人自助建站
求链表中间节点,如果有两个中间节点取后面那个
链表定义
// @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; }* ListNode(…...

h5 ws 客户端 监听ws服务器广播的信息
<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>AI智能写作</title><!-- Bootstrap CSS --><meta charset"utf-8"><meta name"viewport" content"widt…...

网络基础之重中之重
目录 IP协议 编辑 基本概念: 协议头格式: 编辑 网段划分 DHCP : CIDR: 特殊的IP地址: IP地址的数量限制: 私有IP和公网IP 路由 路由的过程: 数据链路层 认识以太网&#x…...

HarmonyOS应用开发者-----基础认证试题及答案
HarmonyOS应用开发者基础认证试题及答案 试题会不定时刷新,本试题仅供大家学习参考 【判断题】 2.5/2.5 所有使用@Component修饰的自定义组件都支持onPageShow,onBackPress和onPageHide生命周期函数。 正确(True)错误(False) 回答正确【判断题】 2.5/2.5 在Column和Row容器组…...

C++:string并非以0作为结束符,c_str和data的返回却包含结束符0
C语言中使用char数组保存字符串时,是以字符为0或者\0作为字符串的结束符标志的。 所以一个char str[10]的数组只能合法的保存9个字符(因为最后还要加一个结束符)。 #include <cstring> #include <iostream>using namespace std;int main() {char str[10] ="…...

ChatGPT插件的优缺点
虽然西弗吉尼亚大学的研究人员看到了最新的官方ChatGPT插件——名为“代码解释器”( Code Interpreter)的教育应用潜力,但他们也发现,对于使用计算方法处理针对癌症和遗传疾病的定向治疗的生物数据的科学家来说,这款插…...

北京985学校,交叉学科考英一数三408
北京师范大学(B) 考研难度(☆☆☆) 内容:23考情概况(拟录取和复试分析)、院校概况、23专业目录、23复试详情、各专业考情分析、各科目考情分析。 正文1096字,预计阅读:3分钟 2023考情概况 北…...

ChatGPT 总结前端HTML, JS, Echarts都包含哪些内容
AIGC ChatGPT ,BI商业智能, 可视化Tableau, PowerBI, FineReport, 数据库Mysql Oracle, Office, Python ,ETL Excel 2021 实操,函数,图表,大屏可视化 案例实战 http://t.csdn.cn/zBytu...

企业架构LNMP学习笔记1
项目开发流程: 公司老板或者产品经理,根据市场调查,决定开发一整套互联网产品。 互动社交电商用户论坛(BBS) 产品决策 (老板产品UI设计) 业务实施、代码开发 程序开发人员 前端开发&#x…...

【位运算】leetcode371:两整数之和
一.题目描述 两整数之和 二.思路分析 题目要求我们实现两整数相加,但是不能使用加号,应该立马想到是用位运算来解决问题。之前说过,异或就是“无进位相加”,故本题可以先将两数异或,然后想办法让得到的结果进位即可。…...

【爬虫小知识】如何利用爬虫爬网页——python爬虫
前言 网络时代的到来,给我们提供了海量的信息资源,但是,想要获取这些信息,手动一个一个网页进行查找,无疑是一项繁琐且效率低下的工作。这时,爬虫技术的出现,为我们提供了一种高效的方式去获取…...

什么是跨域问题 ?Spring MVC 如何解决跨域问题 ?Spring Boot 如何解决跨域问题 ?
目录 1. 什么是跨域问题 ? 2. Spring MVC 如何解决跨域问题 ? 3. Spring Boot 如何解决跨域问题 ? 1. 什么是跨域问题 ? 跨域问题指的是不同站点之间,使用 ajax 无法相互调用的问题。 跨域问题的 3 种情况&#x…...

线性代数的学习和整理17:向量空间的基,自然基,基变换等(未完成)
目录 3 向量空间的基:矩阵的基础/轴 3.1 从颜色RGB说起 3.2 附属知识 3.3 什么样的向量可以做基? 3.4 基的分类 3.1.1 不同空间的基---向量组的数量可能不同 3.1.2 自然基 3.1.3 正交基 3.1.4 标准正交基 3.1.5 基和向量/矩阵 3.1.6 基变换 …...

Java中支持分库分表的框架/组件/中间件简介
文章目录 1 sharding-jdbc2 TSharding3 Atlas4 Cobar5 MyCAT6 TDDL7 Vitess 列举一些比较常见的,简单介绍一下: sharding-jdbc(当当) TSharding(蘑菇街) Atlas(奇虎360) Cobar&#…...

7.2 项目2 学生通讯录管理:文本文件增删改查(C 版本)(自顶向下设计+断点调试) (A)
C自学精简教程 目录(必读) 该作业是 作业 学生通讯录管理:文本文件增删改查(C版本) 的C 语言版本。 具体的作业题目描述,要求,可以参考 学生通讯录管理:文本文件增删改查(C版本)。…...

excel怎么设置任意选一个单元格纵横竖横都有颜色
有时excel表格内容过多的时候,我们通过excel设置任意选一个单元格纵横,竖横背景颜色,这样会更加具有辨识度。设置方式截图如下 设置成功后,预览的效果图...

期货-股票交易规则
交易时间 港股:9:00~9:20 集合竞价,9:3012:00,13:0016:00 持续交易,16:00~16:10 随机收市竞价沪股:9:00~9:25 集合竞价,9:3011:30,13:0015:00 持续交易,11:30~12:00 交易申报深股&a…...

Makefile一些语法
ifneq($(filter true,$(xxx)), )的含义 filter 是过滤的意思,它的原型是:$(filter PATTERN…,TEXT), 意义为:过滤掉字串“TEXT”中所有不符合模式“PATTERN”的单词,保留所有符合此模式的单词做返回值。 结合前面的if…...

0基础可以转行编程行业么
在2022年分行业门类分岗位就业人员年平均工资中,信息传输、软件和信息技术服务业的薪资遥遥领先其他行业,为全国平均薪资水平的 1.78 倍,远超第二名金融行业,其年增长率在9.4%,并成为年收入首个过20 万门槛的行业&…...

【spark】dataframe慎用limit
官方:limit通常和order by一起使用,保证结果是确定的 limit 会有两个步骤: LocalLimit ,发生在每个partitionGlobalLimit,发生shuffle,聚合到一个parttion 当提取的n大时,第二步是比较耗时的…...

基于OpenCV+LPR模型端对端智能车牌识别——深度学习和目标检测算法应用(含Python+Andriod全部工程源码)+CCPD数据集
目录 前言总体设计系统整体结构图系统流程图 运行环境Python 环境OpenCV环境Android环境1. 开发软件和开发包2. JDK设置3. NDK设置 模块实现1. 数据预处理2. 模型训练1)训练级联分类器2)训练无分割车牌字符识别模型 3. APP构建1)导入OpenCV库…...

C++学习6
C学习6 基础知识std::thread 实战boost domain socket server 基础知识 std::thread std::thread是C11标准库中的一个类,用于创建并发执行的线程。它的详细用法如下: 头文件 #include <thread>创建线程 std::thread t(func, args...);其中&am…...

bazel使用中存在的问题
只开远端缓存时。kernel采用的bazel编译,遇到如下问题: 1、Action 详情二进制文件解析为文本文件时报错,无法进一步比较分析导致缓存不命中的原因。--- JDK版本的问题 2、远端缓存全部命中时间收益不明显 ---需分析是否为网络原因 3、$HOM…...

svn软连接和文件忽略
软连接 1)TortoiseSVN->Properties->New->Externals->New 2)填入软连接信息 Local path: 写下软连接后的文件夹的名字 URL: 想要软连接的牡蛎->TortoiseSVN->Repo-browser 复制下填入 文件忽略 以空格隔开就行...

自动驾驶攻城战,华为小鹏先亮剑
点击关注 文|刘俊宏 编|苏扬、王一粟 本文为光锥智能x腾讯科技联合出品 2023年过半,城市NOA(城市领航辅助驾驶)的元年如预期中到来了吗? 8月25日,成都车展开幕,与4个月之前的上海…...

企业供应链数字化怎么做?企业数字化供应链流程落地方式
什么是供应链?简单来说,供应链是围绕客户需求,以提高产品流通各个环节的效率为目标,通过资源整合的方式来实现产品从设计、生产到销售、服务整个环节的组织形态。如同人工智能、区块链、5G等技术的发展带来的各种行业变化…...

java八股文面试[多线程]——synchronized 和lock的区别
其他差别: synchronized是隐式的加锁,lock是显式的加锁; synchronized底层采用的是objectMonitor,lock采用的AQS; synchronized在进行加锁解锁时,只有一个同步队列和一个等待队列, lock有一个同步队列,可以有多个等待队列; synchronized使用了object类的wait和noti…...

实现一个简单的控制台版用户登陆程序, 程序启动提示用户输入用户名密码. 如果用户名密码出错, 使用自定义异常的方式来处理
//密码错误异常类 public class PasswordError extends Exception {public PasswordError(String message){super(message);} }//用户名错误异常类 public class UserError extends Exception{public UserError(String message){super(message);} }import java.util.Scanner;pu…...

Java 大厂八股文面试专题-设计模式 工厂方法模式、策略模式、责任链模式
面试专题-设计模式 前言 在平时的开发中,涉及到设计模式的有两块内容,第一个是我们平时使用的框架(比如spring、mybatis等),第二个是我们自己开发业务使用的设计模式。 面试官一般比较关心的是你在开发过程中ÿ…...

Anaconda Prompt输入jupyter lab无反应
问题:Anaconda Prompt界面输入指令无反应 原因:公司电脑勒索病毒防御工具阻止了进程 解决:找到黑名单恢复进程...