一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 608|回复: 1
收起左侧

[Leetcode] Linked List Cycle II 的清晰易理解的思路 希望是正确的 欢迎大家指正

[复制链接] |试试Instant~ |关注本帖
zzhgetfuture 发表于 2016-4-29 02:44:40 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
这里假设 cycle入口前长度为m cycle一整圈长度为n  fast与slow 在距离cycle入口 x长度的位置相遇 此时:
slow的路程:m + x
fast的路程:2m + 2x
两者距离cycle入口的距离分别为 x, 2x + m - n.假设fast多走一圈(此处假设n > m, 若n<m, 可以给n加一个系数k,k代表fast多走的圈数)此处考虑最简单的情况便于分析。
x ?= 2x +m - n --> n ?= x + m
x = n - m结论成立 此点和初始起点距离cycle入口皆为 m 距离 此时把fast放回起点 速度降为一, slow继续 , 下次相遇时的位置即为cycle入口节点位置.
staycrazy 发表于 2016-4-29 07:07:25 | 显示全部楼层
建议你读一下quora上的这个答案:
https://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work/answer/Albert-Chen-31

这是我见过的最直观的解释。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-10 04:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表