环形链表2--绝妙的运算

一、要求

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

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

不允许修改 链表。

二、思路

基本思路和上一个环形链表(如果有疑问可以移步上一篇博客查看)大部相同,但存在一个关键问题上的不同点。

使用快慢指针的方式来解决环形链表问题。

首先定义两个指向head的struct ListNode*类型的指针变量用来记录开始位置;

接下来判断链表是否为空链表以及链表的首项指向的地址是否为空;

确保上述条件后开始让phead1和phead2分别向前走一步和两步;

再他们向后走的过程中一旦遇到指向NULL的问题说明该链表不是环形链表;

不为NULL就继续向后走;

此时按照上述判断已经确定该链表为环形链表;

对链表的地址进行判断,当两链表指向的地址相同时说明该链表为环形链表。

关键结论:

使phead2和head同时向后一步一步的走,最终他们会在环形链表的入口处相遇!

我们在知道了这个结论以后开始对这个结论进行论证;

//        //             我们假设环状链表环的起点到头部的距离为L 
//        //             环的长度为C
//        //             phead1和phead2相交的位置到环状链表环的起点的位置为X
//        //             此时可以得到L = N*C-X(N为phead2多走的圈数)
//        //             L = (N-1) * C + C - X
//        //             也就是说phead2是从x开始走的,他们两个走的距离刚好越过了X即L = N * C                                   两者的相遇点就是环形链表的起点

三、画图理解 

ps:环形链表的论证已经在上一篇博客中详细解释,在这里不再进行过多赘述,谢谢理解。

四、代码实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * phead1 = head;
    struct ListNode * phead2 = head;
    while(phead2&&phead2->next)
    {
        phead1 = phead1->next;
        phead2 = phead2->next->next;
        if(phead1 == phead2)
        {
            while(head!=phead2)
            {
                head= head->next;
                phead2=phead2->next;
            }
            return head;
        }
    }
    return NULL;
}

五、小思考

如果走的距离不是1和2,他们是否还能相遇?

后面为什么直接使用head而不是创建一个临时指针用于替代它呢?

请将答案放在评论区吧!

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

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

相关文章

静态路由协议实验综合实验

需求: 1、除R5的换回地址已固定外,整个其他所有的网段基于192.168.1.0/24进行合理的IP地址划分。 2、R1-R4每台路由器存在两个环回接口,用于模拟连接PC的网段;地址也在192.168.1.0/24这个网络范围内。 3、R1-R4上不能直接编写到…

机器学习KNN最邻近分类算法

文章目录 1、KNN算法简介2、KNN算法实现2.1、调用scikit-learn库中KNN算法 3、使用scikit-learn库生成数据集3.1、自定义函数划分数据集3.2、使用scikit-learn库划分数据集 4、使用scikit-learn库对鸢尾花数据集进行分类5、什么是超参数5.1、实现寻找超参数5.2、使用scikit-lea…

【vite】

目录 vite介绍vite的基础应用vite创建项目vite创建vue3项目vite创建vue2项目vite创建react项目 vite中使用css的各种功能vite中使用ts vite介绍 一、特点: 开发时效率极高开箱即用,功能完备摄取丰富,兼容rollup超高速热重载预设应用和类库打…

vulhub中 Struts2-015 远程代码执行漏洞复现

影响版本: 2.0.0 - 2.3.14.2 ## 原理与测试 漏洞产生于配置了 Action 通配符 *&#xff0c;并将其作为动态值时&#xff0c;解析时会将其内容执行 OGNL 表达式&#xff0c;例如&#xff1a; xml <package name"S2-015" extends"struts-default"> …

上位机图像处理和嵌入式模块部署(qmacvisual之n点标定)

【 声明&#xff1a;版权所有&#xff0c;欢迎转载&#xff0c;请勿用于商业用途。 联系信箱&#xff1a;feixiaoxing 163.com】 工业场景中&#xff0c;很多时候图像是用来做测量的。虽然我们很希望载台是平的&#xff0c;摄像头是正对着拍摄物体的&#xff0c;但是运行时间长…

可视化图表:象形柱图,比柱图漂亮、有趣100倍。

一、什么是象形柱图 象形柱图&#xff08;Pictorial Bar Chart&#xff09;是一种可视化图表&#xff0c;它使用图形或图片代替传统的矩形柱子来表示数据。每个图形或图片的大小和形状都与对应的数据值相关联&#xff0c;从而形成一种视觉上的象征性表示。 象形柱图通常用于展…

【每日刷题】Day3

【每日刷题】Day3 &#x1f955;个人主页&#xff1a;开敲&#x1f349; &#x1f525;所属专栏&#xff1a;每日刷题&#x1f34d; 目录 1. 69. x 的平方根 - 力扣&#xff08;LeetCode&#xff09; 2. 70. 爬楼梯 - 力扣&#xff08;LeetCode&#xff09; 3. 118. 杨辉三…

STL容器(3)

1,stack容器 1.1 基本概念 概念&#xff1a;stack是一种先进后出的数据结构&#xff0c;它只有一个出口 因此&#xff1a; 栈中只有顶端的元素才可以被使用&#xff0c;因此占不允许有遍历行为 栈中进入数据称为--入栈&#xff08;push) 栈中弹出数据称为--出栈&#xff08…

