# Java O(1) space solution with detailed explanation.

• @lwen8989gmail.com great, I understand! thank you!

• @lwen8989gmail.com Thank you for posting the diagram!

• @lwen8989gmail.com @jerry0723 @VincentCheng @syhxj @JayWong @xuyifan236
I think it should be a=n*c. where n is a positive integer

• @lwen8989gmail.com
Thanks for the diagram, A big help, but I think I can explain a little bit. It bothered me a while that the `fast` may runs several circles other than one when it meets `slow`. So here is my understanding:
Assume `fast` runs `m` circles and `slow` runs `n` circles when they meet. Then we can get the running distance of `fast` is twice as that of `slow`:
`a+m*(b+c)+b = a+n*(b+c)+b`
Hence we can get:
`m*b+m*c = (2*n+1)*b+2*n*c+a`
So there are 2 posibilities:
`1) 2*n+1+a/b = m && 2*n = m` OR
`2) 2*n+1 = m && 2*n+a/c = m`
In case `1)`, I get `b = -a`, which can be ignore because `a` and `b` should be greater than `0`.
So from case `2)`, I get `a = c`.

And brilliant idea of solving this problem! :)

• @karolQ in fact, your deduction is wrong.
counter-example: if only the last element form the circle and a is very large, then m is very large and n = 0. your second case totally wrong.

• The diagram helped a lot! Thank you for your effort!

if (head == null) return null;
boolean isMeet = false;
while (faster.next != null && faster.next.next != null) {
slower = slower.next;
if (!isMeet) faster = faster.next.next;
else faster = faster.next;
if (faster == slower) {
if (!isMeet) {//first time
isMeet = true;
} else {
return slower;
}
}
}
return null;
}

• @lwen8989gmail.com Super clear diagram, helped me understand the solution (thank you!), but not precise. Think of the case if `a=1000`, and `b+c=5`, then `a==c` is certainly not true! But that's OK, because we can still use the diagram, just means faster pointer has to go around the cycle a few extra times:

So faster pointer runs `a+b+n*(b+c)`, where `(b+c)` just means a complete cycle, for the case of `n=1`, we get `a+2b+c` as you did; the slow pointer runs `a+b` as before.

Since fast is 2 times faster than slow: `a+b+n*(b+c) = 2*(a+b)`, then though simple arithmetic we get `a=(n-1)*(b+c)+c`, again for the case of `n=1`, we get `a==c` as before. But we don't have to worry about `(n-1)*(b+c)` because `(b+c)` is just a complete cycle, and running it `(n-1)` times doesn't change any of our positions.

The rest of your explanation is perfectly valid, so we start again with 2 slow pointers, one travels the distance `a`; while the other travels starting from point p, goes through `(n-1)` complete cycles each with a distance of `(b+c)` to arrive at point p again, and finally travels an additional distance of `c` to arrive at q - the cycle start point meeting with the first pointer.

• @karolQ I think your analysis is really help!

• Javascript version:

``````var detectCycle = function(head) {

while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if(fast == slow) {
while(slow2 != slow) {
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
};
``````

• @lwen8989gmail.com you explanation is much better than @qgambit2 . But both of you provide good code.

• @lwen8989gmail.com your illustration is amazing :)

• @lwen8989gmail.com Great explanation with the diagram. None of the others made sense. Thank you very much sir.

• I think the formula exists error..
In my view, the correct one is below:
A + B + kN = 2A + 2B
kN = A +B

• @lwen8989gmail.com

Great graph with explain! Really appreciated

• @rubyfrea Yes, it should be nN + A + B = 2(A + B), I don't know why everybody is saying N = A + B, try 0->1->2->3->4->5->6->7->8->9->6, A should go 2 more cycle when they meet.

Actually, we can get nN - B = A, which is what we want. Since nN is what fast point goes longer than B and slow point has ready finished B in a cycle N, so slow point only needs to go nN - B, then he can reach A. So we set another point from head, then let it move nN - B, which is A. Then it reaches the entering-cycle point.

• @lwen8989gmail.com
Hey, I got a question. How can you make sure when fast and slow first met, fast travels exactly one more cycle than slow. That is , what if a+ 2b+c +b+c == 2(a+b)?

• Awesome solution!

• This remembers me of a computer game about a doctor like ricky trying to get to the exit using different tools like ice something else.
Does anyone know the name of this game?

• @lwen8989gmail.com Thank you for your explation!

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.