Java O(1) space solution with detailed explanation.



@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 thefast
may runs several circles other than one when it meetsslow
. So here is my understanding:
Assumefast
runsm
circles andslow
runsn
circles when they meet. Then we can get the running distance offast
is twice as that ofslow
:
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 case1)
, I getb = a
, which can be ignore becausea
andb
should be greater than0
.
So from case2)
, I geta = c
.And brilliant idea of solving this problem! :)

@karolQ in fact, your deduction is wrong.
counterexample: 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.

@lwen8989gmail.com said in Java O(1) space solution with detailed explanation.:
The diagram helped a lot! Thank you for your effort!

//what about this?
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
ListNode slower = head;
ListNode faster = head;
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
if (slower == head) return head;
isMeet = true;
slower = head;
} 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
, andb+c=5
, thena==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 ofn=1
, we geta+2b+c
as you did; the slow pointer runsa+b
as before.Since fast is 2 times faster than slow:
a+b+n*(b+c) = 2*(a+b)
, then though simple arithmetic we geta=(n1)*(b+c)+c
, again for the case ofn=1
, we geta==c
as before. But we don't have to worry about(n1)*(b+c)
because(b+c)
is just a complete cycle, and running it(n1)
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(n1)
complete cycles each with a distance of(b+c)
to arrive at point p again, and finally travels an additional distance ofc
to arrive at q  the cycle start point meeting with the first pointer.


Javascript version:
var detectCycle = function(head) { var slow = head; var fast = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if(fast == slow) { var slow2 = head; 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 Great explanation with the diagram. None of the others made sense. Thank you very much sir.


@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 enteringcycle 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)?
