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 主页上选择 "新建仓库" 或类似选项。输入仓库名称和描述,并选择其他相关选项(如公开/私有)。确认创建仓库 …...

国防科技大学计算机基础课程笔记02信息编码
1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制,因此这个了16进制的数据既可以翻译成为这个机器码,也可以翻译成为这个国标码,所以这个时候很容易会出现这个歧义的情况; 因此,我们的这个国…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...

无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
如何为服务器生成TLS证书
TLS(Transport Layer Security)证书是确保网络通信安全的重要手段,它通过加密技术保护传输的数据不被窃听和篡改。在服务器上配置TLS证书,可以使用户通过HTTPS协议安全地访问您的网站。本文将详细介绍如何在服务器上生成一个TLS证…...
python如何将word的doc另存为docx
将 DOCX 文件另存为 DOCX 格式(Python 实现) 在 Python 中,你可以使用 python-docx 库来操作 Word 文档。不过需要注意的是,.doc 是旧的 Word 格式,而 .docx 是新的基于 XML 的格式。python-docx 只能处理 .docx 格式…...
3403. 从盒子中找出字典序最大的字符串 I
3403. 从盒子中找出字典序最大的字符串 I 题目链接:3403. 从盒子中找出字典序最大的字符串 I 代码如下: class Solution { public:string answerString(string word, int numFriends) {if (numFriends 1) {return word;}string res;for (int i 0;i &…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...

回溯算法学习
一、电话号码的字母组合 import java.util.ArrayList; import java.util.List;import javax.management.loading.PrivateClassLoader;public class letterCombinations {private static final String[] KEYPAD {"", //0"", //1"abc", //2"…...

GruntJS-前端自动化任务运行器从入门到实战
Grunt 完全指南:从入门到实战 一、Grunt 是什么? Grunt是一个基于 Node.js 的前端自动化任务运行器,主要用于自动化执行项目开发中重复性高的任务,例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...