【面试经典题】环形链表

在这里插入图片描述

个人主页:一代…
个人专栏:数据结构
在这里插入图片描述

在面试中我们经常会遇到有关链表的相关题目,面试官通常会对题目给出拓展

下面我就两个leetcode上的一个双指针的题目为例,并对其进行拓展

题目链接:环形链表

题目描述:在这里插入图片描述
示例:在这里插入图片描述

思路:运用快慢指针,快指针一次走两步,慢指针一次走一步,若链表带环,则快慢指针一定会在环中相遇,若不带环,则快指针就会走到末尾(NULL或最后一个节点)

代码示例:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode  ListNode;
bool hasCycle(struct ListNode *head) {ListNode* slow=head;ListNode* fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow)return true;}return false;
}

|

这里while循环中的fast&&fast->next不能调换顺序,因为当链表不带环,节点个数为偶数时,快指针会走到链表为空的位置,当fast->next在前,对空指针进行解引用,就会造成内存访问错误
(注:fast&&fast->next中如果前一个为假,那么整个表达式为假,就不会对下一个表达式进行计算)

拓展面试题目

在带环链表中,当slow每次走一步,fast每次走三步,那么slow会相遇吗?

slow每次走一步,fast每次走三步,那么当slow进环时,fast和slow相距的距离为N,那么没走一次,相距的距离就会减小2.
当链表长度为C时
在这里插入图片描述

于是就分为下面两种情况
在这里插入图片描述

总结:
1 当N为偶数时,slow和fast在第一轮就会相遇
2 当N为奇数时
C-1为偶数时就会在第二轮相遇
C-1为奇数时一定不会相遇(注:这种结论时错误的,这里下面会讲到)

为什么N是偶数,C时奇数这个条件一定不会成立呢?

假设:链表环之前长度为L,slow和fast相距的距离为N,slow进环时,fast已经在环中转了X圈
在这里插入图片描述
那么就会得出以下几个数学算式:
slow进环时,fast在环中转了X圈,于是fast走过的长度就为L+XC+C-N=L+(X+1)C-N
slow走过的长度为L
又因为fast走过的长度为slow走过的长度的三倍,所以3L=L+(X+1)C-N
得出2L=(X+1)C-N
2L一定为偶数,当C为偶数,N为奇数时,由算式可得偶数=偶数-奇数,这显然时不出立的,于是就可得出把上面结论中当N为奇数,C-1为奇数时一定不可以追上的结论推翻,于是可证明当在环形链表中fast走3步,slow走1步时,fast和slow一定可以相遇,永远追不上的条件不成立

结论:
1 当N为偶数时,slow和fast在第一轮就会相遇
2 当N为奇数时,C-1为偶数时第一轮追不上,在第二轮就可以追上

题目链接:环形链表II

题目描述:在这里插入图片描述
题目示例:在这里插入图片描述
代码示例:

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {ListNode *slow=head,*fast=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow)//相遇{ListNode *meet=slow;while(head!=meet)//相遇的节点即为入环的第一份节点{head=head->next;meet=meet->next;}return meet;}}return NULL;//无环
}

题目思路:定义一个快指针,一个慢指针,快指针一次走一步,慢指针一次走了两步,当两个指针相遇时节点为meet,在让头节点head从头开始走,一次走一步,meet从相遇的地点开始走,一次走一步,当两者相遇时即为入环的第一个节点

那么这是怎么得出来的呢?
在这里插入图片描述
其中E为环的入口点,M为快慢指针的相遇点,L为环之前的链表的长度
由于从slow进环时在到与fast相遇,fast一定不会运动一个环的长度就可以追上slow
假设在slow到环入口时,fast已经转了N圈,环的长度为R
slow运动的距离为L+X
fast运动的距离为L+XR+X
L+NR+X=2L+2X
L=NR-X=R(N-1)+(R-X) (N=1,2,3,4…)

于是meet从相遇点开始走,head从头节点开始走,head走的长度为L,L=R(N-1)+(R-X) (N=1,2,3,4…),当head到入口E时,meet运动了R-X加上转了(N-1)圈的长度,则两者一定会相遇。

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

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

相关文章

Java抽象类:为何它是你代码架构的基石?

目录 1、抽象类的概念 2、抽象类语法 3、抽象类特性 4、抽象类的作用 5、 完结散花 个人主页:秋风起,再归来~ 文章专栏:javaSE的修炼之路 个人格言:悟已往之不谏,知来者犹可追 克…

人脸消费给传统食堂带来的变化

消费的技术基础是脸部识别,脸部识别是基于人的容貌特征信息进行认证的生物特征识别技术,其突出的特征是以非接触方式进行识别,避免个人信息的泄露。 面部识别和指纹识别、掌纹识别、视网膜识别、骨骼识别、心率识别等都是人体生物特征识别技术…

【C语言/数据结构】栈:从概念到两种存储结构的实现

目录 一、栈的概念 二、栈的两种实现方式 1.顺序表实现栈 2.链表实现栈 三、栈的顺序存储结构及其实现 1.栈的声明 2.栈的初始化 3.栈的销毁 4.栈的压栈 5.栈的弹栈 6.栈的判空 7.返回栈顶元素 8.返回栈的长度 四、栈的链式存储结构及其实现 1.栈的声明 2.栈的…

【SRC实战】前端脱敏信息泄露

挖个洞先 https://mp.weixin.qq.com/s/xnCQQCAneT21vYH8Q3OCpw “ 以下漏洞均为实验靶场,如有雷同,纯属巧合 ” 01 — 漏洞证明 一、前端脱敏,请求包泄露明文 “ 前端脱敏处理,请求包是否存在泄露? ” 1、获取验…

