Java O(1) space solution with detailed explanation.


  • 0
    W

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


  • 0
    I

    @lwen8989gmail.com Thank you for posting the diagram!


  • 1
    L

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


  • 3

    @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! :)


  • 0
    L

    @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.


  • 0
    S

    @lwen8989gmail.com said in Java O(1) space solution with detailed explanation.:

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


  • 0
    Z

    //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;
    }


  • 1
    B

    @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.


  • 0
    C

    @karolQ I think your analysis is really help!


  • 0
    R

    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;
        };
    

  • 0
    K

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


  • 0

    @lwen8989gmail.com your illustration is amazing :)


  • 0
    J

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


  • 1
    M

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


  • 0
    J

    @lwen8989gmail.com

    Great graph with explain! Really appreciated


  • 0
    L

    @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.


  • 0
    W

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


  • 0
    F

    Awesome solution!


  • 0
    D

    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?


  • 0
    S

    @lwen8989gmail.com Thank you for your explation!


Log in to reply
 

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