LeetCode 142.环形链表Ⅱ

题目描述

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

提示:

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

进阶:你是否可以使用 O(1) 空间解决此题?

方法一

思路:

和环形链表Ⅰ一样,哈希表,遍历判断有无出现过,没出现过就添加进set,出现过就返回。

代码:

/*** 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) {Map<ListNode,Integer> map=new HashMap<ListNode,Integer>();while(head!=null){if(map.containsKey(head)){return head;}map.put(head,head.val);head=head.next;}return null;}
}

方法二

思路:

快慢指针,快慢指针相等了说明有环。之后的就是要证明快指针比慢指针多走了多少。这里看看就好,我自己肯定是想不出来。假设从链表头到环入口距离为a,快慢指针相遇处距入口距离为b,那么慢指针走了a+b,而快指针走了2a+2b,记相遇处绕回到入口处距离为c,那么快指针多走了一圈,即c+b,即a=c,此时让一个指针从链表头开始走c步,一个指针同时在相遇处走c步,那么他们会在入口相遇

代码:

/*** 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;while(fast!=null){slow=slow.next;if(fast.next!=null)   fast=fast.next.next;else return null;if(fast==slow) {ListNode ptr=head;while(ptr!=slow){ptr=ptr.next;slow=slow.next;}return ptr;}}return null;}
}

参考链接:142. 环形链表 II - 力扣(LeetCode)

【LeetCode热题100】【链表】环形链表 II-CSDN博客

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

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

相关文章

Windows命令行一键安装、配置WSL的方法

本文介绍在Windows电脑中&#xff0c;通过命令行的方式&#xff0c;快速、方便安装适用于Linux的Windows子系统&#xff08;Windows Subsystem for Linux&#xff0c;WSL&#xff09;的方法。 WSL是由微软开发的一项功能&#xff0c;允许在Windows操作系统上运行Linux发行版系统…

Adobe-Premiere-CEP 扩展 入门-视频剪辑-去气口插件-Silence Remover

短视频&#xff0c;这两年比较火&#xff0c;不要再问为什么用Premiere&#xff0c;非常难用&#xff0c;为什么不用某影&#xff0c;某些国内软件非常接地气简单&#xff0c;又例如某音资深的视频短编辑就很好用了。。。 Premiere二次开发调试难&#xff0c;不如自己搞个cons…

Ftp笑脸漏洞(VSFTPD 2.3.4)复现(后门漏洞)

Ftp笑脸漏洞&#xff08;VSFTPD 2.3.4&#xff09;复现&#xff08;后门漏洞&#xff09; 一、原理二、复现准备三、漏洞复现四、Metasploit利用脚本复现 一、原理 vsftpd 是“ very secure FTP daemon ”的缩写&#xff0c;安全性是它的一个最大的特点。 vsftpd是一个 UNIX 类…

学习笔记——字符串(单模+多模+练习题)

单模匹配 Brute Force算法&#xff08;暴力&#xff09; 算法思想 母串和模式串字符依次配对&#xff0c;如果配对成功则继续比较后面位置是否相同&#xff0c;如果出现匹配不成功的位置&#xff0c;则j&#xff08;模式串当前的位置&#xff09;从头开始&#xff0c;i&…

Qt——信号 和 槽

目录 概述 信号和槽的使用 自定义信号和槽 带参数的信号和槽 概述 在Linux系统中&#xff0c;我们也介绍了信号的产生、信号的检测以及信号的处理机制&#xff0c;它就是系统内部的通知机制&#xff0c;也可以是一种进程间通信的方式。在系统中有很多信号&#xff0c;我们可…

设计模式学习笔记 - 回顾总结:在实际软件开发中常用的设计思想、原则和模式

概述 本章&#xff0c;先来回顾下整个专栏的知识体系&#xff0c;主要包括面向对象、设计原则、编码规范、重构技巧、设计模式五个部分。 面向对象 相对于面向过程、函数式编程&#xff0c;面向对象是现在最主流的编程范式。纯面向过程的编程方法&#xff0c;现在已经不多见了…

数据结构中的栈(C语言版)

一.栈的概念 栈是一种常见的数据结构&#xff0c;它遵循后进先出的原则。栈可以看作是一种容器&#xff0c;其中的元素按照一种特定的顺序进行插入和删除操作。 压栈&#xff1a;栈的插入操作叫做进栈/压栈/入栈&#xff0c;入数据在栈顶。 出栈&#xff1a;栈的删除操作叫做…

uniapp/微信小程序实现加入购物车点击添加飞到购物车动画

1、预期效果 2、实现思路 每次点击添加按钮时&#xff0c;往该按钮上方添加一个悬浮元素&#xff0c;通过位移动画将元素移到目标位置。 1. 为每个点击元素设置不同的class&#xff0c;才能通过uni.createSelectorQuery来获取每个元素的节点信息&#xff1b; 2. 添加一个与…

在51单片机里面学习C语言

在开始前我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「&#xff23;语言的资料从专业入门到高级教程」&#xff0c; 点个关注在评论区回复“888”之后私信回复“888”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01; 说出来你们可能都…

0510_IO5

练习题&#xff1a; #include <stdio.h>#include <string.h>#include <stdlib.h>#include <sys/types.h>#include <unistd.h>#include <sys/stat.h>#include <fcntl.h>#include <pthread.h>#include <semaphore.h>#incl…

【智能算法应用】基于麻雀搜索算法-支持向量回归预测(SSA-SVR)

目录 1.算法原理2.数学模型3.结果展示4.调试记录5.参考文献6.代码获取 1.算法原理 【智能算法】麻雀搜索算法&#xff08;SSA&#xff09;原理及实现 2.数学模型 支持向量机(SVM)是针对二分类问题&#xff0c;支持向量回归(SVR)基于SVM应用与回归问题。SVR回归与SVM分类的区…

【数据库原理及应用】期末复习汇总高校期末真题试卷08

试卷 一、选择题(每题 2 分&#xff0c;共 30 分)    1. ___ ____是长期存储在计算机内的有组织,可共享的数据集合. A.数据库管理系统 B.数据库系统 C.数据库 D.文件组织 2. 数据库类型是按照 来划分…

使用 Gitea 进行私有 Git 仓库管理

在本文中&#xff0c;我们将介绍如何使用 Gitea 搭建并管理私有 Git 仓库。Gitea 是一个轻量级的 Git 服务&#xff0c;提供了类似于 GitHub 的功能&#xff0c;适合个人和小团队使用。我们将通过以下步骤来完成搭建和配置 Gitea 服务器。 步骤一&#xff1a;安装 Gitea 首先…

自定义表单元素组件内容变化触发ElForm重新校验

对于下图中“付费类型”怎么实现有很多种方式&#xff0c;我能想到的是以下两种&#xff1a; Element Plus的RadioButton自定义组件 1. RadioButton 它本质上就是一个单选组件&#xff0c;它跟Element Plus的RadioButton本质上没有区别&#xff0c;无非是外观上的差别。那么…

Docker容器:Docker-Consul 的容器服务更新与发现

目录 前言 一、什么是服务注册与发现 二、 Docker-Consul 概述 1、Consul 概念 2、Consul 提供的一些关键特性 3、Consul 的优缺点 4、传统模式与自动发现注册模式的区别 4.1 传统模式 4.2 自动发现注册模式 5、Consul 核心组件 5.1 Consul-Template组件 5.2 Consu…

kaldi学习参考

HMM模型 https://www.cnblogs.com/baixf-xyz/p/16777438.htmlhttps://www.cnblogs.com/baixf-xyz/p/16777438.htmlGMM-HMM 基于GMM-HMM的语音识别系统https://www.cnblogs.com/baixf-xyz/p/16777439.html https://www.cnblogs.com/baixf-xyz/p/16777426.htmlhttps://www.cnbl…

【SRC实战】利用APP前端加密构造数据包

挖个洞先 https://mp.weixin.qq.com/s/ZnaRn222xJU0MQxWoRaiJg “ 以下漏洞均为实验靶场&#xff0c;如有雷同&#xff0c;纯属巧合” 01 — 漏洞证明 “ 参数加密的情况&#xff0c;不会逆向怎么办&#xff1f;” 1、新用户首次设置密码时抓包&#xff0c;此处设置为0000…

Oracle -在线回缩表

conn scott/tiger DROP TABLE EMP1 PURGE; CREATE TABLE EMP1 AS SELECT * FROM EMP; alter table emp1 enable row movement; -- 启动回缩特性 insert into emp1 select * from emp1; / / commit; -- 增加到14000行 -- 分析表的结构 analyze table emp1 comput…

<Linux> 权限

目录 权限人员相对于文件来说的分类更改权限文件的拥有者与所属组umask粘滞位 权限 权限是操作系统用来限制对资源访问的机制&#xff0c;权限一般分为读、写、执行。系统中的每个文件都拥有特定的权限、所属用户及所属组&#xff0c;通过这样的机制来限制哪些用户、哪些组可以…

Oracle count的优化-避免全表扫描

Oracle count的优化-避免全表扫描 select count(*) from t1; 这句话比较简单&#xff0c;但很有玄机&#xff01;对这句话运行的理解&#xff0c;反映了你对数据库的理解深度&#xff01; 建立实验的大表他t1 SQL> conn scott/tiger 已连接。 SQL> drop table t1 purge…