【Linux】虚拟机连不上外网 (1),2024百度网络安全岗面试真题收录解析

vi /etc/sysconfig/network-scripts/ifcfg-ens33 BOOTPROTOstatic ONBOOTyes IPADDR? NETMASK? GATEWAY? dns18.8.8.8 dns1144.144.144.144 这两个必填 自我介绍一下&#xff0c;小编13年上海交大毕业&#xff0c;曾经在小公司待过&#xff0c;也去过华为、OPPO等大厂…

深入理解Armv9 DSU-110中的L3 cache

快速链接: 【精选】ARMv8/ARMv9架构入门到精通-[目录] &#x1f448;&#x1f448;&#x1f448; 关键词&#xff1a; DynamIQ cluster、DSU-110、DSU-120、DSU、cache、mmu、缓存、高速缓存、内存管理、MPAM 思考&#xff1a; 1、L1、L2、L3 cache的替换策略是怎样的&#xff…

Android中的aidl接口及案例说明

目录 一、什么是AIDL 二、AIDL语法规格 三、AIDL实例 客户端: 服务端: 一、什么是AIDL AIDL,即 Android Interface Definition Language,用于android不同进程间通信接口。同一个应用里面还是建议用正常接口实现功能即可。 官方说明:Android 接口定义语言 (AIDL) | …

如何使用屏幕变式控制SAP系统操作界面字段的必输、显示或隐藏

在SAP/ERP项目实施中经常会遇到要求把SAP系统操作的界面中某些字段设置为必输&#xff0c;显示或隐藏&#xff0c;遇到这种需求时&#xff0c;有些业务操作界面可以通过后台进行屏幕的字段状态设置解决&#xff0c;而有些业务的操作界面是没有屏幕字段的后台设置的&#xff0c;…

DSP实时计算平台设计方案:912-基于6U CPCIe的双路光纤图像DSP实时计算平台

基于6U CPCIe的双路光纤图像DSP实时计算平台 一、设备概述 设备基于6U CPCIe架构&#xff0c;通过背板交换实现4片信号处理板卡的互联传输&#xff0c;每个信号处理板卡支持双TMS320C6678&#xff0c;支持2路光纤的图像处理&#xff0c;实现FPGA的预处理和备份工…

机器学习中的GBDT模型及其优缺点(包含Python代码样例)

目录 一、简介 二、优缺点介绍 三、Python代码示例 四、总结 一、简介 GBDT&#xff08;Gradient Boosting Decision Tree&#xff09;是一种集成学习算法&#xff0c;被广泛应用于机器学习中的回归和分类问题。它由多个决策树组成&#xff0c;每个决策树都通过迭代逐渐提升…

之前翻硬币问题胡思乱想的完善

题目背景 小明正在玩一个“翻硬币”的游戏。 题目描述 桌上放着排成一排的若干硬币。我们用 * 表示正面&#xff0c;用 o 表示反面&#xff08;是小写字母&#xff0c;不是零&#xff09;&#xff0c;比如可能情形是 **oo***oooo&#xff0c;如果同时翻转左边的两个硬币&#x…

Transformer位置编码详解

在处理自然语言时候&#xff0c;因Transformer是基于注意力机制&#xff0c;不像RNN有词位置顺序信息&#xff0c;故需要加入词的位置信息来显示的表明词的上下文关系。具体是将词经过位置编码(positional encoding)&#xff0c;然后与emb词向量求和&#xff0c;作为编码块(Enc…

9(10)-1(2)-CSS 布局模型+CSS 浮动

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 一、CSS 布局模型1 流动模型&#xff08;标准流&#xff09; 二、CSS 浮动1 浮…

今日早报 每日精选15条新闻简报 每天一分钟 知晓天下事 4月6日,星期六

每天一分钟&#xff0c;知晓天下事&#xff01; 2024年4月6日 星期六 农历二月廿八 1、 水利部&#xff1a;启动洪水防御Ⅳ级应急响应&#xff0c;全力应对闽赣粤桂暴雨洪水。 2、 两部门&#xff1a;中小学校、幼儿园应定期开展教职工、安保人员消防安全培训。 &#xfeff; &…

文献学习-28-Endora: 用于内镜仿真的视频生成模型

Endora : Video Generation Models as Endoscopy Simulators Authors: Chenxin Li, Hengyu Liu, Yifan Liu, Brandon Y. Feng, Wuyang Li, Xinyu Liu, Zhen Chen, Jing Shao, Yixuan Yuan Keywords: Medical Generative AI Video Generation Endoscopy Abstract 生成模型有…

11 - 三八译码器和存储器组织

---- 整理自B站UP主 踌躇月光 的视频 1. 38译码器 1.1 真值表 A2A1A0O7O6O5O4O3O2O1O00000000000100100000010010000001000110000100010000010000101001000001100100000011110000000 O 0 A 2 ‾ A 1 ‾ A 0 ‾ O 1 A 2 ‾ A 1 ‾ A 0 O 2 A 2 ‾ A 1 A 0 ‾ O 3 A 2 ‾ A…