作者bobju (宝贝猪)
看板Programming
标题Re: [请益] linked list里如何找cycle?
时间Mon Jan 25 21:18:57 2010
※ 引述《pikahacker (喵)》之铭言：
: ※ [本文转录自 Prob_Solve 看板]
: 作者: pikahacker (喵) 看板: Prob_Solve
: 标题: [请益] linked list里如何找cycle?
: 时间: Mon Jan 25 13:06:55 2010
: 如果有人给你一个linked list
: 有办法在O(N)时间内,得知linked list中有没有cycle?
如果条件只是如此, 那应该很简单吧?
只要在走访过的node里留下一个记号, 接着继续走访下一个node,
若在途中再次走访到有记号的node, 就代表有cycle; 若直走到null
都没再遇到有记号的node就代表没cycle.
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 58.115.151.184
1F：→ adrianshum:这方法是 linked list 的 node 有地方 202.155.236.82 01/26 14:40
2F：→ adrianshum:让你放那个 flag 才行, 一般的 linked 202.155.236.82 01/26 14:40
3F：→ adrianshum:list 不能当它有这种 field 吧... 202.155.236.82 01/26 14:41
4F：→ bobju:但是问题里并没强调这点啊~所以我才语带保留 58.115.151.184 01/26 14:50
5F：→ bobju:如果这linked list的资料结构是我订的,我当 58.115.151.184 01/26 14:50
6F：→ bobju:然采用这种方法. 58.115.151.184 01/26 14:51
7F：→ adrianshum:问题只说给你一条 linked list, 怎可以 202.155.236.82 01/26 16:03
8F：→ adrianshum:当是自己定义的东西? 可以自订, 我能做 202.155.236.82 01/26 16:04
9F：→ adrianshum:到 O(1) 喽... 只要在插入 node 的时候 202.155.236.82 01/26 16:04
10F：→ adrianshum:做手脚就好了... 202.155.236.82 01/26 16:04
11F：→ adrianshum:况且问题是 "有人给你一个linked list" 202.155.236.82 01/26 16:05
12F：→ adrianshum:明显就不是自己的东西了... 202.155.236.82 01/26 16:05
13F：→ bobju:问题只给你一条linked list,但却没有限制说 58.115.151.184 01/26 18:00
14F：→ bobju:不能复制或是写入,这就是规则上的不明确. 58.115.151.184 01/26 18:00
15F：→ bobju:我在走访节点的同时,复制并写入到另一条link 58.115.151.184 01/26 18:01
16F：→ bobju:ed list, 并不会破坏原来的linked list,照样 58.115.151.184 01/26 18:01
17F：→ bobju:可依我的方法达到判断的目的. 当然我知道你 58.115.151.184 01/26 18:02
18F：→ bobju:的方法很smart, 只是除非有点演算法的功底, 58.115.151.184 01/26 18:02
19F：→ bobju:否则临场会解答只怕还得脑袋灵光不失常才行. 58.115.151.184 01/26 18:02
20F：→ bobju:另外,要证明O(N)只怕功底就得更深厚了. 58.115.151.184 01/26 18:03
21F：→ adrianshum:复制到另一 linked list 其实这就是我 202.155.236.82 01/26 18:23
22F：→ adrianshum:第一次回答的做法 :P 不过在 "检查" 202.155.236.82 01/26 18:23
23F：→ adrianshum:这部份令到 complexity 变高 (O(N^2)?) 202.155.236.82 01/26 18:24
24F：→ bobju:如果用阵列静态复制,在检查时就是O(N^2),但 58.115.151.184 01/29 14:18
25F：→ bobju:是用动态复制就不会. 58.115.151.184 01/29 14:18