【Leetcode 160】环形链表——双指针,细节讲解

题目

给你一个链表的头节点 head ,判断链表中是否有环。

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

如果链表中存在环 ,则返回 true 。 否则,返回 false 。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

提示:

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。

思路

其实很简单,如果headA的长度与headB的长度相等,则创建两个指针,pA.val === pB.val,不等则向后移动指针,直到链表结束,不等就返回null。

但由于长度不相等,则不能这样判断,首先我们就让他们相等。

因为 headA 长度 + headB 长度 = headB 长度 + headA长度

所以,我们让pA指针先走完 headA,再走headB。

pB指针先走完 headB,再走headA。

此时,它们的总长度就相等了,这时再比较后面的即可。

 

代码

//双指针 时间复杂度 O(m+n) 空间复杂度O(1)
function getIntersectionNode(headA: ListNode | null,headB: ListNode | null
): ListNode | null {//如果有一个链表为空链表,则肯定不相交if (!headA || !headB) return null;//创建 pA 指针,其先指向headA链表,后指向headB链表let pA: ListNode | null = headA;//创建 pB 指针,其先指向headB链表,后指向headA链表let pB: ListNode | null = headB;//只有 pA 与 pB 不相等时才进入循环,如果两个链表都遍历完,则两个指针都为null,也不会进入循环的while (pA !== pB) {//如果 headA链表没有遍历完,则向后移动指针,否则开始遍历headB链表pA = pA ? pA.next : headB;//如果 headB链表没有遍历完,则向后移动指针,否则开始遍历headA链表pB = pB ? pB.next : headA;}//相等,pA 为 相等时的节点,否则pA为nullreturn pA;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Web安全:文件上传漏洞详解,文件上传漏洞原理、绕过方式和防御方案。

「作者简介」&#xff1a;2022年北京冬奥会网络安全中国代表队&#xff0c;CSDN Top100&#xff0c;就职奇安信多年&#xff0c;以实战工作为基础对安全知识体系进行总结与归纳&#xff0c;著作适用于快速入门的 《网络安全自学教程》&#xff0c;内容涵盖系统安全、信息收集等…

在XP/Vista系统下使用Node.js的babel-cli命令行工具转码ES6语法的js文件,让IE8浏览器也能运行

在XP系统下IE浏览器最高只能装到IE8&#xff0c;在Vista系统下最高只能装到IE9。 2015年以后&#xff0c;JavaScript新增了很多语法&#xff0c;比如class、extends&#xff0c;还有let和const等等&#xff0c;这些语法都是XP下的终端浏览器IE8所不支持的。要想让使用了这些新式…

【Django】中间件实现钩子函数预处理和后处理,局部装饰视图函数

在app文件夹里新建middleware.py继承MiddlewareMixin&#xff0c; 编写中间件类&#xff0c;重写process_request、process_response钩子函数 from django.http import HttpRequest, HttpResponse from django.utils.decorators import decorator_from_middleware from django…

NAT 网络转换

NAT(Network Address Translation) 网络地址转换 0x01 NAT 简介 为什么要使用 NAT IPv4 网络地址紧缺&#xff0c;从而出现了私有网段&#xff0c;来补充地址&#xff0c;但私有网段不课访问 internet 所以出现了 NAT 地址转换&#xff0c;将私有地址&#xff0c;转换为公网 I…

typora自动生成标题序号(修改V1.0)

目录 带序号效果图 解决方法 带序号效果图 解决方法 1.进入文件夹&#xff1a;文件–>偏好设置–>外观–>主题–>打开主题文件夹 2.如果没有base.user.css文件&#xff0c;新建一个。如果有直接用记事本打开&#xff0c;把下面代码拷贝进去保存。 /** initiali…

rfid资产管理系统如何帮助医院管理耗材的

RFID资产管理系统可以帮助医院管理耗材&#xff0c;提高耗材管理的效率和准确性。以下是它可以发挥作用的几个方面&#xff1a; 1. 实时跟踪和定位&#xff1a;使用RFID标签附加在耗材上&#xff0c;可以实时跟踪和定位耗材的位置。医院可以通过系统查询耗材的实时位置&#xf…

LeetCode - 贪心算法 (Greedy Algorithm) 集合 [分配问题、区间问题]

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/139242199 贪心算法&#xff0c;是在每一步选择中&#xff0c;都采取当前状态下&#xff0c;最好或最优&#xff08;即最有利&#xff09;的选择&…

(免费领源码)java#SSM#mysql第三方物流系统37852-计算机毕业设计项目选题推荐

摘 要 科技进步的飞速发展引起人们日常生活的巨大变化&#xff0c;电子信息技术的飞速发展使得电子信息技术的各个领域的应用水平得到普及和应用。信息时代的到来已成为不可阻挡的时尚潮流&#xff0c;人类发展的历史正进入一个新时代。在现实运用中&#xff0c;应用软件的工作…

mumu 模拟器安装

1.下载安装 下载地址 Win 历史版本&#xff1a;http://mumu.163.com/update/win/Mac 历史 版本&#xff1a;http://mumu.163.com/20200515/25905_880858.html 2.设置为竖屏 在设置中心--界面设置页面设置宽720&#xff0c;高1280&#xff0c;DPI为240&#xff0c;如下图所示。…

数据结构(六)队列

文章目录 一、概念二、逻辑结构&#xff1a;线性结构三、存储结构&#xff08;一&#xff09;顺序队列&#xff08;二&#xff09;循环队列1. 结构体定义2. 创建队列&#xff08;1&#xff09;函数定义&#xff08;2&#xff09;注意点&#xff08;3&#xff09;代码实现 3. 入…

windows内存管理

一 windows系统的内存管理涉及哪些 1.1 虚拟内存管理机制 windows操作系统使用虚拟内存技术&#xff0c;将磁盘文件&#xff0c;通过映射对象&#xff08;存储在物理内存&#xff09;关联&#xff0c;映射到虚拟内存作为文件试图。即用户操作"虚拟内存中File View Objec…

Android数据缓存框架 - 内存数据载体从LiveData到StateFlow

引言&#xff1a;所有成功者的背后&#xff0c;都有一份艰苦的历程&#xff0c;不要只看到了人前的风光&#xff0c;而低估了他们背后所付出的努力。 随着flow到流行度越来越高&#xff0c;有开发者呼吁我使用flow&#xff0c;于是我就如你们所愿&#xff0c;新增了StateFlow作…

Flink本地idea运行环境配置webui

Flink本地idea运行环境配置webui 1.添加依赖 <dependency><groupId>org.apache.flink</groupId><artifactId>flink-runtime-web_2.11</artifactId><version>1.13.6</version><scope>provided</scope></dependency&g…

【Qt Creator】跨平台的C++图形用户界面应用程序开发框架---QT

&#x1f341;你好&#xff0c;我是 RO-BERRY &#x1f4d7; 致力于C、C、数据结构、TCP/IP、数据库等等一系列知识 &#x1f384;感谢你的陪伴与支持 &#xff0c;故事既有了开头&#xff0c;就要画上一个完美的句号&#xff0c;让我们一起加油 目录 1.互联网的核心岗位以及职…

【Chapter5】死锁与饥饿,计算机操作系统教程,第四版,左万利,王英

文章目录 1.1 什么是死锁1.2 死锁的类型1.2.1 竞争资源引起的死锁1.2.2 进程间通信引起的死锁1.2.3 其他原因引起的死锁 1.3 死锁产生必要条件1.4 死锁的处理策略1.5 死锁的预防1.5.1 破坏资源独占条件1.5.2 破坏不可剥夺条件1.5.3 破坏保持申请条件1.5.4 破坏循环等待条件 1.6…

Spring Boot 统一数据返回格式

在 Spring Boot 项目中&#xff0c;统一的数据格式返回是一种良好的实践&#xff0c;它提高了代码的可维护性和一致性&#xff0c;并改善了客户端与服务端之间的通信。本文将介绍如何在 Spring Boot 中实现统一的数据格式返回。 1 为什么需要统一数据返回格式 ⽅便前端程序员更…

Reader类的使用方法和技巧,你掌握了吗?

哈喽&#xff0c;各位小伙伴们&#xff0c;你们好呀&#xff0c;我是喵手。运营社区&#xff1a;C站/掘金/腾讯云&#xff1b;欢迎大家常来逛逛 今天我要给大家分享一些自己日常学习到的一些知识点&#xff0c;并以文字的形式跟大家一起交流&#xff0c;互相学习&#xff0c;一…

vscode中使用conda虚拟环境

每一次配置环境&#xff0c;真的巨烦&#xff0c;网上的资料一堆还得一个个尝试&#xff0c;遂进行整理 1.准备安装好Anaconda 附带一篇测试教程&#xff0c;安装anaconda 2.准备安装vscode 安装地址&#xff1a;Visual Studio Code 3.创建Conda环境 搜索框搜索Anaconda…

音视频及H264/H256编码相关原理

一、音视频封装格式原理&#xff1a; 我们播放的视频文件一般都是用一种封装格式封装起来的&#xff0c;封装格式的作用是什么呢&#xff1f;一般视频文件里不光有视频&#xff0c;还有音频&#xff0c;封装格式的作用就是把视频和音频打包起来。 所以我们先要解封装格式&#…

香橙派OrangePi AIpro上手初体验

一、前言 非常感谢能够收到CSDN和香橙派的OrangePi AIpro开发板评测活动的邀请&#xff1b;收到的OrangePi AIpro实物如下所示&#xff1a; 二、OrangePi AIpro介绍 通过查询香橙派官网可以了解到OrangePi AIpro的相关信息如下&#xff1a;OrangePi AIPro 开发板是香橙派联合…