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

《程序员面试金典(第6版)》面试题 02.08. 环路检测(哈希法,双指针,检测链表是否有环)

题目描述

给定一个链表,如果它是有环链表,实现一个算法返回环路的开头节点。若环不存在,请返回 null。
题目传送门:面试题 02.08. 环路检测

  • 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。

示例 1:

在这里插入图片描述

 输入:head = [3,2,0,-4], pos = 1输出:tail connects to node index 1解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

在这里插入图片描述

输入:head = [1,2], pos = 0
输出:tail connects to node index 0
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

在这里插入图片描述

输入:head = [1], pos = -1
输出:no cycle
解释:链表中没有环。

进阶:

  • 你是否可以不用额外空间解决此题?

解题思路与代码

  • 这道题算是比较简单的一道题。检测链表是否存在环的最简单的一种方法是哈希法,其次就是快慢指针法。那么前者的空间复杂度可能会高些,但是代码结构简单易懂。

  • 后者虽然说比前者稍微难点,但也没有难太多,多了一点点的思考量而已。

总的来说,这道题是一道好题,考验了你一点点的数学思维,与链表的实际操作

方案一:哈希法

这道题如果是单单的判断链表是否成环,那这道题就是一道简单题,如果还要让你去返回成环的开头节点,那这道题的难度就要上升了。

对于这道题,如果我们用了哈希法,那就是降维打击,因为我们利用unordered_set就可以直接帮你返回相同节点。
具体的代码如下:

class Solution {
public:ListNode *detectCycle(ListNode *head) {unordered_set<ListNode*> set;while(head){if(set.count(head)) return head;set.insert(head);head = head->next;}return nullptr;}
};

在这里插入图片描述

复杂度分析:

  • 时间复杂度:O(n),其中n是链表节点的个数
  • 空间复杂度:O(n),我们需要将链表的每一个节点放入集合中,所以是O(n)

方案二: 快慢指针法

  • 先解释一下这里的快慢指针法是什么意思。在这里,我们先设置两个指针,p1,p2。 p1一次走一格,p2一次走两个。因为他们走的步数不一样,所以,如果链表中有环存在了话,那么p1,p2一定不会相等。反之,如果有环,那p1,p2一定会相等。

那这道题的难点在成环节点,在距离头节点多少位置呢?首先,我们要画图分析。
在这里插入图片描述

  • 我们设从头节点,到成环节点的距离为a,成环节点到p2追到p1的距离为b,被追到的p1节点距离再次回到成环节点的距离为c。

  • p2指针一次走两格,p1指针一次走一格,p2追上p1的时候,p2走过的距离是p1的两倍。

  • p1被追到时p2走了a + n(b + c) + b,p1走了a + b所以不难得出这个等式:a + n(b + c) + b = 2(a + b)

  • 将这个等式变化一下便是 **a = c + (n-1)(b+c)**么。

看着这个图,我们来翻译一个这个数学等式的意思。

  • 假设从头节点走了a步,到达了成环节点。便等于我在相遇节点走了 c 步 + n圈。
  • 我们在p1节点与p2节点相遇的时候,再去设置一个p3节点让它等于头节点。这个时候,p3也一次走一步。
  • 你看图,当p3在头节点走了a步的时候,是不是正好与p1在b的时候走了c步 + n圈呢?

具体代码如下:

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode* p1 = head;ListNode* p2 = head;while(p2){p1 = p1->next;if(p2->next)p2 = p2->next->next;else return nullptr;if(p1 == p2) {ListNode* p3 = head;while(p3!=p1){p1 = p1->next;p3 = p3->next;}return p3;}}return nullptr;}
};

在这里插入图片描述

复杂度分析:

  • 时间复杂度:O(N),N为节点的长度。因为你在实际推演的过程中会发现,p1指针走过的最长的路程也不会超过链表中节点的个数,而是等于节点的个数,所以时间复杂度是O(N)
  • 空间复杂度:O(1),我们设置了几个变量而已,没有使用额外的数据结构,所以是O(1)。

