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

链表中环的入口节点

链表中环的入口节点

描述

链表中环的入口节点
给一个长度为n链表,若其中包含环,请找出该链表的环的入口结点,否则,返回null。

数据范围: n≤10000, 1<=结点值<=10000
要求:空间复杂度 O(1),时间复杂度 O(n)

解法一

解法一:有环的链表,在遍历时会在环中一直循环,想要获得环的入口结点,
直观地想,可以使用hash法保存出现的结点,当重复环的遍历过程时,第一次碰到重复的结点即为环入口结点B。

解法二

解法二:通过定义slow和fast指针,slow每走一步,fast走两步,若是有环,则一定会在环的某个结点处相遇(slow == fast),
根据下图分析计算,C为fast和slow指针第一次相遇的点。可知从C到B与从A到B以相同速度走第一次相遇的节点一定为B,即为入口点。解法二的实现,如下。
在这里插入图片描述

代码实现

public class Node<V> {public Node<V> pre;public Node<V> next;private V v;public Node(V v) {this.v = v;}public V getV() {return v;}public void setV(V v) {this.v = v;}
}
public static Node<Integer> entryNodeOfLoop(Node<Integer> head) {if (head == null || head.next == null){return null;}Node<Integer> fast = head;Node<Integer> slow = head;while (fast !=null && fast.next !=null){fast = fast.next.next;slow = slow.next;if (slow == fast){break;}}// 若是快指针指向null,则不存在环if(fast == null || fast.next == null)return null;// 重新指向链表头部fast = head;while (fast !=slow){fast = fast.next;slow = slow.next;}return fast;
}

从C到B与从A到B以相同速度走第一次相遇的节点一定为B?

在这里插入图片描述
我们用数学的方式证明一下。

如果结论:A到B走和C到B顺时针相同速度走,第一次相遇的点一定为B点。成立
那么数学表达式有 X = n(Y+Z)+Z  n>=0,n为环的圈数;的结论成立为证明A到B走和C到B顺时针相同速度走,第一次相遇的点一定为B点
即证明:X = n(Y+Z)+Z  n>=0;n为环的圈数由第一次相遇在C点得:2(X+Y) = X + w(Y+Z) + Y;(w>=1,w为环的圈数)
推导:==>  2(X+Y) = X + w(Y+Z) + Y + Z + Y;(w>=0,w为环的圈数)==>  2(X+Y) = X + w(Y+Z) + 2Y + Z;(w>=0,w为环的圈数)==>          X  = w(Y+Z) +Z ;(w>=0,w为环的圈数)所以:X = n(Y+Z)+Z  n>=0;n为环的圈数。成立即:A到B走和C到B顺时针相同速度走,第一次相遇的点一定为B点。

相关文章:

链表中环的入口节点

链表中环的入口节点 描述 链表中环的入口节点 给一个长度为n链表&#xff0c;若其中包含环&#xff0c;请找出该链表的环的入口结点&#xff0c;否则&#xff0c;返回null。 数据范围&#xff1a; n≤10000&#xff0c; 1<结点值<10000 要求&#xff1a;空间复杂度 O(1)…...

STL——函数对象,谓词

一、函数对象 1.函数对象概念 概念&#xff1a; 重载函数调用操作符的类&#xff0c;其对象常称为函数对象。 函数对象使用重载的()时&#xff0c;行为类似函数调用&#xff0c;也叫仿函数。 本质&#xff1a; 函数对象(仿函数)是一个类&#xff0c;不是一个函数。 2.函数对象…...

【区分vue2和vue3下的element UI Descriptions 描述列表组件,分别详细介绍属性,事件,方法如何使用,并举例】

在 Element UI&#xff08;为 Vue 2 设计&#xff09;和 Element Plus&#xff08;为 Vue 3 设计&#xff09;中&#xff0c;Descriptions&#xff08;描述列表&#xff09;组件通常用于展示一系列的结构化信息。然而&#xff0c;需要明确的是&#xff0c;Element UI 官方库中并…...

