leetcode 热题 100_环形链表 II

题解一:

        哈希表:遍历链表,用哈希表存储遍历过的链表节点,判断链表节点是否在哈希表中存在,如果存在说明链表出现过,第一个重复出现的节点即为开始入环的第一个节点。

import java.util.HashSet;

public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) return head;
            else set.add(head);
            head = head.next;
        }
        return null;
    }
}

题解二:

        快慢指针:用一快一慢的双指针遍历链表,如果指针不相遇则说明不存在环形结构,如果相遇则存在环形结构。第一次相遇时,快指针走过的路程是慢指针的两倍fast=2*slow,快指针相比慢指针多走了若干圈环形结构fast=slow+n*circle,两式相减会得到slow=n*circle。从链表开始的某个指针要到达环形开始节点处,需要走straight+n*circle步(其中的straight表示进入环形前的一段,n*circle表示在环形走走了若干圈还是回到环形开始节点),所以此时慢指针再走straight步就会到达环形开始节点。同时在此时从链表头出发的新指针也会在straight步后到达环形开始节点,与慢指针相遇。附上过程图解(来源. - 力扣(LeetCode))

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode temp = head;
                while (temp != slow) {
                    temp = temp.next;
                    slow = slow.next;
                }
                return temp;
            }
        }

        return null;
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/464504.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【计算机网络】什么是http?

​ 目录 前言 1. 什么是HTTP协议&#xff1f; 2. 为什么使用HTTP协议&#xff1f; 3. HTTP协议通信过程 4. 什么是url&#xff1f; 5. HTTP报文 5.1 请求报文 5.2 响应报文 6. HTTP请求方式 7. HTTP头部字段 8. HTTP状态码 9. 连接管理 长连接与短连接 管线化连接…

无线局域网——wlan

目录 一.wlan的含义和发展 二.wlan技术带来的挑战 1.企业办公场景多样 2.位置速度的要求 3.安全的要求 4.规范的挑战 三.家庭和企业不同的部署需求 1.胖AP模式组网 2.AC瘦AP模式组网 3.组网模式的不同 四.三层隧道转发实验 1.拓扑 2.AP上线 核心交换机vlan ​编辑…

IIS上部署.netcore WebApi项目及swagger

.netcore项目一般是直接双击exe文件&#xff0c;运行服务&#xff0c;今天有个需求&#xff0c;需要把.netcore项目运行在IIS上&#xff0c;遇到了一个小坑&#xff0c;在这里记录一下。 安装IIS&#xff0c;怎么部署站点&#xff0c;这些过于简单就不细说了&#xff0c;不知道…

vue3+Ts项目按需引入Echarts,并封装成hooks

记录 vue3Ts 项目中&#xff0c;按需引入echarts并进行二次封装使用。 1、安装&#xff1a;npm i echarts 2、新增按需引入配置文件&#xff1a;echartsConfig.ts // 引入 echarts 核心模块&#xff0c;核心模块提供了 echarts 使用必须要的接口。 import * as echarts from …

代码随想录阅读笔记-字符串【反转字符串】

题目 编写一个函数&#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。 不要给另外的数组分配额外的空间&#xff0c;你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 你可以假设数组中的所有字符都是 ASCII 码表中的可打印…

Web核心,HTTP,tomcat,Servlet

1&#xff0c;JavaWeb技术栈 B/S架构:Browser/Server&#xff0c;浏览器/服务器架构模式&#xff0c;它的特点是&#xff0c;客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务器端。浏览器只需要请求服务器&#xff0c;获取Web资源&#xff0c;服务器把Web资源…

windows 免密码ssh登录linux;linux免密码ssh登录其他linux

1、windows 免密码ssh登录linux 参考&#xff1a;https://blog.csdn.net/qq285744011/article/details/118293937 1&#xff09;windows先生成公钥私钥 ssh-keygen -t rsa -C "你的邮箱地址"生成后放在用户命令.ssh文件下 2&#xff09;把公钥复制到linux /root/…

【STM32 定时器(二)TIM 输入捕获PWM 总结】

STM32定时器之输入捕获总结 OC介绍PWM介绍PWM初始化代码部分开启时钟配置时基单元配置CCR配置GPIO配置复用和重定义功能 开启定时器代码实现 &#xff1a;实现呼吸灯 OC介绍 PWM介绍 PWM参数计算 分辨率越细&#xff0c;分的分量越精细&#xff0c;越稳定&#xff0c;假如它为…

洛谷P8972 『GROI-R1』 一切都已过去(树上前缀和+运算符重载)

