[第二轮] 2/25-3/3 CareerCup 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 [the same C as earlier]
Output: C

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

两个指针一快一慢，经典算法吧
时间复杂： O(N)
空间复杂：O(1)

https://gist.github.com/daisyang/5521dd686dcb792ff86d

store each appearing pointer, compare the pointer to the pool while iterate the node O(N)
Btw, what does the ‘corrupt’ mean...

EchoMemory 发表于 2013-2-24 13:51
store each appearing pointer, compare the pointer to the pool while iterate the node O(N)
Btw, what ...

Maybe it means the order of the list is corrupt.

lvchaoshuai 发表于 2013-2-24 18:46
Maybe it means the order of the list is corrupt.

I see... the word is a bit strange...

I use two pointers.
The first pointer move front with one step, and the second move front with two steps.
when they meet each other, set the second pointer to the start of the linked list.
Move one step at the same time, when they meet again, the node is the start of the circle.

gist: https://gist.github.com/sing1ee/5036554

lz, can I comprehand in this way: the stored address in the second C is A. So I should write a code to find the second C?

one node pointer forwards two step each time, called fast node
one node pointer forwards one step each time, called slow node
Since two nodes will in loop, so they will meet in somewhere sometime
最后还是参考了答案, 实现了一下答案，确实精妙..
https://gist.github.com/chrislukkk/5040122

liuzhe1218 发表于 2013-2-26 15:14
lz, can I comprehand in this way: the stored address in the second C is A. So I should write a code  ...

I think the second C is the same node as the first C so the loop is C->D->E->C, so node C is the start point of the loop in this link list, which should return as required

grassgigi 发表于 2013-2-26 15:59
one node pointer forwards two step each time, called fast node
one node pointer forwards one step e ...

代码写得比我认真

two pointers, 一个步长为1，一个步长为2，从头开始扫，第一次聚合后，一个指针只回头，另一个从当前位置起，两个一起一步长为1移动……再次聚首时，则为要找的点。

https://gist.github.com/skxie/674da5d07d7387ad6e11