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

在节点里设置一个bool值，初始为false，遍历后改为true..再次遍历到第一个true值为answer

https://gist.github.com/longwei/5059008
同学们 上代码啊
如果可以改node 的代码 @qeroqero 的办法挺好。
额外的memory允许的话， 可以加一个hashmap，hash每个node的value。

* Solution: use two poninters, speedPtr1 and speedPtr2. In the first round , the speed of speedPtr2 is twice the speed of speedPtr1, move these  two pointers until they meet each other(circle exists), otherwise(no circle); When they meet, restart speedPtr1 from header pointer and speedPtr2 from the next node with the same speed as speedPtr1. move them one node by one node, when they meet again, that's where the circle starts.

c/c++实现

https://github.com/StanleyLee/CareerCup/blob/master/2_6.cpp

【bug求助】程序运行都正常，就是最终检测到circle后， 也正常输出“fn exits" 的测试string，但是就是这句运行完，程序不自动退出，是在不知道问题在哪。希望哪位大神能帮忙解答一下，谢谢啦 ：）

https://github.com/quantumrose/C ... .FindBeginning.java
答案解法......

看了答案以后写的，这个解法之前确实想不到，能给个证明吗？
https://github.com/moophis/careercup/blob/master/2.2-7.cpp#L382

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

When the input linked list doesn't contain a loop, your code will definitely crash...So you have to handle this case.

weep_willow 发表于 2013-3-1 23:47
* Solution: use two poninters, speedPtr1 and speedPtr2. In the first round , the speed of speedPtr2 ...

我估计是你的析构函数出问题了，可能是因为对于有环的链表你在最后释放的时候死在while循环里了。貌似是这个问题。

moophis 发表于 2013-3-1 21:55
When the input linked list doesn't contain a loop, your code will definitely crash...So you have t ...

是的，我写的时候是默认有环的。已改。多谢！

有个idea，遍历过程中 过了每个node以后把这个node.next = null
然后return最后遍历停止的那个node

不过这个好像破坏链表结构了。。应该不满足要求吧
如果要存储这些破坏的信息再最后重构的话，好像还不如直接用hashset存每个node呢..
implementation of the idea from the book
https://gist.github.com/flatlight/5075335

https://gist.github.com/ThunderXu/5074340
FirstMethod: use a hashset
SecondMethod: use a faster pointer which step by 2 and a slower pointer which step by 1, reset the faster pointer to head of the list when they first meets, and then make they forward step by 1 together, when they meet again, the place they meet is the begining of the loop. I copy this idea from former comments