google搜了一下的答案,前提是有range,而且是n+1的元素,但是不用加法解,不会溢
出:
Solution: (by Ovidiu Gheorghioiu at Google) Treat the values of the array as
pointers into the same array. Let us call a chain of pointers a “linked
list”. The linked list starting with the last entry must have the shape of
a “lollipop” with a stick and a cycle. Our goal is to identify that node
in the linked list that joins the stick to the cycle. We do so in two phases:
Phase I: maintain two pointers, one ‘slow’ and one ‘fast’. In one round,
the slow pointer advances one step and the fast pointer advances two steps
along the linked list — both pointers advance simultaneously. Phase I comes
to an end when the two pointers become equal at the end of a round.
Phase II: maintain two pointers, both ‘slow’. The first slow pointer
starts where Phase I ended. The second slow pointer starts at the beginning
of the linked list. Phase II ends when these two pointers become equal at
the end of a round. This node, magically, is the duplicate (in other words,
that node in the linked list where the stick joins the cycle)!
但是没看懂怎么从array转化为链表。