作者StubbornLin (Victor)
看板Programming
标题Re: [请益] linked list里如何找cycle?
时间Mon Jan 25 22:14:22 2010
※ 引述《pikahacker (喵)》之铭言：
: ※ [本文转录自 Prob_Solve 看板]
: 作者: pikahacker (喵) 看板: Prob_Solve
: 标题: [请益] linked list里如何找cycle?
: 时间: Mon Jan 25 13:06:55 2010
: 如果有人给你一个linked list
: 有办法在O(N)时间内,得知linked list中有没有cycle?
如果你只是要知道是否有cycle
用其它人的方法应该就可以
我自己是有想到一个方法
除了发现是否有cycle
还可以用来找到所有cycle
方法和想法很简单
就是本质上cycle的每个节点都有个特性
"都一定有别人指着它，而它也指着别人"
只要去掉不合这样条件的节点
重覆一直做，非cycle成员的的节点
起先会被除掉，这样一来让其它非cycle节点的成员
在接下来几轮中，只要他不是cycle成员
邻居又被去掉了，接着他们也会跟着不见
这样一直去除，最後剩下的就全都是cycle的节点
就可以从中一个一个把他们挑出来
--
Now.in 网路广播平台
http://now.in
哇咧咧 创意投票系统
http://walele.com
易记学 程式设计教学
http://ez2learn.com/
VICTOR's 个人Blog
http://blog.ez2learn.com/
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.252.70.149
1F：推 ddavid:除非这个linked list是双向的，否则你的做 114.42.111.126 01/25 22:26
2F：→ ddavid:法需要O(n^2)。 114.42.111.126 01/25 22:26
3F：→ ddavid:因为要知道一个node有没有被别人指，需要看 114.42.111.126 01/25 22:26
4F：→ ddavid:过所有其它的node。 114.42.111.126 01/25 22:27