作者nikeasyanzi (nikeasyanzi)
看板Prob_Solve
标题Re: [请益] linked list里如何找cycle?
时间Mon Oct 7 22:19:13 2013
想请问版上先进
如果只是单纯singal linking list
那可以用floyd's algorithm 即可解
但万一是任意node 允许连到两个以上相异点 类似m-way tree
parent 可能不只有一个child
用floyd's algorithm不就解不了?
只能用kruskal algorithm 一个个edge加入来检查cycle这样 是嬷?
还是有其他更好的演算法??
恳请赐教!
※ 引述《FRAXIS (喔喔)》之铭言：
: ※ 引述《pikahacker (喵)》之铭言：
: : 如果有人给你一个linked list
: : 有办法在O(N)时间内,得知linked list中有没有cycle?
: 这种题目算是面试常见题吧..
: 有时候除了要判断有没有cycle，还会问cycle起点在哪？
: 这种问题都会要求O(n)时间O(1)变数，且串列是唯读的。
: 还有一个变型，给定两条单向链结串列L和L'，但是L和L'可能在中途会
: 指向同一个节点，然後就重合到串列的尾巴（因为是单向的）。
: 要怎麽判断有无重合？重合的起点在哪？ 要求O(n)的时间和O(1)变数。
: 另外也有一个相关问题
: 给定一个长度为n+1的阵列 a1 ... an+1，1 <= ak <= n for all k
: 除了一对ai=aj之外，其他ak的值都是相异的
: ai是多少？i和j是多少？ 只能使用O(n)的时间和O(1)变数，阵列是唯读。
--
CyberPanel 5000CP 换 NT.500
http://myurl.com.tw/05bd
EmailCash 5000e 换 NT.500
http://myurl.com.tw/rgdq
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 111.251.199.98
1F：→ scwg:这边讨论的 singly linked list 是用走一步走两步线性解的吧 10/08 00:06
2F：→ scwg:对任意 non-weighted graph 用 bfs 或 dfs 都可以只是要额外 10/08 00:09
3F：→ scwg:空间 (或时间), 用不到 Floyd-Warshall 啊.. 10/08 00:09
4F：推 singlovesong:linked list 不准有两个next吧? 10/08 08:57
5F：→ nikeasyanzi:回scwg大:没错 若任意的graph 用DFS BFS 是可以的 10/08 14:34
※ 编辑: nikeasyanzi 来自: 140.113.136.221 (10/08 14:35)
6F：→ nikeasyanzi:回singal link list是有定义只有一个node没错 10/08 14:36
7F：→ nikeasyanzi:只是小弟想询问 万一不是link list 怎麽办 10/08 14:37
8F：→ nikeasyanzi:因为floyd 似乎只适用在只有一个child 的graph上!!?? 10/08 14:39
9F：→ scwg:你看的是哪里的 floyd o_O 10/08 20:35
10F：推 guest2:我猜是指Tortoise and Hare Algorithm (floyd algo.) 10/08 23:32