作者FRAXIS (喔喔)
看板Prob_Solve
标题Re: [请益] linked list里如何找cycle?
时间Wed Jan 27 09:38:43 2010
※ 引述《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)变数，阵列是唯读。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：推 Lucemia:想了一下果然都是cycle detect 的问题 01/27 17:41
2F：推 Lucemia:另外不加这些条件的话用hash就很好解了 01/27 17:44
3F：推 cplusplus:请问最後一题需要考虑重复个数>2和超过两组值吗?? 01/27 23:55
4F：→ FRAXIS:哈 忘记加那个条件 应该只能有一组重复 01/28 09:23
※ 编辑: FRAXIS 来自: 140.119.162.50 (01/28 09:50)
5F：推 cplusplus:那就很简单了 :) 01/28 16:26
6F：→ cplusplus:本来想了很久怎麽解决多组&多个...没想到 01/28 16:27
7F：→ yoco315:起点我想了好久 -_-" 今天有空就在想.. 01/29 00:28
8F：→ yoco315:刚刚快睡着的时候终於想到了... XD 01/29 00:29