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

【LeetCode】142.环形链表Ⅱ

题目

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。

提示:

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

解答

源代码

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast = head, slow = head;boolean flag = false;while (fast != null && fast.next != null) {fast = fast.next.next;slow = slow.next;if (fast == slow) {flag = true;break;}}if (!flag) {return null;}fast = head;while (fast != slow) {fast = fast.next;slow = slow.next;}return fast;}
}

总结

这题需要总结快指针慢指针走过路程的数学关系。

设快指针的路程为f,慢指针的路程为s,因为快指针每次经过两个节点,慢指针每次经过一个节点,则:

f = 2s

设链表非环形部分的节点数为a,环形部分的节点数为b,则:

f = a + k1b + c

s = a + k2b + c(c < b,k1 > k2)

结合以上两式可得:f = s + nb

那么:s = nb

由此我们可以知道慢指针路程为环形部分长度的整数倍,那么快慢指针相遇时,慢指针与环形部分入口处的距离就等于a。

相关文章:

【LeetCode】142.环形链表Ⅱ

题目 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返回 null。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链表中存在环。 为了表示给定链表中的环&#xff0c;评测系统内部…...

16.Netty源码之ChannelPipeline

highlight: arduino-light 服务编排层:ChannelPipeline协调ChannelHandlerHandler EventLoop可以说是 Netty 的调度中心&#xff0c;负责监听多种事件类型&#xff1a;I/O 事件、信号事件、定时事件等&#xff0c;然而实际的业务处理逻辑则是由 ChannelPipeline 中所定义的 Cha…...

“使用Spring Boot构建微服务应用的最佳实践“

标题&#xff1a;使用Spring Boot构建微服务应用的最佳实践 摘要&#xff1a;本文将介绍如何使用Spring Boot构建微服务应用的最佳实践。我们将讨论微服务架构的概念、Spring Boot的优势以及一些最佳实践&#xff0c;同时提供示例代码帮助读者更好地理解和实践。 正文&#x…...

redis高可用之主从复制,哨兵,集群

目录 前言 一、主从复制 1、主从复制的作用 2、主从复制流程 3、部署Redis 主从复制步骤 3.1 环境准备 3.3 修改Redis 配置文件(Master节点操作) 3.4 修改Redis 配置文件(Slave节点操作) 3.5 验证主从效果 二、哨兵 1、哨兵模式原理 2、哨兵模式…...

【Ajax】笔记-原生jsonp跨域请求案例

原生jsonp跨域请求 输入框&#xff1a;输入后&#xff0c;鼠标移开向服务端发送请求&#xff0c;返回用户不存在(直接返回不存在&#xff0c;不做判断) JS <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><me…...

QT--day2(信号与槽,多界面跳转)

第一个界面头文件&#xff1a; #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QIcon> //图标头文件 #include <QPushButton> //按钮类头文件QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public…...

热备份路由协议原理

热备份路由协议原理 HSRP协议/VRRP协议热备份协议 热备份协议&#xff08;Hot Standby Protocol&#xff09; 是一种基于冗余设计的协议&#xff0c;用于提高网络的可靠性和冗余性。它允许多个设备共享同一个IP地址&#xff0c;其中一个设备被选为主设备&#xff0c;其他设备…...

模拟实现定时器

关于java标准库中的定时器的使用可以看定时器Timer的使用 大致思路 定义一个MyTimeTask类&#xff0c;该类用于组织要执行任务的内容以及执行任务的时间戳&#xff0c;后面要根据当前系统时间以及执行任务的时间戳进行比较&#xff0c;来判断是否要执行任务或是要等待任务 用一…...

TCP/IP的分包粘包

TCP/IP的分包粘包 分包粘包介绍导致分包粘包的原因导致TCP粘包的原因&#xff1a;导致TCP分包的原因&#xff1a;避免分包粘包的措施 分包粘包介绍 因为TCP为了减少额外开销&#xff0c;采取的是流式传输&#xff0c;所以接收端在一次接收的时候有可能一次接收多个包。而TCP粘…...

盘点:查快递教程

在“寄快递”成为常态的当下&#xff0c;如何快速进行物流信息查询&#xff0c;是收寄人所关心的问题。在回答这个问题之前&#xff0c;首先我们要知道&#xff0c;物流信息查询&#xff0c;有哪些方法&#xff1f; 1、官网单号查询 知道物流公司和单号的情况下&#xff0c;直…...

TransGPT 开源交通大模型开源

TransGPT 是开源交通大模型&#xff0c;主要致力于在真实交通行业中发挥实际价值。 它能够实现交通情况预测、智能咨询助手、公共交通服务、交通规划设计、交通安全教育、协助管理、交通事故报告和分析、自动驾驶辅助系统等功能。 TransGPT 作为一个通用常识交通大模型&#…...

