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

LeetCode--HOT100题(26)

目录

  • 题目描述:142. 环形链表 II(中等)
    • 题目接口
    • 解题思路
    • 代码
  • PS:

题目描述:142. 环形链表 II(中等)

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

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

LeetCode做题链接:LeetCode-环形链表 II

示例 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 或者链表中的一个有效索引

进阶: 你是否可以使用 O(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) {}
}

解题思路

参考题解:环形链表 II(双指针法,清晰图解)
遇到这种环相遇的问题,第一时间就考虑快慢指针的方法,如果没接触过这类问题,可以看我另一篇文章:环形链表
下面思路是在你理解了判断链表中是否有环的问题的基础上来说的
思路:
在这里插入图片描述

  • 假设有环,环的长度为b,起始位置到环的起点为a,
  • slow走1步,fast走2步,第一相遇的时候 f = 2s(slow = s,fast = f),因为fast是slow的两倍嘛
  • fast 比 slow多走了 n 个环的长度,所以 f = s + nb (快慢指针都走过前面的a步了,重合时,快指针就比慢指针多走n圈)
  • 上面两式相减s = nb,f = 2nb
  • 有图可知:走a+nb步一定是在环入口,有上式可知:第一次相遇时慢指针已经走了nb
  • 我们需要再走慢指针再走a步就到环入口,而快指针怎么办?答案是置于head位置,也是再走a步就到环入口
  • 所以可以一起走a步,最终快慢指针相等的位置就是环入口位置了

具体步骤:

  • 先构建一次相遇,慢指针走一步,快指针走两步,如果有环,最终在环中相遇
  • 接着构建第二次相遇,慢指针位置不变,快指针位置置为head(也就是起始位置)
  • 然后快慢指针现在都是同时走一步,直到相遇,相遇的位置就是环的起始结点

代码

