作者ddavid (谎言接线生)
看板Programming
标题Re: [请益] linked list里如何找cycle?
时间Mon Jan 25 22:36:18 2010
※ 引述《adrianshum (Alien)》之铭言：
: ※ 引述《pikahacker (喵)》之铭言：
: : 作者: 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
话说，这个linked list是哪种linked list？
如果是单向、每个node只能指向一个其它node的话......
......，那只要扫过一次所有node看看有没有node指向null就好了，没有就是有
cycle，因为此种linked list要是有回圈就一定是最後一个点指回了前面某个点XD。
不会是分支造成的，因为没法指向第二个点XD。时间上是O(N)，而且不需要额外的两
个ptr，只需要一个bool flag XD
当然这只判定了有没有，并没找出那一圈是啥。不过内文写「得知linked list
中有没有cycle」，那麽这样就可以了。
--
「你会死。」不由分说，他被狠狠骂了一顿。
午休时，我拉着他到安静的地方。「你怎麽对着人这样说话呢？」
「他本来就会死，难道他不会死？」他抱怨。
－－预言师
--
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 编辑: ddavid 来自: 114.42.111.126 (01/25 22:41)
※ 编辑: ddavid 来自: 114.42.111.126 (01/25 22:43)
1F：→ yauhh:这也不对,所谓linked list就是应该有尾端 61.231.66.54 01/26 00:47
2F：→ yauhh:此外,也有有尾端并且中间夹带圈圈的例子 61.231.66.54 01/26 00:48
3F：→ yauhh:至於尾端,有或没有都有可能. 61.231.66.54 01/26 00:49
4F：→ xam:中间夹带圈圈, 那就有节点犯规多指一个了 114.32.92.137 01/26 03:18
5F：推 nedbob:有cycle的linked list 你在扫的时候就会遇 140.135.11.175 01/26 04:43
6F：→ nedbob:到无穷回圈 怎麽都停止不下来 140.135.11.175 01/26 04:43
7F：推 wupojung:如果next node有两个 应该就变成graph 吧 140.128.86.18 01/26 10:34
8F：→ wupojung:linked list应该是 只有单向 双向 Loop 140.128.86.18 01/26 10:35
9F：→ wupojung:当然loop 可以指回中间 就会变成2in 1out 140.128.86.18 01/26 10:35
10F：→ wupojung:当然发生在单向的时候...多个output 应该 140.128.86.18 01/26 10:36
11F：→ wupojung:不行..因为实作之前就要订 struct了 140.128.86.18 01/26 10:37
12F：→ wupojung:如果无法预估ouput有几个那 list 作不出 140.128.86.18 01/26 10:37
13F：→ wupojung:应该要写成graph = =(or tree) 140.128.86.18 01/26 10:38
14F：→ adrianshum:原 po 你写一个程式试一试就知道问题出 202.155.236.82 01/26 11:25
15F：→ adrianshum:在哪里了. linked list 的 traverse 只 202.155.236.82 01/26 11:25
16F：→ adrianshum:能经由一个 node 的 next 到达另一个 202.155.236.82 01/26 11:26
17F：→ adrianshum:你一直 traverse, circular 的 linked 202.155.236.82 01/26 11:26
18F：→ adrianshum:list 会让你一直都找到 next, 你要怎麽 202.155.236.82 01/26 11:26
19F：→ adrianshum:知道那是一直绕圈圈没有null, 而不是还 202.155.236.82 01/26 11:27
20F：→ adrianshum:没有到 null? 202.155.236.82 01/26 11:27
21F：推 AstralBrain:to楼上: 所以问题出在原po说的linked 220.133.186.66 01/26 12:02
22F：→ AstralBrain:list到底是指什麽东西 220.133.186.66 01/26 12:02
23F：→ AstralBrain:如果只是一般的有向图 拿到所有vertex 220.133.186.66 01/26 12:02
24F：→ AstralBrain:是很合理的.. 220.133.186.66 01/26 12:02
25F：推 yauhh:喔,我了解了,我误解本文的意思,的确检查null 61.231.66.54 01/26 12:17
26F：→ yauhh:即可.不过一般所说"检查所有node"是用走访的 61.231.66.54 01/26 12:18
27F：→ yauhh:所以有adrianshum提的办法.但如果是一般阵列 61.231.66.54 01/26 12:18
28F：→ yauhh:式的链接串列,做回路检查就很快了. 61.231.66.54 01/26 12:19
29F：→ ddavid:隔一天来看就爆出一堆推文XD 114.42.108.102 01/26 12:52
30F：→ ddavid:总之我只是要说特定情况下有个特殊解，不过 114.42.108.102 01/26 12:53
31F：→ ddavid:没有讲清楚是在拿到所有node（或知道个数） 114.42.108.102 01/26 12:53
32F：→ ddavid:的条件是我疏忽了XD 114.42.108.102 01/26 12:54