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從原處開始，同樣的速度前進。它們相遇的地方就是我們要的數。