atcoder abc 358

A welcome to AtCoder Land 题目&#xff1a; 思路&#xff1a;字符串比较 代码&#xff1a; #include <bits/stdc.h>using namespace std;int main() {string a, b;cin >> a >> b;if(a "AtCoder" && b "Land") cout <&…...

手写docker:你先玩转namespace再来吧

哈喽&#xff0c;我是子牙老师。今天咱们聊聊Linux namespace 瓦特&#xff1f;你没听过namespace&#xff1f;那有必要科普一下了&#xff1a;namespace是Linux内核提供的一种软件性质的资源隔离机制。容器化技术&#xff0c;比如docker&#xff0c;就是基于这样的机制实现的…...

注册安全分析报告:PingPong

前言 由于网站注册入口容易被黑客攻击&#xff0c;存在如下安全问题&#xff1a; 暴力破解密码&#xff0c;造成用户信息泄露短信盗刷的安全问题&#xff0c;影响业务及导致用户投诉带来经济损失&#xff0c;尤其是后付费客户&#xff0c;风险巨大&#xff0c;造成亏损无底洞 …...

mysqladmin——MySQL Server管理程序(二)

mysqladmin 是一个命令行工具&#xff0c;用于执行简单的 MySQL 服务器管理任务&#xff0c;如检查服务器的状态、创建和删除数据库、重载权限等。 1 reload 重新加载授权表&#xff08;grant tables&#xff09;。当修改了MySQL的权限系统&#xff08;例如&#xff0c;修改了…...

Microsoft Edge无法启动搜索问题的解决

今天本来想清一下电脑&#xff0c;看到visual studio2022没怎么用了就打算卸载掉。然后看到网上有篇文章说进入C盘的ProgramFiles&#xff08;x86&#xff09;目录下的microsoft目录下的microsoft visual studio目录下的install目录中&#xff0c;双击InstallCleanup.exe&#…...

Appium Android 自动化测试 -- 元素定位

自动化测试元素定位是难点之一&#xff0c;编写脚本时会经常卡在元素定位这里&#xff0c;有时一个元素能捣鼓一天&#xff0c;到最后还是定位不到。 Appium 定位方式和 selenium 一脉相承&#xff0c;selenium 中的定位方式Appium 中都支持&#xff0c;而 Appium 还增加了自己…...

C#.net6.0+Vue+Ant-Design智慧医院手术麻醉系统源码 手术麻醉软件信息化管理系统 麻醉文书祥解

C#.net6.0VueAnt-Design智慧医院手术麻醉系统源码 手术麻醉软件信息化管理系统 麻醉文书祥解 医护人员通过手麻信息系统可以进行手术的预约申请、受理、安排&#xff0c;从门诊医生下医嘱到发起手术申请、护士长审核通过&#xff0c;均实现了全流程信息化管理&#xff0c;大大…...

6G时代,即将来临!

日前&#xff0c;由未来移动通信论坛、紫金山实验室主办的2024全球6G技术大会在南京召开。本次大会以“创新预见6G未来”为主题&#xff0c;在大会开幕式上发布了协力推进全球6G统一标准行动的倡议和紫金山科技城加速培育以6G技术引领未来产业行动计划。 在我国已开展第五代移动…...

进程、线程的区别

进程、线程的关系 开工厂生产手机&#xff0c;制作一条生产线&#xff0c;这个生产线上有很多的器件以及材料。一条生产线就是一个进程。 只有生产线是不够的&#xff0c;使用找五个工人来进行生产&#xff0c;这个工人能够利用这些材料最终一步步的将手机做出来&#xff0c;这…...

JWT详解、JWTUtil工具类的构建方法

一、前言 使用一些用户不友好的项目时&#xff0c;会发现&#xff0c;每一次进入网站&#xff0c;我们都要重新登录。 这是为什么呢&#xff1f; 现代多采用前后端分离的项目架构&#xff0c;这种架构&#xff0c;前后端使用不同的服务器&#xff0c;两个服务器上存储的信息不…...

