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

Leetcode.剑指 Offer II 022 链表中环的入口节点

题目链接

Leetcode.剑指 Offer II 022 链表中环的入口节点 mid

题目描述

给定一个链表,返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next指针进入环的第一个节点为环的入口节点。如果链表无环,则返回 null

为了表示给定链表中的环,我们使用整数 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,1040, 10^40,104] 内
  • −105<=Node.val<=105-10^5 <= Node.val <= 10^5105<=Node.val<=105
  • pos的值为 -1或者链表中的一个有效索引

分析:快慢指针

我们用两个指针 fastslow,初始都指向 headfast每次走两步,slow每次走一步。

如果链表存在环,那么 fastslow一定会在环中相遇。

在这里插入图片描述

因为fastslow要快1步,所以当 slow走过的距离为 x + y到达相遇点时,fast其实已经在环里转了若干圈了(这里假设是 n圈)。

所以 fast走过的路程为 ,x+n∗(y+z)+yx + n * (y + z) + yx+n(y+z)+y

又因为 fast走过的路程 应该是 两倍slow走过的路程,即 x+n∗(y+z)+y=2∗(x+y)x + n * (y + z) + y = 2 * (x + y)x+n(y+z)+y=2(x+y)

化简得 : x=(n−1)∗(y+z)+zx = (n - 1) * (y + z) + zx=(n1)(y+z)+z,即从相遇点走 z的路程,再走若干圈,就是 x的路程。(我们只需要走 0 圈即可),即 x=zx = zx=z

fastslow相遇时,让 fast重新指向头节点 headfastslow同时移动,当他们再次相遇时的点,就是环的起点。

时间复杂度: O(n)O(n)O(n)

C++代码:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *detectCycle(ListNode *head) {if(head == nullptr) return nullptr;ListNode *fast = head , *slow = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;//两者相遇if(slow == fast){fast = head;while(slow != fast){slow = slow->next;fast = fast->next;}return slow;}}return nullptr;}
};

Java代码:

