day16-环形链表

问题描述:

给定一个链表的头节点  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
解释:链表中没有环。

解决方案:

1、物理同向追击:快指针速度-慢~== 1 格/次,即相对追击速度为1时,必然在追上时相遇!

2、快指针一定先进入循环内,慢指针进入时,快指针已经循环了 n 圈

3、快指针与慢指针第一次相遇时:

        状态分析:(1)满指针结束本次循环,即到达循环开始节点的距离为 X;

                          (2)链表起点 到达次循环开始节点的距离为 X;

                          (3)设快指针新起点为 链表起点,且速度等于满指针速度。

函数代码:

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head||!head->next)     return NULL;
        ListNode*slow=head,*fast=head;

        while(1){
            if (!fast||!fast->next) return NULL;

            slow=slow->next;
            fast=fast->next->next;

            if(slow==fast)  break;
        }

        fast=head;

        while(slow!=fast){
            slow=slow->next;
            fast=fast->next;
        }
        return fast;
    }
};

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

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

相关文章

linux下的打包/解包命令(tar,zip/unzip)

目录 打包/解包 作用 zip -r选项 unzip -d选项 如果不使用递归压缩 -l / -v选项 tar 介绍 选项 示例 打包/解包 作用 使多个文件变成一个文件,不易造成数据缺失使下载时间变短 zip 将目录或文件压缩成zip格式 -r选项 递归式压缩某目录及其所有子目录中的文件 如果不…

【大数据】五、yarn基础

Yarn Yarn 是用来做分布式系统中的资源协调技术 MapReduce 1.x 对于 MapReduce 1.x 的版本上: 由 Client 发起计算请求,Job Tracker 接收请求之后分发给各个TaskTrack进行执行 在这个阶段,资源的管理与请求的计算是集成在 mapreduce 上的…

大模型+强化学习_在线交互调参_GLAM

英文名称: Grounding Large Language Models in Interactive Environments with Online Reinforcement Learning 中文名称: 通过在线强化学习在交互式环境中建立大型语言模型 链接: https://arxiv.org/pdf/2302.02662.pdf 代码: https://github.com/flowersteam/Grounding_LLMs…

Listary 清除无效的搜索历史记录

目录预览 一、问题描述二、原因分析三、解决方案四、参考链接 一、问题描述 listary 用过一段时间后,搜索其他东西总会显示一个感叹号的之前的文件,强迫症很难受啊。 二、原因分析 猜测是历史记录的问题记录历史搜索的文件没有重建 三、解决方案 提示…

Centos7 搭建openVPN

一、概述 CentOS 搭建openVPN时需要一台有公网IP的服务器。openVPN 是一个基于SSL/TLS的虚拟专用网络(VPN),它允许你创建一个安全的连接,通过它你可以将你的网络流量封装并加密,从而在公网上进行传输。 一、搭建证书…

现代白色系装修,打造高级感生活空间。福州中宅装饰,福州装修

玄关 玄关嵌入满墙收纳鞋柜,下方留空15公分作为拖鞋区,中间留出40公分作为随手区 客厅 客厅打通阳台,白色亮面瓷砖通铺,即使不做落地窗设计,室内也是十分明亮 落地电视柜,减少卫生死角,白色整体…

vulnhub prime1通关

目录 环境安装 1.信息收集 收集IP 端口扫描 目录扫描 目录文件扫描 查找参数 打Boss 远程文件读取 木马文件写入 权限提升 方法一 解锁密钥 方法二: linux内核漏洞提权 总结 环境安装 Kali2021.4及其prime靶机 靶机安装:Prime: 1 ~ Vul…

Install Docker

Docker Desktop 直接安装 Docker Desktop Docker Desktop includes the Docker daemon (dockerd), the Docker client (docker), Docker Compose, Docker Content Trust, Kubernetes, and Credential Helper. Linux下安装Docker CE 参考官方文档 参见阿里云的文档 # step 1…

docker安装WireGuard服务