『GROI-R1』 一切都已过去 题目背景 悦关上窗&#xff0c;拉上帘布。 果然还是想不起来啊。 隐约记得曾和什么人一起做过这样的事。 仰面躺下&#xff0c;手执一只木笺。 「究竟如何&#xff0c;才能拥有“过去”啊……」 她闭上双眼。 「6 岁前的记忆……究竟如何才能…

Python Flask框架 -- url

这里限定了int&#xff0c;所以只能输入数字 完整代码&#xff1a; # 从flask这个包中导入Flask类 from flask import Flask, request# 使用Flask类创建一个app对象 # __name__ 代表当前app.py这个模块 app Flask(__name__)app.route(/blog/path) def hello_world():return H…

ThingsBoard初始化数据库Postgres

视频教程&#xff1a; ThingsBoard初始化数据库postgres_哔哩哔哩_bilibilihingsBoard是一个基于Java的开源物联网平台&#xff0c;旨在实现物联网项目的快速开发、管理和扩展。本课程主要从0到1带你熟悉ThingsBoard&#xff0c;学习优秀的物联网变成思维与思想&#xff0c;主…

C++ 笛卡尔树

目录 一、性质二、构建笛卡尔树三、应用四、源码 一、性质 堆性质&#xff1a; 笛卡尔树是一种满足堆性质的树。每个节点包含两个值&#xff1a;键值&#xff08;key&#xff09;和优先级值&#xff08;priority&#xff09;。在笛卡尔树中&#xff0c;根节点的优先级值最大&am…

【图论】拓补排序 - 邻接表

文章目录 题目&#xff1a;310. 最小高度树题目描述代码与注释 题目&#xff1a;310. 最小高度树 题目描述 代码与注释 func findMinHeightTrees(n int, edges [][]int) (ans []int) {if n 1 {return []int{0}}g : make([][]int, n)degree : make([]int, n) // 记录每个节点…

粤嵌6818开发板触摸屏应用

一、触摸屏应用 1.触摸屏设备的名字 在Linux下&#xff0c;一切皆文件&#xff0c;触摸屏也是一个文件。 触摸屏设备的名字&#xff1a;/dev/input/event0 2.触摸屏的两个专业术语 事件 ->event0 当一些外接控制设备(鼠标、键盘&#xff0c;wifi&#xff0c;触摸屏&am…

【Linux】信号保存{sigset_t/sigpending/sigprocmask/bash脚本/代码演示}

文章目录 1.信号相关常见概念2.管理信号的数据结构3.初识sigset_t4.信号集操作函数4.1sigpending4.2sigprocmask4.2代码测试1.测试12.测试23.测试3 4.3bash 脚本文件 1.信号相关常见概念 信号相关动作&#xff1a;产生 发送 接收 阻塞 递达(处理) 实际执行信号的处理动作称为信…

Spring Boot中application配置文件的生效顺序

Spring Boot的一个重要特性就是它的自动配置&#xff0c;这一特性在很大程度上依赖于名称为application的配置文件。本文将详细介绍在Spring Boot中&#xff0c;这些配置文件的加载顺序以及每份文件的应用范围。 文章目录 配置文件的种类配置文件的加载顺序配置文件的环境切换 …

一起玩儿3D打印机——03 Marlin固件的获取和安装环境的配置

摘要&#xff1a;本文介绍Marlin固件的获取和安装环境的配置 Marlin是一款开源软件&#xff0c;其主页为&#xff1a;https://marlinfw.org/&#xff0c;首页正中就是下载连接&#xff0c;如下图所示&#xff1a; 单击下面的“Download Marlin 2.1.2.2”按钮就会进入下载页面&a…

图形设计软件 CorelDRAW Graphics Suite 2024 v25.0.0.230 中文破解版

CorelDRAW Graphics Suite (简称CDR) 是加拿大Corel公司开发的一款功能强大的专业平面设计软件、矢量设计软件、矢量绘图软件。软件广泛应用于商标设计、标志制作、封面设计、CIS设计、产品包装造型设计、模型绘制、插图描画、时装/服饰设计、印刷制版、排版及分色输出等诸多领…

linux查看top与修改root密码

top perf top -g -p 进程名 使用top命令&#xff0c;同时输入大写的P&#xff0c;会按照cpu使用率从大到小排列 linux修改用户登录密码 输入Ctrlx进入下面的界面 分别输入mount -o remount, rw / 注意rw后面又两个空格 输入passwd root 修改root密码 输入新密码2次 ex…

三、传输层拥塞控制、差错控制

3.1 概述和传输层服务 传输服务和协议&#xff1a; 为运行在不同主机上的应用进程提供逻辑通信&#xff1b; 传输协议运行在端系统-发送方:将应用层的报文分成报文段&#xff0c;然后传递给网络层&#xff1b;接收方&#xff1a;将报文段重组成报文&#xff0c;然后传递给应用…