作者adrianshum (Alien)
看板Programming
标题Re: [请益] linked list里如何找cycle?
时间Mon Jan 25 14:44:45 2010
※ 引述《pikahacker (喵)》之铭言：
: ※ [本文转录自 Prob_Solve 看板]
: 作者: pikahacker (喵) 看板: Prob_Solve
: 标题: [请益] linked list里如何找cycle?
: 时间: Mon Jan 25 13:06:55 2010
: 如果有人给你一个linked list
: 有办法在O(N)时间内,得知linked list中有没有cycle?
初出来工作的时候, 有些老大出了这问题
当初没有说用O(N) 的, 我想了一个麻烦的方法.
後来他说其实有一个 O(N) 的方法, 我再想一想
就想到了
其实比较像智力问题. 想自己想的话先不要往下看
防雷
两支 ptr 指着 head, ptr A 每次往前移2格, ptr B 每次
移1格.
要是 ptr A reach 到 null 即是 non-cyclic
要是有一刻 ptr B 等如 A, 就是 cyclic
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 202.155.236.82
1F：推 yauhh:水 61.231.66.54 01/25 19:27
2F：推 yoco315:跟 rho method factorization 一样耶 O_O118.160.115.155 01/25 20:20
3F：推 pikahacker:好美的解法 76.24.28.22 01/25 22:21
4F：推 akasan:还是这个解法最优美118.168.186.244 01/25 23:57
5F：推 bobju:要证明是O(n)得用到数论. 58.115.151.184 01/26 14:58
6F：推 cutecpu:推！ 60.248.4.114 01/26 16:53
7F：→ MOONRAKER:赞 59.120.168.228 01/27 21:59
8F：推 lflin:如果 cycle number 是个质数...203.160.254.105 02/04 04:58
9F：→ lflin: 喔 没事 :p203.160.254.105 02/04 05:24
10F：推 DBoyX:好像赛车... 122.121.20.45 03/04 15:52