C/C++ BM6判断链表中是否有环
文章目录
- 前言
- 题目
- 解决方案一
- 1.1 思路阐述
- 1.2 源码
- 解决方案二
- 2.1 思路阐述
- 2.2 源码
- 总结
前言
做了一堆单链表单指针的题目,这次是个双指针题,这里双指针的作用非常明显。
题目
判断给定的链表中是否有环。如果有环则返回true,否则返回false。
数据范围:链表长度 0≤n≤10000,链表中任意节点的值满足 ∣val∣<=100000
要求:空间复杂度 O(1),时间复杂度 O(n)
输入分为两部分,第一部分为链表,第二部分代表是否有环,然后将组成的head头结点传入到函数里面。-1代表无环,其它的数字代表有环,这些参数解释仅仅是为了方便读者自测调试。实际在编程时读入的是链表的头节点。
例如输入{3,2,0,-4},1时,对应的链表结构如下图所示:
示例1
输入:{3,2,0,-4},1
返回值:true
说明:第一部分{3,2,0,-4}代表一个链表,第二部分的1表示,-4到位置1(注:头结点为位置0),即-4->2存在一个链接,组成传入的head为一个带环的链表,返回true
示例2
输入:{1},-1
返回值:false
说明:第一部分{1}代表一个链表,-1代表无环,组成传入head为一个无环的单链表,返回false
示例3
输入:{-1,-7,7,-4,19,6,-9,-5,-2,-5},6
返回值:true
解决方案一
1.1 思路阐述
采用双指针法。
对于一个链表,链表中的节点的值可能会相同,所以我们很难通过值来判断是否有环。但是在链表中,每一个链表节点在内存中的地址是不一样的,所以我们比较节点与节点之间的地址信息。
双指针法:一个指针fast每次间隔一个节点进行遍历,一个指针slow每次按序遍历。通常,间隔遍历的指针fast会首先到达链表表尾,或者表尾的下一个指针即nullptr
。那么如果对于有环的情况,fast会再次回到它所指的前面的节点;slow指针按序遍历,依次前进一个,如果链表没有环,那么slow和fast都会到达链尾。如果有环,fast一定会到达slow所指的节点位置。
这里打个比方,A和B同时在400m跑道上赛跑,A跑得快,B跑的慢。同时起跑,A跑的比B快,AB之间的距离不断拉大,A到后面超过B一圈了,那么超过B一圈的时候,A和B又在跑道上碰上了。这就是我上面写的如果有环,fast一定会到达slow所指的节点位置。
对于循环的终止条件:我们只需要判断fast指针是否遍历到链尾或者链尾的后一个节点空指针。
1.2 源码
#include <cstddef>
class Solution {
public:bool hasCycle(ListNode *head) {if(!head)return false;ListNode *fast=head;ListNode *slow=head;//这里nullptr和NULL效果一样,但在某些地方有点不同,可以查一下互联网//while (fast!=nullptr&&fast->next!=nullptr) {while (fast!=NULL&&fast->next!=NULL) {fast=fast->next->next;slow=slow->next;if(fast==slow)return true;}return false;}
};
解决方案二
2.1 思路阐述
思路一是用双指针,思路二就是哈希了。
在C++中的STL有一个set容器,在C++中,std::set 是标准模板库(STL)中的一个容器,它是一个有序的关联容器,用于存储不重复的元素。每个元素在 std::set 中都有唯一的键值,而且它们按照升序进行排序。
所以刚才我们提到的比较节点是比较内存地址而非值,所以我们在set中存放的应该是ListNode *
。
接下来的事情就很简单了,我每次存一个内存地址,如果出现内存地址相同的情况,那就是有环。
2.2 源码
class Solution {
public:bool hasCycle(ListNode *head) {std::set<ListNode*> node_set;while(head){//如果查找head节点对应的内存地址找到相同的了,并且这个地址不是set的最后一个元素,那么就是有环if(node_set.find(head)!=node_set.end()){return true;}node_set.insert(head);head=head->next;}return false;}
};
总结
如何判断链表有环的情况,之前没遇到过。所以第一次做的时候有点懵逼,同时对双指针的使用上并不是特别熟悉,这道题在初期思考的时候都是想着怎么用单链表加标志位的情况来判断。还是有点草率了。
相关文章:

C/C++ BM6判断链表中是否有环
文章目录 前言题目解决方案一1.1 思路阐述1.2 源码 解决方案二2.1 思路阐述2.2 源码 总结 前言 做了一堆单链表单指针的题目,这次是个双指针题,这里双指针的作用非常明显。 题目 判断给定的链表中是否有环。如果有环则返回true,否则返回fal…...

【Java 设计模式】结构型之适配器模式
文章目录 1. 定义2. 应用场景3. 代码实现结语 适配器模式(Adapter Pattern)是一种结构型设计模式,用于将一个类的接口转换成客户端期望的另一个接口。这种模式使得原本由于接口不兼容而不能一起工作的类可以一起工作。在本文中,我…...

使用函数计算,数禾如何实现高效的数据处理?
作者:邱鑫鑫,王彬,牟柏旭 公司背景和业务 数禾科技以大数据和技术为驱动,为金融机构提供高效的智能零售金融解决方案,服务银行、信托、消费金融公司、保险、小贷公司等持牌金融机构,业务涵盖消费信贷、小…...

卷积和滤波对图像操作的区别
目录 问题引入 解释 卷积 滤波 问题引入 卷积和滤波是很相似的,都是利用了卷积核进行操作 那么他们之间有什么区别呢? 卷积:会影响原图大小 滤波:不会影响原图大小 解释 卷积 我们用这样一段代码来看 import torch.nn as …...
李沐深度学习-线性回归从零开始
# 核心Tensor,autograd import torch from IPython import display import numpy as np import random from matplotlib import pyplot as pltimport syssys.path.append(路径) from d2lzh_pytorch import * backward()函数:一次小批量执行完在进行反向传播 线性回归…...

CentOS 8.5 安装图解
特特特别的说明 CentOS发行版已经不再适合应用于生产环境,客观条件不得不用的话,优选7.9版本,8.5版本次之,最次6.10版本(比如说Oracle 11GR2就建议在6版本上部署)! 引导和开始安装 选择倒计时结…...

好用的流程图工具
分享工作中常用的装逼工具 目前市面上的流程图或者思维导图工具挺多的,但是有的会限制使用数量或者收费,典型的有processon、Xmind,推荐今天Mermaid(官网)。 快速上手 中文教程:Mermaid 初学者用户指南 | Mermaid 中文网。我们选择…...

数据结构:链式栈
stack.h /* * 文件名称:stack.h * 创 建 者:cxy * 创建日期:2024年01月18日 * 描 述: */ #ifndef _STACK_H #define _STACK_H#include <stdio.h> #include <stdlib.h>typedef struct stack{int data…...
openssl3.2 - 官方demo学习 - mac - gmac.c
文章目录 openssl3.2 - 官方demo学习 - mac - gmac.c概述笔记END openssl3.2 - 官方demo学习 - mac - gmac.c 概述 使用GMAC算法, 设置参数(指定加密算法 e.g. AES-128-GCM, 设置iv) 用key执行初始化, 然后对明文生成MAC数据 官方注释给出建议, key, iv最好不要硬编码出现在程…...

HugggingFace 推理 API、推理端点和推理空间相关模型部署和使用以及介绍
HugggingFace 推理 API、推理端点和推理空间相关模型部署和使用以及介绍。 Hugging Face是一家开源模型库公司。 2023年5月10日,Hugging Face宣布C轮1亿美元融资,由Lux Capital领投,红杉资本、Coatue、Betaworks、NBA球星Kevin Durant等跟投…...

python的tabulate包在命令行下输出表格不对齐
用tabulate可以在命令行下输出表格。 from tabulate import tabulate# 定义表头 headers [列1, 列2, 列3]# 每行的内容 rows [] rows.append((张三,数学,英语)) rows.append((李四,信息科技,数学))# 使用 tabulate 函数生成表格 output tabulate(rows, headersheaders, tab…...

LLM之幻觉(二):大语言模型LLM幻觉缓减技术综述
LLM幻觉缓减技术分为两大主流,梯度方法和非梯度方法。梯度方法是指对基本LLM进行微调;而非梯度方法主要是在推理时使用Prompt工程技术。LLM幻觉缓减技术,如下图所示: LLM幻觉缓减技术值得注意的是: 检索增强生成&…...
C# 使用多线程,关闭窗体时,退出所有线程
this.Close(); 只是关闭当前窗口,若不是主窗体的话,是无法退出程序的,另外若有托管线程(非主线程),也无法干净地退出;Application.Exit(); 强制所有消息中止,退出所有的窗体&…...

数据结构实验6:图的应用
目录 一、实验目的 1. 邻接矩阵 2. 邻接矩阵表示图的结构定义 3. 图的初始化 4. 边的添加 5. 边的删除 6. Dijkstra算法 三、实验内容 实验内容 代码 截图 分析 一、实验目的 1.掌握图的邻接矩阵的存储定义; 2.掌握图的最短路径…...

Spring Boot整合JUnit
引言 测试是软件开发过程中不可或缺的一环,而JUnit作为Java生态中最流行的测试框架之一,与Spring Boot的整合为开发者提供了一套强大的测试工具。本文将讨论Spring Boot整合JUnit的技术细节、最佳实践以及测试驱动开发(TDD)的优雅…...
uniapp写小程序实现清除缓存(存储/获取/移除/清空)
在uni-app中,可以使用uni.setStorageSync和uni.getStorageSync来进行数据的存储和获取。而移除缓存数据可以使用uni.removeStorageSync,清空缓存数据可以使用uni.clearStorageSync。 以下是使用示例: 存储数据: uni.setStorage…...

js菜单隐藏显示
1、树状结构对应的表: 2、生成menulist的SQL语句 select {"id":"MenuID","parent":"ParentID","FirstLvMenu":"FirstLvMenu", "text":"MenuName","url":"MenuUrl",&quo…...

学习Spring的第五天(Bean的依赖注入)
Bean的依赖注入有两种方式: 一 . 常规Bean的依赖注入 很简单,不过多赘述了,注意ref: 是构造函数或set方法的参数,一般为对象, value: 是构造函数或set方法的参数,一般为值. 看下图 1.1 下面来演示一下集合数据类型的关于Bean的依赖注入 1.1.1这是List的注入(演示泛型为Strin…...

GAN在图像数据增强中的应用
在图像数据增强领域,生成对抗网络(GAN)的应用主要集中在通过生成新的图像数据来扩展现有数据集的规模和多样性。这种方法特别适用于训练数据有限的情况,可以通过增加数据的多样性来提高机器学习模型的性能和泛化能力。 以下是GAN在…...
Git推送本地文件到仓库
1. 在 Gitee 上创建一个新的仓库: 登录到 Gitee(https://gitee.com)账号。在 Gitee 主页上选择 "新建仓库" 或类似选项。输入仓库名称和描述,并选择其他相关选项(如公开/私有)。确认创建仓库 …...

使用docker在3台服务器上搭建基于redis 6.x的一主两从三台均是哨兵模式
一、环境及版本说明 如果服务器已经安装了docker,则忽略此步骤,如果没有安装,则可以按照一下方式安装: 1. 在线安装(有互联网环境): 请看我这篇文章 传送阵>> 点我查看 2. 离线安装(内网环境):请看我这篇文章 传送阵>> 点我查看 说明:假设每台服务器已…...

【OSG学习笔记】Day 18: 碰撞检测与物理交互
物理引擎(Physics Engine) 物理引擎 是一种通过计算机模拟物理规律(如力学、碰撞、重力、流体动力学等)的软件工具或库。 它的核心目标是在虚拟环境中逼真地模拟物体的运动和交互,广泛应用于 游戏开发、动画制作、虚…...

Zustand 状态管理库:极简而强大的解决方案
Zustand 是一个轻量级、快速和可扩展的状态管理库,特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
C# SqlSugar:依赖注入与仓储模式实践
C# SqlSugar:依赖注入与仓储模式实践 在 C# 的应用开发中,数据库操作是必不可少的环节。为了让数据访问层更加简洁、高效且易于维护,许多开发者会选择成熟的 ORM(对象关系映射)框架,SqlSugar 就是其中备受…...

SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
Spring是如何解决Bean的循环依赖:三级缓存机制
1、什么是 Bean 的循环依赖 在 Spring框架中,Bean 的循环依赖是指多个 Bean 之间互相持有对方引用,形成闭环依赖关系的现象。 多个 Bean 的依赖关系构成环形链路,例如: 双向依赖:Bean A 依赖 Bean B,同时 Bean B 也依赖 Bean A(A↔B)。链条循环: Bean A → Bean…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
Go语言多线程问题
打印零与奇偶数(leetcode 1116) 方法1:使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...