环形链表II

给定一个链表的头节点  head ,返回链表开始入环的第一个节点。 如果链表无环,则返回 null

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

不允许修改 链表。

提示:

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

 代码:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode LN;
struct ListNode *detectCycle(struct ListNode *head) {
    LN* fast,*slow;
    fast=slow=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            LN* meet=slow;
            while(head!=meet)
            {
                head=head->next;
                meet=meet->next;
              
            }
            return meet;
        }
    }
    return NULL;
}

结论:fast和slow的相遇点和head节点同时出发相遇的节点就是入口点

ps:入口点就是它的下一个节点指向了前面的节点导致链表成为环形链表

证明:

但是上述证明还是不够严谨 

如上图如果链表很长且环很短那么就显示的很奇怪但上面的证明不是完全错的,

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

gma 2 用户文档(pdf版)更新计划

随着 gma 2 整体构建完成&#xff0c;下一步继续针对库内所有功能完成一个用户指南&#xff08;非网站&#xff09;。相较于上次更新用户文档pdf版&#xff0c;已经过去了大半年。当然&#xff0c;PDF 版比网站上内容更丰富&#xff0c;也更新&#xff08;文档基于 gma 2.0.9a2…

李沐37_微调——自学笔记

标注数据集很贵 网络架构 1.一般神经网络分为两块&#xff0c;一是特征抽取原始像素变成容易线性分割的特征&#xff0c;二是线性分类器来做分类 微调 1.原数据集不能直接使用&#xff0c;因为标号发生改变&#xff0c;通过微调可以仍然对我数据集做特征提取 2.pre-train源…

【保姆级】2024年OnlyFans订阅指南

OnlyFans是一个独特的社交媒体平台&#xff0c;它为创作者和粉丝提供了一个互动交流的空间。通过这个平台&#xff0c;创作者可以分享他们的独家内容&#xff0c;而粉丝则可以通过订阅来支持和享受这些内容。如果你对OnlyFans感兴趣&#xff0c;并希望成为其中的一员&#xff0…

LeetCode 113—— 路径总和 II

阅读目录 1. 题目2. 解题思路3. 代码实现 1. 题目 2. 解题思路 看到树的问题一般我们先考虑一下是否能用递归来做。 假设 root 节点的值为 value&#xff0c;如果根节点的左子树有一个路径总和等于 targetSum - value&#xff0c;那么只需要将根节点的值插入到这个路径列表中…

hbase-2.2.7分布式搭建

一、下载上传解压 1.在官网或者云镜像网站下载jar包 华为云镜像站&#xff1a;Index of apache-local/hbase/2.2.7 2.上传到linux并解压 tar -zxvf hbase-2.2.7-bin.tar.gz -C /usr/locol/soft 二、配置环境变量 1. vim /etc/profile export HBASE_HOME/usr/local/soft/h…

快速探索随机树-RRT

文章目录 简介原理算法运动规划的变体和改进简介 快速探索随机树(RRT)是一种算法,旨在通过随机构建空间填充树来有效搜索非凸高维空间。该树是从搜索空间随机抽取的样本中逐步构建的,并且本质上偏向于向问题的大型未搜索区域生长。RRT 由 Steven M. LaValle 和 James J. K…

Unity 扩展自定义编辑器窗口

在Assets文件夹路径下任意位置创建Editor文件夹&#xff0c;将扩展编辑器的代码放在Editor文件夹下 生成编辑器窗口 代码中首先引用命名空间 using UnityEditor; 然后将创建的类继承自EditorWindow public class MenuEditor : EditorWindow 然后通过扩展编辑器菜单功能调用…

Jackson 2.x 系列【24】Spring Web 集成之 Jackson2ObjectMapperBuilder

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 本系列Jackson 版本 2.17.0 源码地址&#xff1a;https://gitee.com/pearl-organization/study-jaskson-demo 文章目录 1. 前言2. Spring Web3. Jackson2ObjectMapperBuilder3.1 成员属性3.2 静态方法3…

FMEA分析

目录 1、FMEA的核心目的 2、FMEA的种类 3、FMEA的实施步骤 4、FMEA的SOD等级 5、FMEA的例子 FMEA&#xff08;Failure Modes and Effects Analysis&#xff0c;失效模式与影响分析&#xff09;是一种预防性的可靠性设计分析&#xff0c;用来确定潜在失效模式及其原因。它主…