gitignore文件使用方法(gitignore教程)(git status --ignored)(git check-ignore -v <file>)

文章目录 Gitignore文件使用描述Gitignore基本语法1. 基本语法★★★★★2. 配置方法 匹配示例示例1示例2示例3 其他命令git status --ignored&#xff08;用于显示被Git忽略的文件和文件夹的状态&#xff09;git check-ignore -v <file>&#xff08;用于检查指定文件是否…...

mybatis拼接sql导致的oom报错 GC报错

报错1&#xff1a;mybatis拼接过多 java.lang.OutOfMemoryError: GC overhead limit exceeded 具体报错&#xff1a; nested exception is org.apache.ibatis.builder.BuilderException: Error evaluating expression ew.sqlSegment ! null and ew.sqlSegment ! and ew.non…...

如何通俗理解扩散模型?

扩散模型(Diffusion Model)是一类十分先进的基于扩散思想的深度学习生 成模型。生成模型除了扩散模型之外&#xff0c;还有出现较早的 VAE ( Variational Auto- Encoder&#xff0c;变分自编码器) 和 GAN ( Generative Adversarial Net &#xff0c;生成对抗网络) 等。 虽然它们…...

【C#】并行编程实战:并行编程中的模式

本章将介绍并行编程模式&#xff0c;重点是理解并行代码问题场景并使用并行编程/异步技术解决他们。本章会介绍几种最重要的编程模式。 本教程学习工程&#xff1a;魔术师Dix / HandsOnParallelProgramming GitCode 1、MapReduce 模式 引入 MapReduce 是为了解决处理大数据的问…...

Apache Kafka 入门教程

Apache Kafka 入门教程 一、简介简介架构 二、Kafka 安装和配置JDK安装 Kafka配置文件详解 三、Kafka 的基本操作启动和关闭Topic 创建和删除Partitions 和 Replication 配置Producer 和 Consumer 使用方法ProducerConsumer 四、Kafka 高级应用消息的可靠性保证Kafka StreamKaf…...

python皮卡丘编程代码教程,用python打印皮卡丘

大家好&#xff0c;小编来为大家解答以下问题&#xff0c;如何用print函数打印一只皮卡丘&#xff0c;用python如何打印丘比特之心&#xff0c;现在让我们一起来看看吧&#xff01;...

shell脚本:数据库的分库分表

#!/bin/bash ######################### #File name:db_fen.sh #Version:v1.0 #Email:admintest.com #Created time:2023-07-29 09:18:52 #Description: ########################## MySQL连接信息 db_user"root" db_password"RedHat123" db_cmd"-u${…...

AtCoder Beginner Contest 312(A~D)

A //语法题也要更仔细嘞&#xff0c;要不然也会wa #include <bits/stdc.h> // #pragma GCC optimize(3,"Ofast","inline") // #pragma GCC optimize(2) using namespace std; typedef long long LL; #define int LL typedef pair<int, int> …...

SQL中Partition的相关用法

使用Partition可以根据指定的列或表达式将数据分成多个分区。每个分区都是逻辑上独立的&#xff0c;可以单独进行查询、插入、更新和删除操作。Partition可以提高查询性能&#xff0c;因为它可以限制在特定分区上执行查询&#xff0c;而不是在整个表上执行。 在SQL中&#xff…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

【Java学习笔记】Arrays类

Arrays 类 1. 导入包&#xff1a;import java.util.Arrays 2. 常用方法一览表 方法描述Arrays.toString()返回数组的字符串形式Arrays.sort()排序&#xff08;自然排序和定制排序&#xff09;Arrays.binarySearch()通过二分搜索法进行查找&#xff08;前提&#xff1a;数组是…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

CMake基础:构建流程详解

目录 1.CMake构建过程的基本流程 2.CMake构建的具体步骤 2.1.创建构建目录 2.2.使用 CMake 生成构建文件 2.3.编译和构建 2.4.清理构建文件 2.5.重新配置和构建 3.跨平台构建示例 4.工具链与交叉编译 5.CMake构建后的项目结构解析 5.1.CMake构建后的目录结构 5.2.构…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

9-Oracle 23 ai Vector Search 特性 知识准备

很多小伙伴是不是参加了 免费认证课程&#xff08;限时至2025/5/15&#xff09; Oracle AI Vector Search 1Z0-184-25考试&#xff0c;都顺利拿到certified了没。 各行各业的AI 大模型的到来&#xff0c;传统的数据库中的SQL还能不能打&#xff0c;结构化和非结构的话数据如何和…...