【第三轮】6.23-6.29 CareerCup 2.6

【解题思路】
大家想得都好复杂……linkedlist有两个功能分别是contains和remove。所以只要把list里每一个元素都删除后查看list里是否还包含相同值的元素。有的话则返回该值后break，没有的话就继续遍历该表。如果最后证明没有loop，则输出“您真逗儿”。
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist】
https://github.com/donnice/donnice/blob/master/Q2_6

是我想得太简单了么？求点评求指导

【解题思路】书上的方法，自己最开始想笨了，去用哈希保存，没有用这个更tricky的方法。原理自己证明一下就更容易记住。
【时间复杂度】O(N)
【空间复杂度】O(1)
https://gist.github.com/xun-gong/405acfb9e32a7c26f2a7

【解题思路】use a fast pointer and a slow pointer to find the loop start
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/JoshuaTang/d452f86d908029b800e0

【解题思路】比较猥琐的方法，直接用hashset存储所有的Node，如果出现重复，则为begin。
【时间复杂度】O(N)
【空间复杂度】O(N)
【gist link】https://gist.github.com/guchang/15692ad672dc01beb649

//【解题思路】
        //assume there is a loop
        * 用两个指针，慢指针以一个节点为前进单位，快指针以两个节点为前进单位。
        * 两个指针第一次相遇时的节点和链表起始节点距离环起始节点的距离相等
        * 此时，把其中一个节点指向链表起点，然后两个指针一起以一个节点为单位前进，再次相遇时的节点便是环起始节点。
//【时间复杂度】
//O(k+n)
//【空间复杂度】
//O(1)
//【gist link】
https://gist.github.com/Tsien/2b657a0bc23f0ca63350

【解题思路】
use tortoise & hare to detect whether the list has a cycle
if a cycle exists, move the one pointer to head, leave one point where it was
move two pointers at the pace of one step.
they will point to the start of the loop when they collide.

【时间复杂度】
O(n)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/happyWinner/62b20505882cd5bacd7c

第一次刷题发帖 求大神们帮忙看看 第一个方法的时间复杂度
gist link: https://github.com/eyrelzy/CrackingtheCodingInterview/commit/bf74cf22e0d488262887fe2d094c7b95b41ddfdd

grassgigi 发表于 2014-6-26 09:58
【解题思路】
龟兔赛跑
Proof:

大牛，我照着你的code写了一个bug，不知道哪里错了
http://www.1point3acres.com/bbs/thread-105023-1-1.html

Solution1
Idea: Using a hashSet to store the node info

Improvement: we can using hashSet the store the hashCode of the node.

Notice: two different object may have the same hashCode, java can use equals() method to avoid hash collide(one way to solve hash collide in java), so in the implementation, we cannot only use the hashCode to distinguish different object.

Time Complexity: O(n)
Space Complexity: O(n)

Solution2
Idea: same in Book

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

Time Complexity: O(n)
Space Complexity: O(1)

Code:
http://www.jyuan92.com/post-470