【第三轮】6.23-6.29 CareerCup 2.6

"""
============================================================================
Solution        : Faster pointer moves two steps at a time,
                    slower pointer moves onw step at a time,
                    after their first time meet,
                    reset fater pointer back to head
                    return slower when they meet again
Time Complexity : O(n)
Space Complexity: O(1)
Gist Link       : https://gist.github.com/habina/d8bbd5fbe1567502c676
============================================================================
"""

【解题思路】  No idea till read the book... faster pointer and slower pointer, slower pointer move 1 step each time, faster pointer move 2 steps each time. When they meet, assign one of them as the header of the linked list, when they meet again, output the node
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】 https://gist.github.com/bitcpf/7790d1e5f963ae582fe2

【解题思路】 看书上的解法，用快慢指针
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】 https://gist.github.com/yokiy/da71157d9de7dc6491ba

【解题思路】 用HashSet存每个node，遇到一样的就返回。再就是书上space O(1)的解法了
【时间复杂度】
O(N)
【空间复杂度】
O(n)
【gist link】 https://gist.github.com/XiaoxiaoLi/2dcd9f629fef8469a1f7

【解题思路】assume one loop in the list, use a hashset to store node, traverse the list and see if a node has already been in the set
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/startupjing/33c7e74aca2ab63441ae

【解题思路】Use fast and slow runner. If fast and slow runner meet, there is a loop.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/nealhu/e333fc1162464261f663

【解题思路】
1. Floyd's algorithm
2. Brent's algorithm
C.f. wiki page: cycle detection
【时间复杂度】
O(λ + μ)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/04fef6f51373925ab3a6
【test case】
null list
no loop
common case

【解题思路】Fast/Slow 指针
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link】https://gist.github.com/weazord/8ddffcbd65ed86fb00aa

【解题思路】Use slow and fast pointers. When they meet, move slow pointer to head. Then move two pointers with the same pace until they meet.
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link】https://gist.github.com/jason51122/cafb1093ab8fb82ee0b0