b*y
2 楼
☆─────────────────────────────────────☆
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)
☆──────────────
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)
☆──────────────
j*y
3 楼
嗯
准再找个板斧开博采了
呵呵
【在 d****n 的大作中提到】
准再找个板斧开博采了
呵呵
【在 d****n 的大作中提到】
相关阅读
DNN就是hype (转载)mobile后端 什么tech stack 最快糙猛？mongodb 3.2 有人用吗Pandas DataFrame: how to plot candlestick with datetime xlabels?现在哪个DPDK的TCP/IP Stack比较好？sharing pluralsight还是我那句话，不作不死谁推荐个 machine learning 入门教程月光教授和金教授的前世今生 (下三滥的程序员)快速系统学习 c++ design pattern有什么好书或者网站吗realtime轮子deepstream.io现在Scala又火了？再次请教个linux组合问题请教一下，各位牛人觉得Rust语言怎么样？求问个C# gc的问题能把pc上的单机程序转成online的么？围棋人机大战细则出炉 李世石最多拿到125万美元太喜欢plotly了请教 怎么实现保存搜索结果的URL不明白为啥std::nth_element不叫做kth_element