江协科技51单片机学习- p11 静态数码管显示

前言&#xff1a; 本文是根据哔哩哔哩网站上“江协科技51单片机”视频的学习笔记&#xff0c;在这里会记录下江协科技51单片机开发板的配套视频教程所作的实验和学习笔记内容。本文大量引用了江协科技51单片机教学视频和链接中的内容。 引用&#xff1a; 51单片机入门教程-2…...

pandas.frame输出parquet

代码 import pandas as pd import pyarrow._parquet as pqdata pd.read_parquet("0000.parquet") total_rows len(data) half_row_num total_rows//2 print(half_row_num) first_half data.iloc[:20000] second_half data.iloc[20000:20000] # print(first_hal…...

【CT】LeetCode手撕—42. 接雨水

目录 题目1- 思路2- 实现⭐42. 接雨水——题解思路 3- ACM实现 题目 原题连接&#xff1a;42. 接雨水 1- 思路 模式识别&#xff1a;求雨水的面积 ——> 不仅是只求一个比当前元素大的元素&#xff0c;还要求面积 单调栈 应用场景&#xff0c;需要找到左边比当前元素大的…...

GPT-4o一夜被赶超,Claude 3.5一夜封王|快手可灵大模型推出图生视频功能|“纯血”鸿蒙大战苹果AI|智谱AI“钱途”黯淡|月之暗面被曝进军美国

快手可灵大模型推出图生视频功能“纯血”鸿蒙大战苹果AI&#xff0c;华为成败在此一举大模型低价火拼间&#xff0c;智谱AI“钱途”黯淡手握新“王者”&#xff0c;腾讯又跟渠道干上了“美食荒漠”杭州&#xff0c;走出一个餐饮IPOGPT-4o一夜被赶超&#xff0c;Anthropic推出Cl…...

C# + easyui 写的一个web项目

用C# easyui 来开发&#xff0c;其实就是为了开发速度&#xff0c;用easyui可以一天写很多页面&#xff0c;比一些低代码平台还快。 登陆页面 主界面 记录数统计 家庭信息采集表 新建家庭 家庭成员 低保、五保人员帮扶情况登记表 低保、五保人员帮扶情况登记表的新增和编辑 治…...

JVM 垃圾回收分配及算法

一、判断对象是否可以回收 垃圾收集器在做垃圾回收的时候&#xff0c;首先需要判定的就是哪些内存是需要被回收 的&#xff0c;哪些对象是「存活」的&#xff0c;是不可以被回收的&#xff1b;哪些对象已经「死掉」了&#xff0c;需 要被回收。 一般有两种方法来判断&#xff…...

尚品汇-(四)

&#xff08;1&#xff09;商品的基本知识 1.1基本信息—分类 一般情况可以分为两级或者三级。咱们的项目一共分为三级&#xff0c;即一级分类、二级分类、三级分类。 比如&#xff1a;家用电器是一级分类&#xff0c;电视是二级分类&#xff0c;那么超薄电视就是三级分类。…...

MongoDB学习和应用(高效的非关系型数据库)

一丶 MongoDB简介 对于社交类软件的功能&#xff0c;我们需要对它的功能特点进行分析&#xff1a; 数据量会随着用户数增大而增大读多写少价值较低非好友看不到其动态信息地理位置的查询… 针对以上特点进行分析各大存储工具&#xff1a; mysql&#xff1a;关系型数据库&am…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

.Net Framework 4/C# 关键字(非常用,持续更新...)

一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

iview框架主题色的应用

1.下载 less要使用3.0.0以下的版本 npm install less2.7.3 npm install less-loader4.0.52./src/config/theme.js文件 module.exports {yellow: {theme-color: #FDCE04},blue: {theme-color: #547CE7} }在sass中使用theme配置的颜色主题&#xff0c;无需引入&#xff0c;直接可…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...