solution

来源: dynamic 于 2009-05-20 21:41:18 [档案] [旧帖] [给我悄悄话] 本文已被阅读：次 (572 bytes)

本文内容已被 [ dynamic ] 在 2009-06-09 09:31:02 编辑过。如有问题，请报告版主或论坛管理删除.

回答: Loop in single linked list 由外-国人于 2009-05-15 07:55:51

这题有一些不同的做法，这里提供一种：

首先把这个数组看成一个有向图：如果a[i]=j，那么就加一条从i到j的边。不难发现，每个点的out-degree都是1。

如果从n+1这个点出发，那么我们会进入一个cycle，并且这个cycle不含n+1（形状像一个勺子，或者说希腊字母rho）。那个cycle的"entrance"就至少被两个数指向，所以我们就只需要找到那个entrance。

先从n+1出发，走n步，此时肯定已经进入cycle了。记录下此时位置，看继续多少步后回到原处，就求出了cycle的长度k。

然后重新回到n+1。让一个pointer先走k步，另一个pointer从原处开始，同样的速度前进。它们相遇的地方就是我们要的数。