b***y
发帖数: 2799 | 1 ☆─────────────────────────────────────☆
wmbyhh (wmbyhh) 于 (Fri Jul 18 22:00:22 2008) 提到:
一个链表中有环，如何求解这个环的起始位置。
网上已经有人给出答案，就是用2个指针，p=p->next, q=q->next->next，找到它们相
遇的位置，再求解这个环长度Y,从起点head到这个相遇位置长度L，
然后另2个指针，1个从head出发，1个从距离相遇位置Y-L%Y位置出发，直到这2个指针
相遇，此时就是环在链表中的起始地址。
现在我还是不懂得，这个L%Y是如何来的。
请指点一下。
☆─────────────────────────────────────☆
goodbug (好虫) 于 (Fri Jul 18 22:12:19 2008) 提到:
这么复杂干啥？先找出环，这标准的跳1跳2就可以弄出来，转一圈记录长度。
然后环上设一指针静止，另一指针从头上走，碰到为止，记录步数。
如此转一整圈，最小值就是起始位置。
时间复杂度都是O(N^2)
☆────────────── |
|