IDEA使用SCALA

一、在IDEA中下载插件 在设置->插件中找到scala&#xff0c;并下载。 下载完成后重启idea 二、在idea中创建spark的RDD操作项目 新建项目选中Scala。 创建完成后为项目添加java包&#xff0c;这个添加的是spark安装包中jars目录下的所有jar包 然后编写RDD操作 import or…

安全中级-初开始

一、网络基础 重要点&#xff1a;TTL值&#xff08;防环&#xff0c;linux64.Windows128 &#xff09;&#xff0c;IP数据包包头格式字节&#xff08;20&#xff09; 标识标志偏移量起到什么作用&#xff08;数据超过1500会分片&#xff09; wireshack抓包会有一个MSS&#x…

铭飞 MCMS 存在SQL注入漏洞

声明&#xff1a; 本文仅用于技术交流&#xff0c;请勿用于非法用途 由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失&#xff0c;均由使用者本人负责&#xff0c;文章作者不为此承担任何责任。 简介 铭飞&#xff08;MCMS&#xff09;是一种计算机管理…

Opencv3.4+FFMpeg3.4+pkg-config交叉编译arm开发板

Ubuntu16.04 64位 FFmpeg3.4 OpenCv3.4 一、下载FFmpeg https://github.com/FFmpeg/FFmpeg 1.配置 ./configure --prefix/home/zeng/ffmpeg_install --enable-cross-compile --cross-prefixarm-linux-gnueabihf- --ccarm-linux-gnueabihf-gcc --target-oslinux --cpuco…

算法课程笔记——排序

Bool返回真假 为何用const不用define 1.保护被修饰的东西 2.通常不分配存储空间&#xff0c; 效率高 匿名函数只在一处用&#xff0c;其他处用不到 不写&就是拷贝 u相等就u&#xff0c;不等就v 一个字符是空格一个是换行&#xff0c;后面是取下标i那就是1&#xff08;true&…

图解数学:拉格朗日松弛方法的直观理解

昨晚写了拉格朗日松弛方法的原理分析&#xff0c;今天意犹未尽&#xff0c;图解一下&#xff0c;从直观上进一步理解这种方法。 一、一个简单例子 我们先来看一个简单的例子&#xff0c;下面数学规划问题没有约束条件&#xff1a; min ⁡ f ( x ) − x 2 8 x − 10 \begin…

全排列问题

日升时奋斗&#xff0c;日落时自省 目录 1、全排列 2、全排列II 3、子集 4、组合 1、全排列 首先要了解全排列是怎么样的 例如:数组[1,2,3]的全排列&#xff08;全排列就是不同顺序排列方式&#xff09; 例子所有的排列方式如&#xff1a;[1,2,3],[1,3,2],[2,1,3],[2,3…

Leetcode876_链表的中间结点

1.leetcode原题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 2.题目描述 给你单链表的头结点 head &#xff0c;请你找出并返回链表的中间结点。 如果有两个中间结点&#xff0c;则返回第二个中间结点。 示例 1&#xff1a; 输入&#xff1a;head [1,2,3,4,5…

PTA 编程题(C语言)-- 判断素数

题目标题&#xff1a; 判断素数 题目作者 陈越 浙江大学 本题的目标很简单&#xff0c;就是判断一个给定的正整数是否素数。 输入格式&#xff1a; 输入在第一行给出一个正整数N&#xff08;≤ 10&#xff09;&#xff0c;随后N行&#xff0c;每行给出一个小于…

康耐视visionpro-CoglntersectLineLineTool操作说明工具详细说明

◆CogIntersectLineLineTool功能说明&#xff1a; 创建两条线的交点 备注&#xff1a;在“Geometry-Intersection”选项中的所有工具都是创建两个图形的交点工具&#xff0c;其中包括圆与圆的交点、线与圆的交点、线与线的交点、线与圆的交点等&#xff0c;工具使用的方法相似。…

C++ - set 和 map详解

目录 0. 引言 1. 关联式容器 2. 键值对 3. 树形结构 4. set 4.1 set 的定义 4.2 set 的构造 4.3 set 的常用函数 4.4 set 的特点 5. multiset 5.1 multiset 插入冗余数据 5.2 multiset - count 的使用 6. map 6.1 map 的定义 6.2 map 的构造 6.3 map的常…