/*** 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;ListNode fast = head;ListNode slow = head;//fast 或 fast.next 为 null , 说明链表没有环while(fast != null && fast.next != null){slow = slow.next;fast = fast.next.next;//快慢指针相遇了,fast 重新回到头节点 head,快慢指针再同时移动if(slow == fast){fast = head;while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}}return null;}
}

相关文章:

Leetcode.剑指 Offer II 022 链表中环的入口节点

题目链接 Leetcode.剑指 Offer II 022 链表中环的入口节点 mid 题目描述 给定一个链表&#xff0c;返回链表开始入环的第一个节点。 从链表的头节点开始沿着 next指针进入环的第一个节点为环的入口节点。如果链表无环&#xff0c;则返回 null。 为了表示给定链表中的环&#…...

4种不同编程语言的打印方式

意义 打印方式是编程中不可或缺的一部分&#xff0c;它可以帮助开发人员有效地调试和测试代码&#xff0c;并提供有用的信息来监视程序的运行状态和性能。 编程语言中的打印方式是指将程序输出到终端或控制台上进行显示。这个功能在编程中非常重要&#xff0c;因为它可以帮助开…...

websocket介绍

我们聊聊轮询技术,什么是轮询?轮询就是在特定的时间间隔,由浏览器对服务器发出HTTP请求,然后由服务器返回最新的数据给客户端的浏览器。 轮询分为两种: 短轮询:通过不断的向服务端发送数据,客户端发送Request,服务端直接返回Response(不管服务端数据有没有改变)。长轮…...

Educational Codeforces Round 144 (Rated for Div. 2),C,D

C. Maximum Set 思路&#xff1a; 我们求最大数组&#xff0c;显然是L一直乘2,直到再乘2就越过区间位置。我们说过&#xff0c;再乘一个2就不行&#xff0c;那么我们除一个2&#xff0c;换句话说&#xff0c;就是再乘一个4就不行了。发现&#xff0c;我们可能有机会乘一个3&a…...

【redis学习篇】Redis三种持久化方式详解

官方文档 一、Redis持久性 Redis如何将数据写入磁盘 持久性是指将数据写入持久存储&#xff0c;如固态磁盘&#xff08;SSD&#xff09;。Redis提供了一系列持久性选项。其中包括&#xff1a; RDB&#xff08;快照&#xff09;&#xff1a;RDB持久性以指定的时间间隔执行数据…...

垃圾回收中的分代年龄

为什么CMS里的分代年龄是6而不是15 CMS (Concurrent Mark Sweep) 是一种基于分代的垃圾收集器&#xff0c;其中分代年龄指的是一个对象在年轻代中经历了多少次垃圾收集。在 CMS 中&#xff0c;当一个对象的分代年龄达到阈值时&#xff0c;就会被晋升到老年代中。 在 CMS 中&a…...

蓝桥杯-左移右移(2022国赛)

蓝桥杯-左移右移1、问题描述2、解题思路与代码实现2.1 方法一&#xff1a;使用LinkedList双向链表实现(50%)2.2 方法二&#xff1a;使用HashMap左右临界值实现(100%)1、问题描述 小蓝有一个长度为 N 的数组, 初始时从左到右依次是 1,2,3,…N 。 之后小蓝对这个数组进行了 M 次操…...

你还在手撸SQL?ChatGPT笑晕在厕所

文章目录你还在手撸SQL&#xff1f;ChatGPT笑晕在厕所一、背景二、面向Chat编程1. 数据库设计2. 建表语句3. 加中文注释4. 数据模拟5. 查询成绩6. 修改课程任课老师7. 删除课程8. 删除一个有关联数据的课程总结你还在手撸SQL&#xff1f;ChatGPT笑晕在厕所 一、背景 经典3表设…...

【Redis】Redis慢查询

文章目录慢查询记录慢查询两个配置参数修改配置参数慢查询日志慢查询记录 我们都知道像mysql等持久化数据库会有慢查询日志&#xff0c;其实Redis中也有慢查询日志的功能。慢查询就是系统在执行命令的前后计算每条命令的执行时间&#xff0c;如果超过我们预设的时间&#xff0c…...

【Kubernetes】第二十一篇 - k8s 项目部署流程和操作梳理

一&#xff0c;前言 上一篇&#xff0c;介绍了 k8s 污点和容忍度&#xff1b; 在了解前面 k8s 介绍之后&#xff0c;设计并完成一个前后端项目的部署和持续集成&#xff1b; 本篇&#xff0c;介绍基于 k8s 项目部署流程设计&#xff1b; 二&#xff0c;项目部署流程设计 本…...

推荐系统[九]项目技术细节讲解z2:搜索Query理解[Term Weight、Query 改写、同义词扩写]和语义召回技术

搜索Query理解和语义召回技术 随着用户规模和产品的发展, 搜索面临着越来越大的 query 长尾化挑战,query 理解是提升搜索召回质量的关键。本次将介绍搜索在 query term weighting,同义词扩展,query 改写,以及语义召回等方向上的实践方法和落地情况。 1.面临问题:长尾 qu…...

【项目精选】基于SSH的医院在线挂号系统(视频+论文+源码)

点击下载源码 医院挂号系统主要用于实现医院的挂号&#xff0c;前台基本功能包括&#xff1a;用户注册、用户登录、医院查询、挂号、取消挂号、修改个人信息、退出等。 后台基本功能包括&#xff1a;系统管理员登录、医院管理、科室管理、公告管理、退出系统等。 本系统结构如…...

Pandas库:从入门到应用(一)

一、Pandas简介 pandas是 Python 的核⼼数据分析⽀持库&#xff0c;提供了快速、灵活、明确的数据结构&#xff0c;旨在简单、直观地处理关系型、标记型数据。pandas是Python进⾏数据分析的必备⾼级⼯具。 pandas的主要数据结构是 **Series(**⼀维数据)与 DataFrame (⼆维数据…...

MySQL中concat()、concat_ws()、group_concat()函数使用

在平时工作中&#xff0c;经常记不清或者记混他们的用法&#xff0c;正好有时间就记录一下&#xff5e;concat()函数语法&#xff1a;concat(str1, str2, int1...)例如执行sql:SELECT CONCAT(id,USERNAME,USER_PHONE) FROM tb_user输出查询结果为&#xff1a; 1test15216756754…...

【JavaEE初阶】第四节.文件操作 和 IO (上篇)

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、文件 1.1 文件的概念 1.2 文件的路径二、 Java中文件系统操作 2.1 File类的属性 2.2 File类的构造方法 2.3 File类的方法 …...

开源免费堡垒机Teleport堡垒机的安装

准备:纯净centos7系统一个作为堡垒机,若干个linux系统或windows系统服务器作为受保护的服务器 堡垒机IP:192.168.1.15 服务器IP:192.168.1.10 1、teleport安装 下载地址: https://www.tp4a.com/static/download/teleport-server-linux-x64-3.6.4-b3.tar.gz xshell上传压缩…...

图形报表ECharts

图形报表ECharts1 图形报表ECharts1.1 ECharts简介-富客户端图表库ECharts缩写来自Enterprise Charts&#xff0c;商业级数据图表&#xff0c;是百度的一个开源的使用JavaScript实现的数据可视化工具&#xff0c;可以流畅的运行在PC和移动设备上&#xff0c;兼容当前绝大部分浏…...

便捷式储能电源核心技术--单相逆变器设计

便捷式储能电源核心技术–单相逆变器设计 1.逆变器的规格参数 输入电压直流400V输出电压交流rms220V开关频率10kHz滤波电容6.23uF控制方式单极性倍频2.视频学习链接 视频学习链接 3.主电路仿真设计...

Gamma矫正

Gamma 曲线Gamma校正被使用在8位RGB图中。用来解决在有限的存储空间中保存尽可能多的人类感受敏感的色彩内容。Gamma 矫正Gamma校正的方式就是采样时,和输出到显示器给人类看时,对亮度进行的调整.如采样时 Gamma1/2.2 调亮Gamma&#xff0c;如显示时 Gamma2.2 调暗Gamma实际亮度…...

速懂cookie,session,token

文章目录cookiesessiontoken区别cookie 是浏览器提供的一种能力&#xff0c;可以在每次发起请求前&#xff0c;带上cookie里面的内容&#xff08;一些key&#xff0c;value值&#xff09; 分类&#xff1a; 会话级cookie&#xff1a;默认情况&#xff0c;就是会话级cookie&…...

django filter 统计数量 按属性去重

在Django中&#xff0c;如果你想要根据某个属性对查询集进行去重并统计数量&#xff0c;你可以使用values()方法配合annotate()方法来实现。这里有两种常见的方法来完成这个需求&#xff1a; 方法1&#xff1a;使用annotate()和Count 假设你有一个模型Item&#xff0c;并且你想…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

C# 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek

文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama&#xff08;有网络的电脑&#xff09;2.2.3 安装Ollama&#xff08;无网络的电脑&#xff09;2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...

AGain DB和倍数增益的关系

我在设置一款索尼CMOS芯片时&#xff0c;Again增益0db变化为6DB&#xff0c;画面的变化只有2倍DN的增益&#xff0c;比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析&#xff1a; 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

智能职业发展系统:AI驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...