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

面试常问-如何判断链表有环、?

如何判断链表有环

  • 题目:
  • 解决方案一:
  • 解决方案二:
  • 解决方案三:

题目:

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

解决方案一:

可以使用快慢指针法, 分别定义 fast 和 slow指针,从头结点出发,fast指针每次移动两个节点,slow指针每次移动一个节点,如果 fast 和 slow指针在途中相遇 ,说明这个链表有环。

public class Solution {public boolean hasCycle(ListNode head) {ListNode fast = head;ListNode slow = head;// 空链表、单节点链表一定不会有环while (fast != null && fast.next != null) {fast = fast.next.next; // 快指针,一次移动两步slow = slow.next;      // 慢指针,一次移动一步if (fast == slow) {   // 快慢指针相遇,表明有环return true;}}return false; // 正常走到链表末尾,表明没有环}
}

解决方案二:

通过Set集合去重也能实现,效率不高图一乐

public class Solution {public boolean hasCycle(ListNode head) {Set<ListNode> set=new HashSet<>();while(head!=null){if(set.contains(head))return true;set.add(head);head=head.next;}return false;}
}

解决方案三:

提供一个全新的思路,一次遍历单指针搞定,时间击败100%。每次遍历完一个节点,将它的下一个节点指向初始节点,然后继续遍历: 如果下一节点为空,没有换 如果下一节点的下一指针为root,有环。

public class Solution {public boolean hasCycle(ListNode head) {ListNode root = head;while(head!=null){if(head.next==root) return true;//如果节点的下一节点为初始节点  有环ListNode tem = head; head = head.next;//否则继续遍历下一个节点tem.next = root;//上一个节点的下一节点为初始节点}return false;//走到了尽头,没有换}
}

相关文章:

面试常问-如何判断链表有环、?

如何判断链表有环 题目&#xff1a;解决方案一&#xff1a;解决方案二&#xff1a;解决方案三&#xff1a; 题目&#xff1a; 给你一个链表的头节点 head &#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;…...

基于springboot实现农机电招平台系统项目【项目源码+论文说明】计算机毕业设计

基于springboot实现农机电招平台系统演示 摘要 随着农机电招行业的不断发展&#xff0c;农机电招在现实生活中的使用和普及&#xff0c;农机电招行业成为近年内出现的一个新行业&#xff0c;并且能够成为大群众广为认可和接受的行为和选择。设计农机电招平台的目的就是借助计算…...

森林无人机高效解决巡查难题,林区防火掀新篇

山东省某市为了强化森林火灾防范&#xff0c;采用了一项新兴手段——复亚智能无人机森林火情监测系统。这套系统在AI飞行大脑的指挥下&#xff0c;让无人机在空中巡逻&#xff0c;实现了无人机森林防火系统的实施落地。 一、AI大脑如何引领森林无人机高空巡逻&#xff1f; 在山…...

python 爬虫之 爬取网站信息并保存到文件

文章目录 前期准备探索该网页的HTML码的特点开始编写代码存入文件总的程序文件存储效果 前期准备 随便找个网站进行爬取&#xff0c;这里我选择的是(一个卖书的网站&#xff09; https://www.bookschina.com/24hour/62700000/ 我的目的是爬取这个网站的这个页面的书籍的名称以…...

kubelet漏洞CVE-2020-8559复现与分析

首先下载源码 git clone --branch v1.17.1 --single-branch https://github.com/kubernetes/kubernetes.git 参考 移花接木&#xff1a;看CVE-2020-8559如何逆袭获取集群权限-腾讯云开发者社区-腾讯云...

基于C#实现奇偶排序

这篇就从简单一点的一个“奇偶排序”说起吧&#xff0c;不过这个排序还是蛮有意思的&#xff0c;严格来说复杂度是 O(N2)&#xff0c;不过在多核的情况下&#xff0c;可以做到 N2 /(m/2)的效率&#xff0c;这里的 m 就是待排序的个数&#xff0c;当 m100&#xff0c;复杂度为 N…...

Kibana部署

服务器 安装软件主机名IP地址系统版本配置KibanaElk10.3.145.14centos7.5.18042核4G软件版本&#xff1a;nginx-1.14.2、kibana-7.13.2-linux-x86_64.tar.gz 1. 安装配置Kibana &#xff08;1&#xff09;安装 [rootelk ~]# tar zxf kibana-7.13.2-linux-x86_64.tar.gz -C…...

【Linux】了解进程的基础知识

进程 1. 进程的概念1.1 进程的理解1.2 Linux下的进程1.3 查看进程属性1.4 getpid和getppid 2. 创建进程3. 进程状态4. 进程优先级5. 进程切换6. 环境变量7. 本地变量与内建命令 1. 进程的概念 一个已经加载到内存中的程序&#xff0c;叫做进程&#xff08;也叫任务&#xff09…...

ES6 — ES14 新特性

一、ES6 新特性&#xff08;2015&#xff09; 1. let和const 在ES6中&#xff0c;新增了let和const关键字&#xff0c;其中 let 主要用来声明变量&#xff0c;而 const 通常用来声明常量。let、const相对于var关键字有以下特点&#xff1a; 特性varletconst变量提升✔️全局…...

附录12-time.h的常用方法

目录 1 数据类型 1.1 time_t 1.2 tm 1.3 clock_t 2 相关知识 3 获取从1970年1月1日以来的UTC秒数 time() 4 获取本时区时间字符串 ctime() 5 获取GMT时间的tm gmttime() 6 获取本地时间的tm localtime() 7 记录当前毫秒数 clock() 8 将表示本地时间的tm转…...

C语言公交车之谜(ZZULIOJ1232:公交车之谜)

题目描述 听说郑州紫荆山公园有英语口语角&#xff0c;还有很多外国人呢。为了和老外对上几句&#xff0c;这周六早晨birdfly拉上同伴早早的就坐上了72路公交从学校向紫荆山进发。一路上没事干&#xff0c;birdfly开始思考一个问题。 从学校到紫荆山公园共有n(1<n<20)站路…...

Liunx Ubuntu Server 安装配置 Docker

1. 安装Docker 1.1 更新软件包列表 sudo apt update1.2 添加Docker存储库 sudo apt install apt-transport-https ca-certificates curl gnupg-agent software-properties-common curl -fsSL https://download.docker.com/linux/ubuntu/gpg | sudo apt-key add - sudo add-a…...

Oracle ORA12514 监听程序当前无法识别连接描述符中请求的服务

最简单的有可能是你的服务还没有开启&#xff0c;需要启动服务&#xff01;&#xff01;&#xff01;&#xff01; 在连接数据库的时候&#xff0c;有时会遇到一个“ORA12514&#xff1a;监听程序当前无法识别连接描述符中请求的服务”的错误&#xff0c;这个错误其实就是数据…...

druid keepAlive 导致数据库连接数飙升

一.背景 应用在执行完某个复杂业务&#xff0c;主要包含20几个查询SQL的操作后&#xff0c;会导致数据库连接池一直升高 druid版本&#xff1a;1.2.11 druid配置文件&#xff1a; spring.datasource.druid.maxActive100 spring.datasource.druid.initialSize20 spring.datas…...

四川竹哲电子商务有限公司深耕抖音电商服务领域

随着数字经济的飞速发展&#xff0c;抖音电商服务成为了越来越多企业的首选。在这个充满机遇与挑战的时代&#xff0c;四川竹哲电子商务有限公司以其卓越的实力和专业的服务&#xff0c;成为了抖音电商服务领域的佼佼者。 一、深耕抖音电商服务领域 作为一家专注于抖音电商服务…...

爬虫中XPath语法四个重要概念及示例

一、根节点与非根节点 1、/div :选择div节点&#xff0c;只有当它是文档的根节点时。 2、//div&#xff1a;选择文档中所有的div节点&#xff08;包括非根节点&#xff09;。 二、通过属性选择节点 1、//href&#xff1a;选择带href属性的所有节点。 2、//a[hrefhttp://ba…...

MySQL-03-索引

索引是提高MySQL查询性能的一个重要途径&#xff0c;但过多的索引可能会导致过高的磁盘使用率以及过高的内存占用&#xff0c;从而影响应用程序的整体性能。应当尽量避免事后才想起添加索引&#xff0c;因为事后可能需要监控大量的SQL才能定位到问题所在&#xff0c;而且添加索…...

CSS-长度单位篇

px&#xff1a;像素em&#xff1a;相对元素font-size的倍数rem&#xff1a;相对根字体大小&#xff0c;html标签就是根%&#xff1a;相对父元素计算 注意&#xff1a;CSS中设置长度&#xff0c;必须加单位&#xff0c;否则样式无效&#xff01;...

自己动手实现一个深度学习算法——七、卷积神经网络

文章目录 1.整体结构2.卷积层1&#xff09;全连接层存在的问题2&#xff09;卷积运算3&#xff09;填充4&#xff09;步幅5&#xff09;3维数据的卷积运算6&#xff09;结合方块思考7&#xff09;批处理 3.池化层1&#xff09;池化层的特征 4.卷积层和池化层的实现1&#xff09…...

office word 使用笔记

office word 使用笔记 1. 功能1.1 格式快捷键1.2 复选框 2 遇到过的问题2.1 表格标题和表格距离过大 1. 功能 1.1 格式快捷键 复制格式&#xff1a;ctrl shift c 粘贴格式&#xff1a;ctrl shift v 1.2 复选框 方框位置和类型&#xff1a;“插入——高级符号——字体”选…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

sqlserver 根据指定字符 解析拼接字符串

DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

Scrapy-Redis分布式爬虫架构的可扩展性与容错性增强:基于微服务与容器化的解决方案

在大数据时代&#xff0c;海量数据的采集与处理成为企业和研究机构获取信息的关键环节。Scrapy-Redis作为一种经典的分布式爬虫架构&#xff0c;在处理大规模数据抓取任务时展现出强大的能力。然而&#xff0c;随着业务规模的不断扩大和数据抓取需求的日益复杂&#xff0c;传统…...