启动 WireGuard 如下异常 则是linux内核需要升级 $ wg-quick down wg0 $ wg-quick up wg0 Error: WireGuard exited with the error: Cannot find device "wg0" This usually means that your hosts kernel does not support WireGuard!at /app/lib/WireGuard.js:65…

效率加倍 :5 个有助于自动化办公的 Python 工具库

想想你在工作中所做的所有重复性任务。发送电子邮件、创建 Excel 报告、从 PDF 中提取数据、手动进行大量的数据分析工作。 我相信没有人愿意天天重复这样做,但最终,必须有人这样做。有没有更好的解决方案呢? 在本文中,我将向大…

【STL学习】(1)string类

前言 本文将详细讲解STL中string类的常用的接口函数。 一、为什么学习string类? 1、字符串类型的重要性 在现实生活中有很多复杂类型是以字符串来表达的,比如我们在搜索引擎输入的“数据”,一个人的姓名、身份证号等等。 所以字符串类型是很…

康奋威科技邀您到场参观2024长三角快递物流展

参展企业介绍 杭州康奋威科技股份有限公司创立于2005年,由国家“万人计划”专家任天挺先生创立并担任法人,是一家专业从事智能装备研发与制造的国家级高新技术企业。专注于自动化控制、机械设计、信息化方面的技术研究,主要为太阳能光伏、智…

一篇文章让你完全掌握使用Git推送代码到新版GitCode

Git推送代码到新版GitCode 前言一、安装git二、tortoise git的安装2.1 关于tortoise git2.2 tortoise git和tortoise git汉语包的下载2.3安装过程2.4配置tortoise git 三、创建GitCode项目关于READM文件关于.gitignore文件关于LICENS文件 四、配置GitCode和Git4.1克隆项目4.2配…

【十二】【算法分析与设计】滑动窗口(3)

30. 串联所有单词的子串 给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。 s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。 例如,如果 words ["ab","cd","ef"]&#xff…

【Godot 3.5控件】用TextureProgress制作血条

说明 本文写自2022年11月13日-14日,内容基于Godot3.5。后续可能会进行向4.2版本的转化。 概述 之前基于ProgressBar创建过血条组件。它主要是基于修改StyleBoxFlat,好处是它几乎可以算是矢量的,体积小,所有东西都是样式信息&am…

Mysql学习--深入探究索引和事务的重点要点与考点

꒰˃͈꒵˂͈꒱ write in front ꒰˃͈꒵˂͈꒱ ʕ̯•͡˔•̯᷅ʔ大家好,我是xiaoxie.希望你看完之后,有不足之处请多多谅解,让我们一起共同进步૮₍❀ᴗ͈ . ᴗ͈ აxiaoxieʕ̯•͡˔•̯᷅ʔ—CSDN博客 本文由xiaoxieʕ̯•͡˔•̯᷅ʔ 原创 CSDN …

基于springboot+vue+Mysql的闲一品交易平台

开发语言:Java框架:springbootJDK版本:JDK1.8服务器:tomcat7数据库:mysql 5.7(一定要5.7版本)数据库工具:Navicat11开发软件:eclipse/myeclipse/ideaMaven包:…

2024,产品国际化改造

2024,我们的核心是国际化/信创/多租户/AI融合应用。 作为招投标与即将推进的项目需求,优先对产品进行国际化改造。 1.我们的思考 作为基础平台个性化定制的项目落地模式,我们必须兼顾平台与定制直接的平衡,使整个系统能快速在多…

力扣541. 反转字符串 II

思路:题目的意思就是每2k个字符进行一次循环访问,如果个数小于k就全部反转,如果大于k则只反转k个字符; class Solution {public String reverseStr(String s, int k) {char[] charArray s.toCharArray();int length charArray.length;//每…

DDR4总结最全纯干货分享

DDR存储器发展的主要方向一言以蔽之,是更高速率,更低电压,更密的存储密度,从而实现更好的性能。 DDR4 SDRAM(Double Data Rate Fourth SDRAM):DDR4提供比DDR3/ DDR2更低的供电电压1.2V以及更高的…