链表经典面试题之二

 今天我们做一道环形链表的题目力扣141题https://leetcode.cn/problems/linked-list-cycle/

 这道题让我们分析链表中是否存环,存在的话返回true,不存在返回false。首先看到这道题我们要捋顺思路,怎么才能达到它要的效果?要找出是否存在一个环,那么我们能不能看看尾结点的下一个结点是不是之前出现过的结点呢?我们在仔细想一想,如果有环的话,存在尾结点吗?当然不存在,如果环存在的话,就没有尾结点,都已经叫尾结点了那肯定就是最后一个结点。所以我们不妨改变思路,用快慢双指针的方式做这道题目。

struct ListNode *fast=head;
struct ListNode *slow=head;

我们定义fast一次走两步,slow一次走一步,如果有环fast肯定先进环一直在换里面转,当slow进环的时候两个指针距离相差为N,而fast和slow每走一步,距离就减少1,总会存在,距离为0的情况,当fast=slow的时候,存在环,否则不存在;

 

while(){slow=slow->next;fast=fast->next->next;if(slow==fast)return true;}return false;

 但是这个while循环的条件怎么判断呢?什么时候循环停下?fast走的快,当fast走到尾为空的时候停下,有人会有疑问,不是有环的时侯链表没有尾吗?是的,但是我们这个判断是循环停下的条件,如果循环没有进循环时不时就是没有环就直接返回false了呢?

while(fast){slow=slow->next;fast=fast->next->next;if(slow==fast)return true;}return false;

这样就结束了吗?我们运行会发现它报了一个空指针的错误

到底哪里出现空指针了呢?我们想一下当时fast一次走两步,fast=fast->next->next,我们只判断了当fast==NULL的时候循环停止,是不是忽略掉fast->next的时候到空了呢?这个时候,fast->next还能指向next吗?所以,这个循环应该是while(fast&&fast->next)才可以。

struct ListNode *fast=head;
struct ListNode *slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(slow==fast)return true;}return false;

当我们这样写完,运行就通过啦

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

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

相关文章

transformers安装避坑

1.4 下载rust编辑器 看到这里你肯定会疑惑了,我们不是要用python的吗? 这个我也不知道,你下了就对了,不然后面的transformers无法安装 因为是windows到官网选择推荐的下载方式https://www.rust-lang.org/tools/install。 执行文…

开发知识点-Ant-Design-Vue

Ant-Design-Vue a-input a-input Vue组件 a-spin 加载中的效果 data字段 mounted钩子函数 Ant Design Vue 组件库 list-type“picture-card” 上传的图片作为卡片展示 name show-upload-list action :beforeUpload“handleBeforeUpload” :headers“customHeaders” :disabl…

剑指JUC原理-16.读写锁

👏作者简介:大家好,我是爱吃芝士的土豆倪,24届校招生Java选手,很高兴认识大家📕系列专栏:Spring源码、JUC源码🔥如果感觉博主的文章还不错的话,请👍三连支持&…

11-09 周四 CNN 卷积神经网络基础知识

11-09 周四 CNN 卷积神经网络 时间版本修改人描述2023年11月9日09:38:12V0.1宋全恒新建文档 简介 学习一下CNN&#xff0c;卷积神经网络。使用的视频课程。视觉相关的任务&#xff1a; 人脸识别 卷积网络与传统网络的区别&#xff1a; <img altimage-20231109094400591 s…

专业128分总分390+上岸中山大学884信号与系统电通院考研经验分享

专业课884 信号系统 过年期间开始收集报考信息&#xff0c;找到了好几个上岸学姐和学长&#xff0c;都非常热情&#xff0c;把考研的准备&#xff0c;复习过程中得与失&#xff0c;都一一和我分享&#xff0c;非常感谢。得知这两年专业课难度提高很多&#xff0c;果断参加了学长…

QT 布局管理综合实例

通过一个实例基本布局管理&#xff0c;演示QHBoxLayout类、QVBoxLayout类及QGridLayout类效果 本实例共用到四个布局管理器&#xff0c;分别是 LeftLayout、RightLayout、BottomLayout和MainLayout。 在源文件“dialog.cpp”具体代码如下&#xff1a; 运行效果&#xff1a; Se…

外部访问K8S集群内部的kafka集群服务

不许转载 kafka 部署 把 kafka 部署到 k8s 后&#xff0c;我们肯定是通过 service 从 k8s 外部访问 kafaka。这里的 service 要么是 NodePort&#xff0c; 要么是 LoadBalancer 类型。我们使用的方式是 LoadBalancer。 我们先看下面这张图&#xff0c;这是 kafka 在集群中的网…

