Java two-pointer solution.


  • 4
    C
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;   // no circle
        }
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {  // circle detected
                while (head != fast) {
                    fast = fast.next;
                    head = head.next;
                }
                return head;
            }
        }
        return null; // no circle
    }

  • 1
    Y

    how can you think of this solution´╝č


  • 0
    *

    @yhvivian You can find patterns. Most of the times, cycle detection problems can be solved using two-pointers.


  • 0
    J
    This post is deleted!

  • 2
    J

    A bit explaination.
    Provide the X is the length from head to the start point of circle and Y is the length of the circle. We know slow moves t, while fast moves 2t. They meet at K where is the length from the start point of the circle.
    Then we have :

    t = X + nY + K
    2t = X + mY + K
    

    , then we get

    X+K  =  (m-2n)Y 
    

    which means when they meet at K, the length from K to start point of the circle is just the X. At this moment, we use a head pointer to move by the same step (=1), and they must meet at the start point of the circle which we want.


  • 0
    N

    @jasonloveoj said in Java two-pointer solution.:

    A bit explaination.
    Provide the X is the length from head to the start point of circle and Y is the length of the circle. We know slow moves t, while fast moves 2t. They meet at K where is the length from the start point of the circle.
    Then we have :

    t = X + nY + K
    2t = X + mY + K
    

    , then we get

    X+K  =  (m-2n)Y 
    

    which means when they meet at K, the length from K to start point of the circle is just the X. At this moment, we use a head pointer to move by the same step (=1), and they must meet at the start point of the circle which we want.

    One further step to make it more clear:

    X = (Y - K) + (m - 2n - 1)Y
    

    which means by finishing the rest length of the circle and some number of circle lengths, the traveled distance is equal to X.


Log in to reply
 

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