总结

这道题目是一个经典的链表问题,经常出现在计算机科学和软件工程的面试和教程中。

这道题目的主要意义和重要性可以从以下几个方面来看:

  • 数据结构理解与应用:这道题目需要你理解和操作链表这种基础数据结构。理解数据结构的特性和操作方法是编程和算法学习的基础。

  • 双指针技巧:这道题目需要使用到双指针(快慢指针)的技巧。这是一个常用的算法设计策略,可以帮助解决一些看似复杂的问题。

  • 算法分析:通过这道题目,你需要理解和分析算法的时间复杂度和空间复杂度。这道题的解决方案有一个很好的性质:它只需要常量的额外空间,且时间复杂度为线性。

  • 问题解决和调试能力:这道题目也可以帮助你提升问题解决和调试的能力。理解为什么这个解决方案能够工作,对于提升你的算法设计和问题解决能力是非常有帮助的。

所以,这道题目的意义不仅仅是解决一个具体的问题,更重要的是通过这个问题来学习和提升你的数据结构知识,算法设计和问题解决能力。

最后的最后,如果你觉得我的这篇文章写的不错的话,请给我一个赞与收藏,关注我,我会继续给大家带来更多更优质的干货内容

相关文章:

《程序员面试金典(第6版)》面试题 02.08. 环路检测(哈希法,双指针,检测链表是否有环)

题目描述 给定一个链表&#xff0c;如果它是有环链表&#xff0c;实现一个算法返回环路的开头节点。若环不存在&#xff0c;请返回 null。 题目传送门&#xff1a;面试题 02.08. 环路检测 如果链表中有某个节点&#xff0c;可以通过连续跟踪 next 指针再次到达&#xff0c;则链…...

软考A计划-试题模拟含答案解析-卷六

点击跳转专栏>Unity3D特效百例点击跳转专栏>案例项目实战源码点击跳转专栏>游戏脚本-辅助自动化点击跳转专栏>Android控件全解手册点击跳转专栏>Scratch编程案例 &#x1f449;关于作者 专注于Android/Unity和各种游戏开发技巧&#xff0c;以及各种资源分享&am…...

Linux 上的 .NET 崩溃了怎么抓 Dump

一&#xff1a;背景 1. 讲故事 训练营中有朋友问在 Linux 上如何抓 crash dump&#xff0c;在我的系列文章中演示的大多是在 Windows 平台上&#xff0c;这也没办法要跟着市场走&#xff0c;谁让 .NET 的主战场在工控 和 医疗 呢&#xff0c;上一张在 合肥 分享时的一个统计图…...

QT桌面项目(状态栏和导航栏设置)

文章目录 前言一、状态栏二、导航栏三、同时添加状态栏和导航栏总结 前言 为了和我们这个项目做的更加真实&#xff0c;这里为我们的项目添加上状态栏和导航栏让他变成更加接近手机的桌面效果。 一、状态栏 这个状态栏就是显示时间和wifi状态&#xff0c;电池电量的&#xf…...

数据链路层:点对点协议PPP

数据链路层&#xff1a;点对点协议PPP 笔记来源&#xff1a; 湖科大教书匠&#xff1a;点对点协议PPP 声明&#xff1a;该学习笔记来自湖科大教书匠&#xff0c;笔记仅做学习参考 数据链路层只负责直接相连的两个结点之间的通信 PPP是点对点数据链路层协议 用户通过ISP接入因特…...

C/C++读取txt文件中的float数据并用指针存储

C语言中读取txt文件中的数据 以下是一个简单的示例代码&#xff0c;演示如何在C语言中读取txt文件中的数据&#xff1a; #include <stdio.h>int main() {FILE *fp;char buffer[100];// 打开文件fp fopen("example.txt", "r");// 如果文件打开失败…...

