作者tiwei (∫期望dt=ivy + C)
站内Programming
标题Re: [请益] linked list里如何找cycle?
时间Tue Jan 26 12:39:11 2010
※ 引述《ddavid (谎言接线生)》之铭言：
: ※ 引述《adrianshum (Alien)》之铭言：
: : 初出来工作的时候, 有些老大出了这问题
: : 当初没有说用O(N) 的, 我想了一个麻烦的方法.
: : 後来他说其实有一个 O(N) 的方法, 我再想一想
: : 就想到了
: : 其实比较像智力问题. 想自己想的话先不要往下看
: : 防雷
: : 两支 ptr 指着 head, ptr A 每次往前移2格, ptr B 每次
: : 移1格.
这题是interview无敌常见题阿
印象中连Programming Interview Exposed这本书里也有提到
Alien用的这个应该是标准解法
如果你google一下就会发现大家都用这个方法
: : 要是 ptr A reach 到 null 即是 non-cyclic
: : 要是有一刻 ptr B 等如 A, 就是 cyclic
: 话说，这个linked list是哪种linked list？
: 如果是单向、每个node只能指向一个其它node的话......
: ......，那只要扫过一次所有node看看有没有node指向null就好了，没有就是有
这个方法就不行了..因为你怎麽知道你扫完所有node不是一直扫到重复的呢
前几篇也有人提到把每个扫过得做标记
但这样不就改了原本node的data..好像也不是个很好的做法
: cycle，因为此种linked list要是有回圈就一定是最後一个点指回了前面某个点XD。
: 不会是分支造成的，因为没法指向第二个点XD。时间上是O(N)，而且不需要额外的两
: 个ptr，只需要一个bool flag XD
: 当然这只判定了有没有，并没找出那一圈是啥。不过内文写「得知linked list
: 中有没有cycle」，那麽这样就可以了。
A->B->C
^
| |
E<-D
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 160.39.43.40
1F：→ ddavid:如上篇的推文，Linked list在拿到所有点的 114.42.108.102 01/26 12:55
2F：→ ddavid:情况下才能用的特殊解这样啦XD 114.42.108.102 01/26 12:55
3F：推 Huangs:如果用 hash table 来存每个点是否拜访过 61.217.25.93 01/26 16:46
4F：→ Huangs:也是一种标记方式。hash table每次 check 61.217.25.93 01/26 16:46
5F：→ Huangs:的平均复杂度是 O(1)，所以最後仍然是 O(N) 61.217.25.93 01/26 16:46
6F：→ adrianshum:hash table 这招不错耶... 我没想到 202.155.236.82 01/26 18:26
7F：推 ddavid:但在空间复杂度上输了，因为至少要O(N)，而 114.36.142.187 01/26 21:41
8F：→ ddavid:楼上你提的方法只要两个额外ptr，是O(1)。 114.36.142.187 01/26 21:41
9F：推 Huangs:linked list 就已经是 O(N) 61.217.25.93 01/28 13:25
10F：→ Huangs:再多 O(N) 也还是 O(N) 61.217.25.93 01/28 13:25
11F：→ Huangs:而且这题又没有要求空间复杂度 61.217.25.93 01/28 13:25
12F：推 ddavid:没有要求但是我们可以最佳化啊XD 114.36.137.168 01/28 19:54
13F：→ ddavid:标记法O(N)的系数小，但空间花得多，所以两 114.36.137.168 01/28 19:55
14F：→ ddavid:个方法依不同情况都会有用途。呃，不过实作 114.36.137.168 01/28 19:57
15F：→ ddavid:上标记法是否真的系数较小就难说了XD 114.36.137.168 01/28 19:58