/*** 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) {if (head == null) {return null;}// 快慢指针都从head开始ListNode slow = head;ListNode fast = head;do {if (fast == null || fast.next == null) {return null;}// 快慢指针的移动slow = slow.next;fast = fast.next.next;} while (slow != fast); // 快慢指针相遇则退出// 将快指针置于head(开头),慢指针不变,还是在环中fast = head;// 快慢指针再次相遇就是环起始节点while (fast != slow) {// 快慢指针的移动,现在都是一格一格移动(快指针不再移动两个格)fast = fast.next;slow = slow.next;}return fast;}
}

在这里插入图片描述

PS:

感谢您的阅读!如果您觉得本篇文章对您有所帮助,请给予博主一个喔~

相关文章:

LeetCode--HOT100题(26)

目录 题目描述&#xff1a;142. 环形链表 II&#xff08;中等&#xff09;题目接口解题思路代码 PS: 题目描述&#xff1a;142. 环形链表 II&#xff08;中等&#xff09; 给定一个链表的头节点 head &#xff0c;返回链表开始入环的第一个节点。 如果链表无环&#xff0c;则返…...

HTTP 请求方法详解

HTTP 请求方法详解 请求方法 请求方法&#xff08;Request Methods&#xff09;是在 HTTP 请求中用于指定对目标资源执行的操作类型。每个请求都需要指定一个请求方法&#xff0c;以告知服务器要执行的操作。 以下是一些常见的 HTTP 请求方法及其主要用途&#xff1a; GET&…...

孤立随机森林(Isolation Forest)(Python实现)

目录 1 简介 2 孤立随机森林算法 2.1 算法概述 2.2 原理介绍 2.3 算法步骤 3 参数讲解 4 Python代码实现 5 结果 1 简介 孤立森林&#xff08;isolation Forest&#xff09;是一种高效的异常检测算法&#xff0c;它和随机森林类似&#xff0c;但每次选择划分属性和划…...

小程序如何自定义分享内容

小程序项目中遇到门票转增功能&#xff0c;用户可将自己购买的门票分享给好友&#xff0c;好友成功领取即得门票一张 1.自定义分享按钮 通过button里的open-type属性里的share参数即自可定义分享按钮 <button open-type"share">分享</button>2.配置分…...

SpringBoot整合WebSocket详解

环境&#xff1a;Springboot3.0.5 WebSocket介绍 WebSocket协议RFC 6455提供了一种标准化的方式&#xff0c;通过一个TCP连接在客户端和服务器之间建立全双工、双向的通信通道。它是一个不同于HTTP的TCP协议&#xff0c;但设计为在HTTP之上工作&#xff0c;使用80和443端口&am…...

伪原创神码ai怎么样【php源码】

这篇文章主要介绍了python汉化补丁包下载&#xff0c;具有一定借鉴价值&#xff0c;需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获&#xff0c;下面让小编带着大家一起了解一下。 火车头采集ai伪原创插件截图&#xff1a; ** Spyder汉化&#xff08;python汉化&…...

Air001基于Keil环境开发,使用airisp串口命令行烧录

Air001基于Keil环境开发&#xff0c;使用airisp串口命令行烧录 有人会有这样的疑惑&#xff0c;使用Keil平台开发&#xff0c;为什么不直接使用CMSIS-DAP直接烧录&#xff0c;还要使用串口方式来去单独烧录&#xff0c;不是我不想&#xff0c;目前使用合宙官方的Air103芯片版本…...

kubernetes 中的事件(event)简介以及如何收集event和基于event告警

引用另外一篇文章对k8s event的介绍 1.什么是kubernetes事件 Kubernetes Events 是一种 Kubernetes 资源对象&#xff0c;记录了某个组件在某个时间做了某个动作&#xff0c;用于展示集群内发生的情况&#xff0c;当 Kubernetes 集群中资源状态发生变化时&#xff0c;可以产生…...

C++小游戏贪吃蛇源码

graphics.h是针对DOS下的一个C语言图形库 (c也可以) 目前支持下载此头文件的常用的有两种: 1. EGE (Easy Graphics Engine)2. EasyX Graphics LibraryEGE, 全名Easy Graphics Engine, 是windows下的简易绘图库&#xff0c;是一个类似BGI(graphics.h)的面向C/C语言新手的图形库…...

【密码学】穴居人密码

穴居人密码 文字记载中&#xff0c;有时会把来自古希腊文化之前的各种记录作为密码学的例子&#xff0c;但称它们为密码学一定太不严格了&#xff0c;这是因为那些方法都太原始了。密码学的起源能追溯到多早&#xff0c;取决于你把密码学的相关定义确定得有多宽泛。大多数作者都…...

neo4j的CQL命令实例演示

天行健&#xff0c;君子以自强不息&#xff1b;地势坤&#xff0c;君子以厚德载物。 每个人都有惰性&#xff0c;但不断学习是好好生活的根本&#xff0c;共勉&#xff01; 文章均为学习整理笔记&#xff0c;分享记录为主&#xff0c;如有错误请指正&#xff0c;共同学习进步。…...

vue3+ts使用antv/x6

使用 2.x 版本 x6.antv 新官网: 安装 npm install antv/x6 //"antv/x6": "^2.1.6",项目结构 1、初始化画布 index.vue <template><div id"container"></div> </template><script setup langts> import { onM…...

wsl1 ubuntu通过宿主机代理连接外网

文章目录 环境变量配置apt换源apt安装&#xff0c;测试是否能通外网可能出现的问题&#xff1a;Temporary failure resolving 参考 背景&#xff1a;公司电脑是局域网&#xff0c;通过走代理来连接外网 wsl1 ubuntu想要通过来连接宿主机的局域网代理&#xff0c;访问外网 可以…...

ubuntu20.04 opencv4.2 安装笔记

参考&#xff1a; https://docs.opencv.org/4.x/d7/d9f/tutorial_linux_install.html Build with opencv_contrib # 1. Install minimal prerequisites&#xff0c; libgtk2.0-dev pkg-config 用来显示图像 sudo apt update && sudo apt install -y cmake g wget un…...

ubuntu安装nginx以及php的部署

目录 1.安装依赖包 2.安装nginx 3.编译nginx 4.启动nginx 5.访问nginx 6.增加源地址 7.安装php 8.配置php-fpm 9.修改权限 10.配置nginx里的php 11.启动php-fpm 12.配置php文件以及权限 13.登陆查看 1.安装依赖包 apt-get install gcc apt-get install libpcre3 l…...

IntelliJ IDEA 2021/2022关闭双击shift全局搜索

我这里演示的是修改&#xff0c;删除是右键的时候选择Remove就好了 IDEA左上角 File-->Settings 找到Navigate -->Search Everywhere &#xff0c;右键添加快捷键。 OK --> Apply应用...

HTML 元素中的name 属性

name 属性是 HTML 元素中常用的属性之一。它用于指定表单元素的名称&#xff0c;以便在提交表单时将其值与对应的键关联起来。 每个表单元素&#xff08;例如 <input>、<select> 和 <textarea>&#xff09;都可以具有一个 name 属性&#xff0c;该属性为元素…...

快速上手React:从概述到组件与事件处理

前言 「作者主页」&#xff1a;雪碧有白泡泡 「个人网站」&#xff1a;雪碧的个人网站 「推荐专栏」&#xff1a; ★java一站式服务 ★ ★ React从入门到精通★ ★前端炫酷代码分享 ★ ★ 从0到英雄&#xff0c;vue成神之路★ ★ uniapp-从构建到提升★ ★ 从0到英雄&#xff…...

K8S系列文章之 离线安装自动化工具Ansible

参考 文档 离线安装 Ansible - DevOps - dbaselife 一、Ansible简介 Ansible是一款开源的IT配置管理工具&#xff0c;常被IT界的小伙伴们用于自动化的场景&#xff0c;多用在服务部署、配置管理方面。配置文件采用最常见的yaml格式&#xff0c;学习起来也是比较容易&#xff…...

mysql8.0.3集群搭建

下载mysql安装包&#xff1a; https://dev.mysql.com/downloads/mysql/5.7.html#downloads 准备环境 1、准备三台服务器并设置hosts 192.168.236.143 mysql1 192.168.236.144 mysql2 192.168.236.145 mysql32、设置免密登陆 #生成秘钥 ssh-keygen -t rsa #一直按Enter即可…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例

使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件&#xff0c;常用于在两个集合之间进行数据转移&#xff0c;如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model&#xff1a;绑定右侧列表的值&…...

学校招生小程序源码介绍

基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码&#xff0c;专为学校招生场景量身打造&#xff0c;功能实用且操作便捷。 从技术架构来看&#xff0c;ThinkPHP提供稳定可靠的后台服务&#xff0c;FastAdmin加速开发流程&#xff0c;UniApp则保障小程序在多端有良好的兼…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

【JavaWeb】Docker项目部署

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

tree 树组件大数据卡顿问题优化

问题背景 项目中有用到树组件用来做文件目录&#xff0c;但是由于这个树组件的节点越来越多&#xff0c;导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多&#xff0c;导致的浏览器卡顿&#xff0c;这里很明显就需要用到虚拟列表的技术&…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...