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)
☆──────────────
相关阅读
尾递归不会导致堆栈溢出吗?有三赢的可能?Golang 真是优秀的生产力工具微信群的聊天机器人还是很初级的问个python题目关于诈骗的定义[bssd]国内一些信息分享996 icu请教一个C++ 的 iterator 问题。MSFT破万亿了再有正式fulltime的情况下 还能做一个contract 的job吗请教手机上开发地图应用的程序语言选择问题爱德蒙·贝拉米肖像前一段版上讨论的server side的auto complete技术如何生成一个确定大小的sparse分区文件Python 进浏览器了MSFT Intelligent cloud持续成功Re: 请教万能的买买提一个数学建模问题 (转载)有没有开源的configurable workflow库推荐?Hinton的仿生学思路