从F5 BIG-IP RCE漏洞(CVE-2023-46747)来看请求走私的利用价值

0x01 前言 F5 BIG-IP广域流量管理器是一种网络流量管理设备&#xff0c;用于提升链路性能与可用性。F5在金融行业具有特别广泛的使用量&#xff0c;做过各大银行攻防演练的小伙伴对这个系统应该不会陌生。 最近爆出的CVE-2023-46747漏洞能达到远程RCE的效果&#xff0c;属于严重…

软件测试之冒烟测试详解

1. 核心 冒烟测试就是完成一个新版本的开发后&#xff0c;对该版本最基本的功能进行测试&#xff0c;保证基本的功能和流程能走通。 如果不通过&#xff0c;则打回开发那边重新开发&#xff1b; 如果通过测试&#xff0c;才会进行下一步的测试(功能测试&#xff0c;集成测试…

EDA实验----四选一多路选择器设计(QuartusII)

目录 一&#xff0e;实验目的 二&#xff0e;实验仪器设备 三&#xff0e;实验原理&#xff1a; 四&#xff0e;实验要求 五&#xff0e;实验内容及步骤 1.实验内容 2.实验步骤 六&#xff0e;实验报告 七.实验过程 1.创建Verilog文件&#xff0c;写代码 2.波形仿真 …

图扑智慧农业:农林牧数据可视化监控平台

数字农业是一种现代农业方式&#xff0c;它将信息作为农业生产的重要元素&#xff0c;并利用现代信息技术进行农业生产过程的实时可视化、数字化设计和信息化管理。能将信息技术与农业生产的各个环节有机融合&#xff0c;对于改造传统农业和改变农业生产方式具有重要意义。 图…

浙江大学漏洞报送证书

获取来源&#xff1a;edusrc&#xff08;教育漏洞报告平台&#xff09; url&#xff1a;主页 | 教育漏洞报告平台 兑换价格&#xff1a;20金币 获取条件&#xff1a;提交浙江大学任意中危或以上级别漏洞

Leetcode刷题详解—— 组合总和

1. 题目链接&#xff1a;39. 组合总和 2. 题目描述&#xff1a; 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target &#xff0c;找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 &#xff0c;并以列表形式返回。你可以按 任意顺序 返回这些…

To create the 45th Olympic logo by using CSS

You are required to create the 45th Olympic logo by using CSS. The logo is composed of five rings and three rectangles with rounded corners. The HTML code has been given. It is not allowed to add, edit, or delete any HTML elements. 私信完整源码 <!DOCT…

docker下的nginx代理转发到tomcat

多次尝试失败原因&#xff0c;修改nginx配置文件以后&#xff0c;需要./nginx.sh -s reload 下&#xff0c;之前一直不转发&#xff0c;好像完全没有跳转的意思&#xff0c;后来查了多篇文档&#xff0c;最简单的方法如下 docker 安装 nginx 和tomcat就不多说了&#xff0c;可…

红黑树-RBTree

目录 1. 红黑树的概念2. 红黑树的性质3. 结点的定义4. 结点的插入5. 整体代码 1. 红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式…

Cesium 相机设置

1.setView 直接跳转到目的地 // 设置相机位置 const position Cesium.Cartesian3.fromDegrees(113, 31, 20000); // setView通过定义相机目的地&#xff08;方向&#xff09;,直接跳转到目的地 viewer.camera.setView({ destination: position, // 位置设置 orientation: { //…

基于自然语言处理的结构化数据库问答机器人系统

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长 Wechat / QQ 名片 :) 1. 项目简介 知识库&#xff0c;就是人们总结出的一些历史知识的集合&#xff0c;存储、索引以后&#xff0c;可以被方便的检索出来供后人查询/学习。QnA Maker是用于建立知识库的工具&#xff0c;使用…

YOLOv8-Seg改进:分割注意力系列篇 | 高效的通道先验卷积注意力(CPCA) | 中科院 2023.6

🚀🚀🚀本文改进:高效的通道先验卷积注意力(CPCA)方法,支持注意力权重在通道和空间维度上的动态分布; 🚀🚀🚀CPCA 小目标分割检测&复杂场景首选,实现涨点 🚀🚀🚀YOLOv8-seg创新专栏:http://t.csdnimg.cn/KLSdv 学姐带你学习YOLOv8,从入门到创新…

C++初阶--类与对象(3)(图解)

文章目录 再谈构造函数初始化列表隐式类型转换explicit关键字 static成员友元类内部类匿名对象拷贝函数时的一些优化 再谈构造函数 在我们之前的构造函数中&#xff0c;编译器会通过构造函数&#xff0c;对对象中各个成员给出一个适合的初始值&#xff0c;但这并不能称之为初始…