对KMP算法的一点碎碎念——上篇

对KMP算法的一点碎碎念——上篇 文章目录 对KMP算法的一点碎碎念——上篇1. KMP 算法 Next数组 求解问题1.1 前置知识-最长公共前后缀LCP1.1.1 前缀与后缀1.1.2 最长公共前后缀LCP 1.2 手算法求解 Next数组值(3种常见情况)1.2.1 情况1: next数组 正常存放匹配字符的长度情况1的…...

算法---边界着色

题目 给你一个大小为 m x n 的整数矩阵 grid &#xff0c;表示一个网格。另给你三个整数 row、col 和 color 。网格中的每个值表示该位置处的网格块的颜色。 两个网格块属于同一 连通分量 需满足下述全部条件&#xff1a; 两个网格块颜色相同 在上、下、左、右任意一个方向上…...

二叉排序树的查找、插入、删除

目录 二叉排序树的定义 二叉排序树的查找 二叉排序树的插入 二叉排序树的定义 二叉排序树的定义 二叉排序树&#xff08;Binary Sort Tree&#xff0c; BST&#xff09;&#xff0c;也称二叉查找树。 二叉排序树或者是一棵空树&#xff0c;或者是一棵具有下列特性的非空二叉…...

《Opencv3编程入门》学习笔记—第三章

《Opencv3编程入门》学习笔记 记录一下在学习《Opencv3编程入门》这本书时遇到的问题或重要的知识点。 第三章 HighGUI图形用户界面初步 一、图像的载入、显示和输出到文件 &#xff08;一&#xff09;OpenCV的命名空间 简单的OpenCV程序标配&#xff1a; #include <o…...

如何从Ubuntu Linux中删除Firefox Snap?

Ubuntu Linux是一款广受欢迎的开源操作系统&#xff0c;拥有强大的功能和广泛的应用程序选择。默认情况下&#xff0c;Ubuntu提供了一种称为Snap的软件打包格式&#xff0c;用于安装和管理应用程序。Firefox是一款流行的开源网络浏览器&#xff0c;而Firefox Snap是Firefox的Sn…...

数学建模的初阶-快速上手

目录 第一步&#xff1a;明确问题 第二步&#xff1a;选择建模方法 第三步&#xff1a;收集数据 第四步&#xff1a;构建数学模型 第五步&#xff1a;模型验证与评估 数学建模软件推荐 统计模型 (1) 线性回归模型 (2) 逻辑回归模型 (3) 时间序列模型 优化模型 (1) …...

复习向 C/C++ 编程语言简介和概括(C++复习向p1)

文章目录 C 编程语言C 和 C 关系标准的 C 组成ANSI 标准比较重要的标准化时间 C 编程语言 是一种静态类型的、编译式的、通用式的、大小写敏感、不规则的编程语言支持过程化编程&#xff0c;面向对象&#xff0c;泛型编程 C 和 C 关系 C 是 C 的一个超集&#xff0c;任何合法…...

DRF之过滤,排序,分页

一、权限组件源码解读 1.继承了APIView 才有的---》执行流程---》dispatch中----》三大认证 APIView的dispatch def initial(self, request, *args, **kwargs):self.perform_authentication(request)self.check_permissions(request)self.check_throttles(request) 2 读…...

我的Redis学习,共写了14篇博客文章

早在19和20年全面学习SpringBoot相关技术知识时也曾经有学习到Redis&#xff0c;主要是看了几家的视频教程&#xff0c;但是未曾有具体的实践&#xff0c;后来再学习到Docker和Spring Session框架的Redis存储时&#xff0c;又稍微的实践了一丢丢&#xff0c;所有的实践也就仅此…...

mPython软件使用指南

