首页
题库
面试
求职
学习
竞赛
More+
所有博客
搜索面经/职位/试题/公司
搜索
我要招人
去企业版
登录 / 注册
首页
>
试题广场
>
一个长度为100的循环链表,指针A和指针B都指向了链表中的同
[单选题]
一个长度为100的循环链表,指针A和指针B都指向了链表中的同一个节点,A以步长为1向前移动,B以步长为3向前移动,一共需要同时移动多少步A和B才能再次指向同一个节点____。
99
100
101
49
50
51
添加笔记
邀请回答
收藏(831)
分享
60个回答
添加回答
34
推荐
SunburstRun
答案是E,因为有100个节点,可以先假设先都在节点1,B经过33步刚刚到达节点100,而A在34,第34步B到达节点3,A在35,所以接下来是3+3n=35+n,所以n=16,所以总共=34+16=50
编辑于 2015-08-25 00:17:20
回复(6)
160
Miss_Wendy
A B一快一慢,当二者差一圈时,刚好指向同一节点,3*x-1*x=100 x=50
发表于 2015-08-25 10:39:00
回复(6)
52
shellshell
这个题从物理角度分析一下就好理解了。A向前移动1步,B向前移动3步。假设A,B都在起点,那么把A看做静止,B相对于A就是以2两步移动了。所以这个题可以这么说:在长度为100的循环链表中,A,B均在起点,A不移动,B每次移动2步,问啥时候能回到起点?
发表于 2016-03-22 08:55:39
回复(4)
46
牛牛12315
跑圈100m A速度1m/s B速度3m/s B比A多跑一圈耗时100/(3-1)=50s
发表于 2015-09-06 10:39:58
回复(0)
6
牛客172864号
假定经过n步A、B再次相遇。则A经过的结点为n,B经过的结点为3n;此刻B必然比A多经过了整数倍的链表长度(圈的长度),假定经过了i倍的链表长度,则有3n-n=100i,即2n=100i;满足该等式的最小整数位i=2,n=100。即A经过了100个结点,B经过了100个结点,二者再次相遇。
编辑于 2016-04-05 23:53:50
回复(0)
6
忆水寒
题目说的不好,那我相差两圈呢?答案B也对啊,也没说最少多少步
发表于 2016-03-04 19:25:34
回复(4)
4
小红辣椒
大家都在讨论 B 选项 100 为什么不行
其实题目已经交待得很清楚了,是问什么时候“A和B才能再次指向同一个节点”
“再次” !“再次” !“再次” !
很明显只能选 E,50
发表于 2022-05-07 08:39:17
回复(0)
4
testestest
(3x)%100=x%100,x=50.
发表于 2016-03-14 19:21:10
回复(1)
4
GayLeague
B比A快 2 步,要在此指向同一个节点必然套圈了,100/2=50,不必想的太复杂
发表于 2015-10-31 23:09:35
回复(1)
2
InGodWeTrust
答案是E:
发表于 2017-02-25 20:46:54
回复(0)
1
染_
长度100 ,A step = 1 ,B step = 3 ,假设AB同在起始点可知 x % 100 == (x * 3)% 100 为相遇,题中100和50都相符,考虑到再次相遇,选50最为妥当。
发表于 2022-06-18 10:41:20
回复(0)
0
牛客726231979号
直接可以挑选较小的数值计算,分别乘以1和3后对100取余,相等且最小的那个即为正确答案。
发表于 2023-12-20 21:21:34
回复(0)
0
ZGG_cs
都没说是什么循环链表?? 双循环链表走第49步,不也可以吗?
发表于 2023-07-11 16:49:18
回复(0)
0
机会留着有准备的人
快慢指针
发表于 2023-05-10 15:29:09
回复(0)
0
有痕
让我看看有多少人选B
发表于 2023-04-27 22:09:10
回复(0)
0
安苒_
这道题目,本质上是相遇追击问题,使用的快慢指针的技巧
发表于 2022-11-14 16:27:55
回复(0)
0
牛客623827772号
头结点也包括在链表长度里面吗?如果不包括不就整个链表101个结点了吗
发表于 2022-10-18 23:43:20
回复(0)
0
牛客801282807号
这个题目到底是移动多少次还是移动多少步
发表于 2022-08-15 10:03:26
回复(0)
0
内向且正义
设A步长为 sp1
B 为 sp2
移动次数为 n
表长 为 len
则由A B 移动关系和表长可得
sp1*n%len=sp2*n%len
发表于 2022-05-03 17:46:47
回复(0)
0
XInobukiki
b呢
发表于 2022-03-31 18:32:05
回复(0)
0
I虫
不是n%100==n*3%100吗
发表于 2021-04-07 19:59:30
回复(0)
这道题你会答吗?花几分钟告诉大家答案吧!
提交观点
问题信息
C++工程师
golang工程师
iOS工程师
安卓工程师
运维工程师
链表
前端工程师
算法工程师
测试工程师
PHP工程师
安全工程师
游戏研发工程师
2021
数据库工程师
远景
测试开发工程师
大数据开发工程师
Java工程师
来自:
阿里巴巴2016研发工...
难度:
60条回答
831收藏
19050浏览
热门推荐
相关试题
合并二叉树
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
测试工程师
安全工程师
c#工程师
数据库工程师
大数据开发工程师
瓜子二手车
2019
评论
(7)
下面算法的时间复杂度是 int f...
Java工程师
C++工程师
iOS工程师
安卓工程师
运维工程师
前端工程师
算法工程师
PHP工程师
测试工程师
安全工程师
数据库工程师
大数据开发工程师
远景
游戏研发工程师
golang工程师
测试开发工程师
2021
评论
(3)
在类的定义中可以有两个同名函数,这...
哔哩哔哩
游戏研发工程师
2020
评论
(0)
将1,2,3,......,99,...
数学运算
评论
(27)
来自
阿里巴巴2016研发工程...
A为整数数组, N为A的数组长度,...
数组
评论
(23)
来自
阿里巴巴2016研发工程...
扫描二维码,关注牛客网
意见反馈
下载牛客APP,随时随地刷题