当前位置: 首页 > 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;“插入——高级符号——字体”选…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)

说明&#xff1a; 想象一下&#xff0c;你正在用eNSP搭建一个虚拟的网络世界&#xff0c;里面有虚拟的路由器、交换机、电脑&#xff08;PC&#xff09;等等。这些设备都在你的电脑里面“运行”&#xff0c;它们之间可以互相通信&#xff0c;就像一个封闭的小王国。 但是&#…...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

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

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

ElasticSearch搜索引擎之倒排索引及其底层算法

文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...

用docker来安装部署freeswitch记录

今天刚才测试一个callcenter的项目&#xff0c;所以尝试安装freeswitch 1、使用轩辕镜像 - 中国开发者首选的专业 Docker 镜像加速服务平台 编辑下面/etc/docker/daemon.json文件为 {"registry-mirrors": ["https://docker.xuanyuan.me"] }同时可以进入轩…...

基于matlab策略迭代和值迭代法的动态规划

经典的基于策略迭代和值迭代法的动态规划matlab代码&#xff0c;实现机器人的最优运输 Dynamic-Programming-master/Environment.pdf , 104724 Dynamic-Programming-master/README.md , 506 Dynamic-Programming-master/generalizedPolicyIteration.m , 1970 Dynamic-Programm…...

算法岗面试经验分享-大模型篇

文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer &#xff08;1&#xff09;资源 论文&a…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...