一个简短的补充------对链表练习题的补充补充
昨天不是写了一篇有关链表的数据结构练习题嘛,其实那篇文章的第二道题还有许多值得我们思考的东西,今天就在这做一个简短的补充。补充一下运用那道题解决另一道题。 
给大家看一下绿色让眼睛放松一下。
给定一个链表的头节点 head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
这道题跟我说的昨天第二道题十分相似,但确实它的进阶版,这里我们要解决的是,除了判断它是否有环,还需找出它的环是哪个节点,这样一看,这题目好像确实是难上加难了,但是问题总是有对应的方法去解决的,这里我们不得不先丢出一个结论,大家先看等下我再解释。
结论: 一个指针从相遇的点走,另一个从链表的开头走,那么这两个指针一定会在入环的节点相遇。
那么现在我们给大家证明一下这个结论:
我们设不为环的地方为L,环的周长为C,N为正整数变量, 那么我们知道L的距离要么使C-X,异或N*C-X,那么只要相遇那么只要两指针往后走,那就一定可以在入环的位置相遇。
那么这时我们就可以根据这个结论解决这道题目了。
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode *detectCycle(struct ListNode *head) {if(head==NULL){return NULL;}
struct ListNode * fast=head;
struct ListNode * slow=head;while(fast && fast->next)
{fast=fast->next->next;
slow=slow->next;
if(slow==fast)
{struct ListNode *meet=fast;while(head!=meet){head=head->next;meet=meet->next;}return meet;}}return NULL;}
代码解析:我们通过第一个while循环找到有环链表的相遇位置meet,然后我们就可以让head和meet开始走,直到相遇,那么这个相遇的位置就是环的入口位置了。
那么这篇文章就结束了。
相关文章:
一个简短的补充------对链表练习题的补充补充
昨天不是写了一篇有关链表的数据结构练习题嘛,其实那篇文章的第二道题还有许多值得我们思考的东西,今天就在这做一个简短的补充。补充一下运用那道题解决另一道题。 给大家看一下绿色让眼睛放松一下。 给定一个链表的头节点 head ,返回链表…...
Spring最新核心高频面试题(持续更新)
1 什么是Spring框架 Spring框架是一个开源的Java应用程序开发框架,它提供了很多工具和功能,可以帮助开发者更快地构建企业级应用程序。通过使用Spring框架,开发者可以更加轻松地开发Java应用程序,并且可以更加灵活地组织和管理应…...
[计网底层小探索]:实现并部署多线程并发Tcp服务器框架(基于生产者消费者模型的线程池结构)
文章目录 一.网络层与传输层协议sockaddr结构体继承体系(Linux体系)贯穿计算机系统的网络通信架构图示: 二.实现并部署多线程并发Tcp服务器框架线程池模块序列化反序列化工具模块通信信道建立模块服务器主体模块任务回调模块(根据具体应用场景可重构)Tips:DebugC代码过程中遇到…...
Spring Boot 笔记 020 redis集成
1.1 安装redis Windows 下 Redis 安装与配置 教程_redis windows-CSDN博客 2.1 引入redis坐标 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-data-redis</artifactId></dependency> 2.2 配置…...
防火墙——计算机网络
前述基于密码的安全机制不能有效解决以下安全问题: 用户入侵: 利用系统漏洞进行未授权登录; 授权用户非法获取更高级别权限等。 软件入侵: 通过网络传播病毒、蠕虫和特洛伊木马。 拒绝服务攻击等。 解决方法: 防火墙&a…...
用html编写的招聘简历
用html编写的招聘简历 相关代码 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</tit…...
215数组中的第K个最大元素
215数组中的第K个最大元素 题目描述 给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。…...
【动态规划】【矩阵快速幂】LeetCode2851. 字符串转换
作者推荐 【深度优先搜索】【树】【有向图】【推荐】685. 冗余连接 II 涉及知识点 【矩阵快速幂】封装类及测试用例及样例 LeetCode 2851. 字符串转换 给你两个长度都为 n 的字符串 s 和 t 。你可以对字符串 s 执行以下操作: 将 s 长度为 l (0 <…...
【LeetCode每日一题】单调栈 402 移掉k位数字
402. 移掉 K 位数字 给你一个以字符串表示的非负整数 num 和一个整数 k ,移除这个数中的 k **位数字,使得剩下的数字最小。请你以字符串形式返回这个最小的数字。 示例 1 : 输入:num "1432219", k 3 输出ÿ…...
力扣 309. 买卖股票的最佳时机含冷冻期
题目来源:https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/ C题解:动态规划 状态1:表示持有股票。更新为之前持有股票(dp[i-1][0])或者不持有股票且不处于冷冻期后买入&…...
2024年刷题记录
马上要开始找实习了,又开始重启刷题计划了!加油冲冲冲!刷题的顺序follow代码随想录的60天刷题计划!感谢FuCosmo的总结!之前都是按照C的语法进行刷题的,这次也同样使用C。 Day 1 数组 这些题过年前都刷过了…...
【JGit 】简述及学习资料整理
JGit 介绍 [官网](JGit | The Eclipse Foundation): https://www.eclipse.org/jgit/ 用户指南 : https://github.com/eclipse-jgit/jgit/wiki/User-Guide JGit是一个用于Java编程语言的开源Git实现。它提供了一组Java库和API,使开发人员可以在他们的Java应用程序…...
python数据类型-集合set
1 集合(set)的定义 1.1 集合是一个无序且不重复元素的序列: 1)无序:存储顺序和添加的顺序不一定相同,不支持索引、切片 2)元素不重复:当添加重复元素时,集合会自动去重…...
excel如何指定求和
在Excel中,你可以使用函数来实现动态求和,使得当指定行的数值更新后,和也随之更新。具体来说,你可以使用SUM函数结合一些动态的引用方法。以下是一种实现方式: 假设你要对A列(从A1到A10,以示例…...
服务端实时推送技术之SSE(Server-Send Events)
文章目录 前言一、解决方案:1、传统实时处理方案:2、HTML5 标准引入的实时处理方案:3、第三方推送: 二、SSE1.引入库1、客户端: 2.服务端:三、业务实践:能否做到精准投递? 总结 前言…...
使用IntelliJ IDEA查看接口的全部实现方法
在大型Java项目中,经常会使用接口和抽象类进行代码设计。为了更好地了解代码结构和功能,我们需要快速查看一个接口的所有实现类。IntelliJ IDEA提供了一些方便的方法来实现这一目标。 1. 点击查看接口的实现子类 在IDEA中,你可以轻松地查看…...
阿里云幻兽帕鲁服务器操作系统类型怎么选择?
使用阿里云服务器搭建幻兽帕鲁操作系统类型选Windows还是Linux?如果对Linux熟悉就选择Linux,相对于windows,Linux更少占用系统资源;如果对Linux不熟悉,首选Windows。事实上,阿里云提供的幻兽帕鲁服务器通过…...
Codeforces Round 927 (Div. 3) LR-remainders的题解
原题描述: C.LR-remains 每次测试时限:2 秒 每次测试的内存限制:256 兆字节 输入:标准输入 输出:标准输出 样例1输入: 4 4 6 3 1 4 2 LRRL 5 1 1 1 1 1 1 LLLLL 6 8 1 2 3 4 5 6 RLLLRR 1 10000 1000…...
HarmonyOS—@Observed装饰器和@ObjectLink嵌套类对象属性变化
Observed装饰器和ObjectLink装饰器:嵌套类对象属性变化 概述 ObjectLink和Observed类装饰器用于在涉及嵌套对象或数组的场景中进行双向数据同步: 被Observed装饰的类,可以被观察到属性的变化;子组件中ObjectLink装饰器装饰的状…...
The method toList() is undefined for the type Stream
The method toList() is undefined for the type Stream (JDK16) default List<T> toList() { return (List<T>) Collections.unmodifiableList(new ArrayList<>(Arrays.asList(this.toArray()))); }...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试
作者:Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位:中南大学地球科学与信息物理学院论文标题:BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接:https://arxiv.…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
Android15默认授权浮窗权限
我们经常有那种需求,客户需要定制的apk集成在ROM中,并且默认授予其【显示在其他应用的上层】权限,也就是我们常说的浮窗权限,那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...
【论文阅读28】-CNN-BiLSTM-Attention-(2024)
本文把滑坡位移序列拆开、筛优质因子,再用 CNN-BiLSTM-Attention 来动态预测每个子序列,最后重构出总位移,预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵(S…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
