【第三轮】6.23-6.29 CareerCup 2.6

2.6
Given a circular linked list, implement an algorithm which returns the node at the beginning of the loop.
DEFINITION
Circular linked list: A (corrupt) linked list in which a node's next pointer points to an earlier node, so as to make a loop in the linked list.
EXAMPLE
Input:A ->B->C->D->E-> C[thesameCasearlier]
Output:C

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
龟兔赛跑
Proof:
K -- number of nodes before cycle start point in list
C -- number of nodes of cycle
Let the faster nodes forward 2 steps each turn, slow nodes forward 1 step each turn.
S -- how many steps slow node passed when two nodes meet.
X -- the node distance between the meet point and cycle start point

When two meet each other, lets say first nodes go through whole cycle M times, second nodes go through whole cycle N times, we have:

equation 1 => S = K + M *C + X
eq 2 => 2S = K + N * C + X

eq 2 - eq 1 => S  = (N - M) * C
Replace S in eq 1 => X = (N - M)C - K - M = (N - 2M)C - K

So at their meeting point, after K more steps the slower node will arrive the cycle start.
Inorder to do that we just need to put the fast node back to head and go one step forward each time, as well as slow node, until they meet each other again in the cycle start point

【时间复杂度】
O(N)

【空间复杂度】
O(1)

【gist link】
https://gist.github.com/chrislukkk/f452d108f42cc6a52110

【解题思路】
我还真不知道除了书上的技术, 还有什么好办法..计数法好像也可以..不过要先扫一下有多少个不同的元素.
【时间复杂度】
n, if there is a loop
【空间复杂度】
1
【gist link】
https://gist.github.com/gaoyike/f319f54ad7e9b9c4adea
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】Java利用object的hashcode(),用HashSet<Integer>存储每个object的hashcode()，遇到hashcode()一致的，则认为遇到了之前的object （参考了hawstein大神的算法）
C++可以对object的首地址进行hash
【时间复杂度】O(n)
【空间复杂度】O(n)
【gist link】https://gist.github.com/chouclee/02602d805ed9640ab10d

【解题思路】
书上很经典的解法，一般list中取一个点，普遍会想到采用快慢指针的概念。
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/UncleGarden/7542e36e48a297042df9

【解题思路】
using fast (2x) and slow (1x) pointers, when they meet, assign fast pointer to the beginning of the list, and the next time they meet is the beginning of the loop.
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/iwilbert/0c73b9dadb9cac4a0fa0
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】
no loop should return null

【解题思路】
the same as Linked List Cycle II in leetcode. set a fast point and a slow point.
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/JoyceeLee/8358b4b671949731cc42

【解题思路】
using fast (2x) and slow (1x) pointers, when they meet, assign fast pointer to the beginning of the list, and the next time they meet is the beginning of the loop. I used the method in the book
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】https://gist.github.com/hilda8519/2a4317a8d9fa1a9b8056

【解题思路】  faster and slower runner
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】  https://gist.github.com/jyhjuzi/d1238d32b9453e37167e

【解题思路】  
快慢指针
【时间复杂度】
O(N)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/WOLOHAHA/aff331d845cc880ccab3