首页 > 试题广场 >

一个长度为100的循环链表，指针A和指针B都指向了链表中的同

[单选题]
一个长度为100的循环链表，指针A和指针B都指向了链表中的同一个节点，A以步长为1向前移动，B以步长为3向前移动，一共需要同时移动多少步A和B才能再次指向同一个节点____。 
  • 99
  • 100
  • 101
  • 49
  • 50
  • 51
添加回答
推荐
SunburstRun头像 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)
Miss_Wendy头像 Miss_Wendy
A B一快一慢，当二者差一圈时，刚好指向同一节点，3*x-1*x=100   x=50
发表于 2015-08-25 10:39:00 回复(6)
shellshell头像 shellshell
这个题从物理角度分析一下就好理解了。A向前移动1步，B向前移动3步。假设A，B都在起点，那么把A看做静止，B相对于A就是以2两步移动了。所以这个题可以这么说：在长度为100的循环链表中，A,B均在起点，A不移动，B每次移动2步，问啥时候能回到起点？
发表于 2016-03-22 08:55:39 回复(4)
牛牛12315头像 牛牛12315
跑圈100m   A速度1m/s B速度3m/s   B比A多跑一圈耗时100/（3-1）=50s
发表于 2015-09-06 10:39:58 回复(0)
牛客172864号头像 牛客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)
已注销头像 已注销
题目说的不好，那我相差两圈呢？答案B也对啊，也没说最少多少步
发表于 2016-03-04 19:25:34 回复(6)
小红辣椒头像 小红辣椒
大家都在讨论 B 选项 100 为什么不行

其实题目已经交待得很清楚了，是问什么时候“A和B才能再次指向同一个节点”

“再次” ！“再次” ！“再次” ！

很明显只能选 E，50
发表于 2022-05-07 08:39:17 回复(0)
testestest头像 testestest
(3x)%100=x%100,x=50.
发表于 2016-03-14 19:21:10 回复(1)
GayLeague头像 GayLeague
B比A快 2 步，要在此指向同一个节点必然套圈了，100/2=50，不必想的太复杂
发表于 2015-10-31 23:09:35 回复(1)
InGodWeTrust头像 InGodWeTrust
答案是E：

发表于 2017-02-25 20:46:54 回复(0)
染_头像 染_
长度100 ，A step = 1 ，B step = 3 ，假设AB同在起始点可知 x % 100 == （x * 3）% 100 为相遇，题中100和50都相符，考虑到再次相遇，选50最为妥当。
发表于 2022-06-18 10:41:20 回复(0)
孤单的跟鞋声和你的笑丶头像 孤单的跟鞋声和你的笑丶
设指针A移动的步数为 ( x )，指针B移动的步数也为 ( x )。 
对于指针A，每次移动步长为1，所以它移动 ( x ) 步后的位置为 ( x \mod 100 )。 
对于指针B，每次移动步长为3，所以它移动 ( x ) 步后的位置为 ( (3x) \mod 100 )。
我们需要找到最小的正整数 ( x )，使得： [ x \mod 100 = (3x) \mod 100 ]
发表于 2024-06-28 10:34:16 回复(0)
牛客726231979号头像 牛客726231979号
直接可以挑选较小的数值计算，分别乘以1和3后对100取余，相等且最小的那个即为正确答案。
发表于 2023-12-20 21:21:34 回复(0)
ZGG_cs头像 ZGG_cs
都没说是什么循环链表?? 双循环链表走第49步，不也可以吗？

发表于 2023-07-11 16:49:18 回复(0)
机会留着有准备的人头像 机会留着有准备的人
快慢指针
发表于 2023-05-10 15:29:09 回复(0)
有痕头像 有痕
让我看看有多少人选B
发表于 2023-04-27 22:09:10 回复(0)
安苒_头像 安苒_
这道题目，本质上是相遇追击问题，使用的快慢指针的技巧
发表于 2022-11-14 16:27:55 回复(0)
牛客623827772号头像 牛客623827772号
头结点也包括在链表长度里面吗？如果不包括不就整个链表101个结点了吗
发表于 2022-10-18 23:43:20 回复(0)
牛客801282807号头像 牛客801282807号
这个题目到底是移动多少次还是移动多少步
发表于 2022-08-15 10:03:26 回复(0)
内向且正义头像 内向且正义
设A步长为  sp1
B 为  sp2
移动次数为 n
表长 为 len
则由A B 移动关系和表长可得
sp1*n%len=sp2*n%len
发表于 2022-05-03 17:46:47 回复(0)
XInobukiki头像 XInobukiki
b呢
发表于 2022-03-31 18:32:05 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 链表 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 2021 数据库工程师 远景 测试开发工程师 大数据开发工程师 Java工程师
来自：阿里巴巴2016研发工...
难度：
61条回答 19470浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号