[第二轮] 2/25-3/3 CareerCup 2.6

想了很久都想不到，還是看答案了

C language:
https://gist.github.com/hukun01/5075970

moophis 发表于 2013-3-2 11:01
我估计是你的析构函数出问题了，可能是因为对于有环的链表你在最后释放的时候死在while循环里了。貌似是这 ...

嗯，对，就是这个问题，thanks for pointing out this, lol :)

moophis 发表于 2013-3-2 10:50
看了答案以后写的，这个解法之前确实想不到，能给个证明吗？
https://github.com/moophis/careercup/blob/ ...

你给的链接打不开，嘿嘿

moophis 发表于 2013-3-2 10:50
看了答案以后写的，这个解法之前确实想不到，能给个证明吗？
https://github.com/moophis/careercup/blob/ ...

如果你是通过两个指针来做的话，一个简单的证明可以这样来想：
fast指针速度为2， slow指针速度为1， 那么当两个指针相遇的时候，假设时间为t，那么2*t-1*t=n*len, i.e. t=n*len, 其中len为环的长度，也就是说slow指针走的距离为环的长度的n倍。相遇必定是在环内的某一个nodeX上，那么从head到这个nodeX相距的长度就是这个环的长度。这个时候，一个指针从head重新走，一个指针从相遇nodeX的下一个node开始走，当再次相遇时，肯定是环的交点，因为从交点以后，到走完一个环的距离是想的相等的。
不知道我说清楚没，如果你需要严格的数学证明也是可以的

weep_willow 发表于 2013-3-4 04:24
如果你是通过两个指针来做的话，一个简单的证明可以这样来想：
fast指针速度为2， slow指针速度为1， 那 ...

嗯，这样好像说的通，谢谢啦！我后来把文件名改了，所以链接挂了。。。已经改好

champoier 发表于 2013-2-28 14:25
two pointers, 一个步长为1，一个步长为2，从头开始扫，第一次聚合后，一个指针只回头，另一个从当前位置起 ...

擦，我这智商，没看懂为什么第二次相遇就是要找的点

leonsu777 发表于 2013-3-1 02:42
https://gist.github.com/longwei/5059008
同学们 上代码啊
如果可以改node 的代码 @qeroqero 的办法挺好 ...

不应该hash node的value  应该hash node的内存地址

weep_willow 发表于 2013-3-4 04:24
如果你是通过两个指针来做的话，一个简单的证明可以这样来想：
fast指针速度为2， slow指针速度为1， 那 ...

擦，我这智商。。


1  为什么   [那么从head到这个nodeX相距的长度就是这个环的长度] 而不是 [这个环的长度的n倍]
2  第二次他们以相同速度运动，为什么一定会相遇

weep_willow 发表于 2013-3-4 04:24
如果你是通过两个指针来做的话，一个简单的证明可以这样来想：
fast指针速度为2， slow指针速度为1， 那 ...

终于看懂了

这个证明不是很难，设环之前的长度为L1，环的长度为L2，第一次一快一慢两个指针如果在n步之后相遇，那么2n-n=n=k*L2. 这时候从环的起点开始数，相遇的位置为第(n-L1)mod L2 = (k*L2-L1)mod L2个结点, 从这个结点出发再走L1步就有(k*L2-L1+L1)mod L2=0，所以L1步之后我们就停在了环的第一个结点上。
但是正着想就没头绪了，第一个发明这方法的人是怎么想到的？我觉得这个问题更重要一点