当前位置: 首页 > 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…...

XCTF-web-easyupload

试了试php&#xff0c;php7&#xff0c;pht&#xff0c;phtml等&#xff0c;都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接&#xff0c;得到flag...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...