①软件界面 一、软件界面的介绍 1.模式切换 硬件编程 Python3.6 Jupyter python3.6模式细节补充&#xff08;一般不使用该模式&#xff0c;此处可跳过&#xff09; Python3.6模式的界面 左侧指令分类栏 Python3.6模式的图形化指令分类分为&#xff1a; Python语法基础相关指令&…...

龙芯2K1000实战开发-系统配置详解

目录 概要 整体架构流程 技术名词解释 技术细节 ​编辑 总结...

【一起撸个DL框架】5 实现:自适应线性单元

CSDN个人主页&#xff1a;清风莫追欢迎关注本专栏&#xff1a;《一起撸个DL框架》GitHub获取源码&#xff1a;https://github.com/flying-forever/OurDLblibli视频合集&#xff1a;https://space.bilibili.com/3493285974772098/channel/series 文章目录 5 实现&#xff1a;自适…...

开箱即用的工具函数库xijs更新指南(v1.2.6)

xijs 是一款开箱即用的 js 业务工具库, 聚集于解决业务中遇到的常用函数逻辑问题, 帮助开发者更高效的开展业务开发. 接下来就和大家一起分享一下 v1.2.6 版本的更新内容以及后续的更新方向. 贡献者列表: 1. 计算变量内存calculateMemory 该模块主要由 zhengsixsix 贡献, 我们可…...

【Netty】ChannelPipeline源码分析(五)

文章目录 前言一、ChannelPipeline 接口1.1 创建 ChannelPipeline1.2 ChannelPipeline 事件传输机制1.2.1 处理出站事件1.2.2 处理入站事件 二、ChannelPipeline 中的 ChannelHandler三、ChannelHandlerContext 接口3.1 ChannelHandlerContext 与其他组件的关系3.2 跳过某些 Ch…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

vscode(仍待补充)

写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh&#xff1f; debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

稳定币的深度剖析与展望

一、引言 在当今数字化浪潮席卷全球的时代&#xff0c;加密货币作为一种新兴的金融现象&#xff0c;正以前所未有的速度改变着我们对传统货币和金融体系的认知。然而&#xff0c;加密货币市场的高度波动性却成为了其广泛应用和普及的一大障碍。在这样的背景下&#xff0c;稳定…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

Python 实现 Web 静态服务器(HTTP 协议)

目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1&#xff09;下载安装包2&#xff09;配置环境变量3&#xff09;安装镜像4&#xff09;node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1&#xff09;使用 http-server2&#xff09;详解 …...

OD 算法题 B卷【正整数到Excel编号之间的转换】

文章目录 正整数到Excel编号之间的转换 正整数到Excel编号之间的转换 excel的列编号是这样的&#xff1a;a b c … z aa ab ac… az ba bb bc…yz za zb zc …zz aaa aab aac…; 分别代表以下的编号1 2 3 … 26 27 28 29… 52 53 54 55… 676 677 678 679 … 702 703 704 705;…...

Python常用模块:time、os、shutil与flask初探

一、Flask初探 & PyCharm终端配置 目的: 快速搭建小型Web服务器以提供数据。 工具: 第三方Web框架 Flask (需 pip install flask 安装)。 安装 Flask: 建议: 使用 PyCharm 内置的 Terminal (模拟命令行) 进行安装,避免频繁切换。 PyCharm Terminal 配置建议: 打开 Py…...

【大模型】RankRAG:基于大模型的上下文排序与检索增强生成的统一框架

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构C.1 指令微调阶段C.2 排名与生成的总和指令微调阶段C.3 RankRAG推理&#xff1a;检索-重排-生成 D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;RankRAG&#xff1a;Unifying Context Ranking…...

记一次spark在docker本地启动报错

1&#xff0c;背景 在docker中部署spark服务和调用spark服务的微服务&#xff0c;微服务之间通过fegin调用 2&#xff0c;问题&#xff0c;docker容器中服务器来后&#xff0c;注册中心都有&#xff0c;调用服务也正常&#xff0c;但是调用spark启动任务后报错&#xff0c;报错…...