3.整数运算

系列文章目录 信息的表示和处理 : Information Storage(信息存储)Integer Representation(整数表示)Integer Arithmetic(整数运算)Floating Point(浮点数) 文章目录 系列文章目录前…

钟表——蓝桥杯十三届2022国赛大学B组真题

问题分析 这个问题的关键有两点:1.怎么计算时针,分针,秒针之间的夹角,2.时针,分针,秒针都是匀速运动的,并非跳跃性的。问题1很好解决看下面的代码就能明白,我们先考虑问题2&#xf…

Springboot+Vue项目-基于Java+MySQL的车辆管理系统(附源码+演示视频+LW)

大家好!我是程序猿老A,感谢您阅读本文,欢迎一键三连哦。 💞当前专栏:Java毕业设计 精彩专栏推荐👇🏻👇🏻👇🏻 🎀 Python毕业设计 &…

Rx(Reactive Extensions)的由来

既然我们已经介绍了响应式编程,现在是时候了解我们的明星了:响应式扩展,通常简称为Rx。微软开发了Reactive扩展库,使其易于处理事件流和数据流。在某种程度上,时变值本身就是一个事件流;每个值更改都是一种类型的事件它会更新依赖…

Vue中使用$t(‘xxx‘)实现中英文切换;

(原文链接) 介绍 {{$t(key)}} :是VueI18n插件提供的函数,主要用于根据当前语言环境返回对应的翻译文本,以便在页面上显示多语言内容。 key:作为参数传递给函数$t()的字符串,用于指定需要翻译的…

【C++要哮着学】初识C++,什么是C++?什么是命名空间?什么又是缺省函数?

文章目录 前言1、C简介1.1、什么是C1.2、C起源1.3、C发展 2、C关键字(C98)3、命名空间3.1、命名空间的定义及使用3.2、命名空间的嵌套3.3、命名空间的三种使用方式3.3.1、加命名空间名称及作用域限定符3.3.2、使用using将命名空间中某个成员引入3.3.3、使…

MySQL 通过 systemd 启动时 hang 住了……

mysqld:哥,我起不来了…… 作者:贲绍华,爱可生研发中心工程师,负责项目的需求与维护工作。其他身份:柯基铲屎官。 爱可生开源社区出品,原创内容未经授权不得随意使用,转载请联系小编…

【Docker学习】重启容器的docker restart

命令: docker container restart 描述: 重启一个或多个容器 用法: docker container restart [OPTIONS] CONTAINER [CONTAINER...] 别名: docker restart(docker的一些命令可以简写,docker restart就等同于docker cont…

SQLZOO:The JOIN operation

数据表:game-gaol-eteam game idmdatestadiumteam1team210018 June 2012National Stadium, WarsawPOLGRE10028 June 2012Stadion Miejski (Wroclaw)RUSCZE100312 June 2012Stadion Miejski (Wroclaw)GRECZE100412 June 2012National Stadium, WarsawPOLRUS... goal …

UE4_照亮环境_不同雾效的动态切换

一、问题及思路: 我们在一个地图上,经常切换不同的区域,不同的区域可能需要不同的色调,例如暖色调的野外或者幽暗的山洞,这两种环境上,雾效的选用肯定不一样,夕阳西下的户外用的就是偏暖的色调&…

【小白的大模型之路】基础篇:Transformer细节

基础篇:Transformer 引言模型基础架构原论文架构图EmbeddingPostional EncodingMulti-Head AttentionLayerNormEncoderDecoder其他 引言 此文作者本身对transformer有一些基础的了解,此处主要用于记录一些关于transformer模型的细节部分用于进一步理解其具体的实现机…

LeetCode_栈和队列相关OJ题目

✨✨所属专栏:LeetCode刷题专栏✨✨ ✨✨作者主页:嶔某✨✨ 上一篇:数据结构_栈和队列(Stack & Queue)-CSDN博客 有效的括号 解析: 这里我们用数组实现的栈来解决这个问题,在有了栈的几个基础接口之后,我们运用这…

【Chrome实用命令笔记】

文章目录 Chrome实用命令笔记1、chrome基本介绍2. 打开开发者工具(DevTools)方法一:快捷键方法二:右键菜单方法三:浏览器设置 2. 开发者工具面板Elements面板Console面板Sources面板Network面板Performance面板Memory面…

(done) Beam search

参考视频1:https://www.bilibili.com/video/BV1Gs421N7S1/?spm_id_from333.337.search-card.all.click&vd_source7a1a0bc74158c6993c7355c5490fc600 (beam search 视频) 参考博客1:https://jasonhhao.github.io/2020/06/19/…

Springboot项目如何创建单元测试

文章目录 目录 文章目录 前言 一、SpringBoot单元测试的使用 1.1 引入依赖 1.2 创建单元测试类 二、Spring Boot使用Mockito进行单元测试 2.1 Mockito中经常使用的注解以及注解的作用 2.2 使用Mockito测试类中的方法 2.3 使用Mockito测试Controller层的方法 2.4 mock…

通过 Java 操作 redis -- list 列表基本命令

目录 使用命令 lpush,lrange,rpush 使用命令 lpop 和 rpop 使用命令 blpop,brpop 使用命令 llen 关于 redis list 列表类型的相关命令推荐看Redis - list 列表 要想通过 Java 操作 redis,首先要连接上 redis 服务器&#xff…