Fully Explained! why fast and slow can meet in the cycle

  • 3

    I want to explain why we can get the answer when using fast-slow method. Share my opinion below.

    Fast-Slow Solution:

    public class Solution { //java version
        public boolean hasCycle(ListNode head) {
            ListNode fast = head;
            ListNode slow = head;
            while(fast != null && fast.next != null){            
                fast = fast.next.next; //2 times
                slow = slow.next;
                if(fast == slow) return true;
            return false;


    we assume that they can meet. Set the linear length as a, the cycle length as c, the slow's running distance from cycle's start point to meeting point as b. a and c are known, b is unknown. We want a equation to describe b by using a and c.

    Here is the diagram:

                   .   \     
                   c   2   
                   \  /     
    1-2-3-4-5-...-a -1  

    An important point is that, the running part of linear length is not a, actually it's a-1.** That's because they use head as start point:

        ListNode fast = head;
        ListNode slow = head;

    then begin to run:

            fast = fast.next.next;
            slow = slow.next;

    The head point can't be included when calculating this relation:

    slow total running length * 2 = fast total running length

    If fast's speed is twice of slow's speed, we can get:

    slow total running length = (a-1)+b //not a!!!
    fast total running length = 2*((a-1)+b) //2 can be t times

    Because they meet at point b, we can get equation:

    (fast total running length - running part of linear length) % c = b

    which is:

    (2*((a-1)+b) - (a-1))%c = b
    2*((a-1)+b) - (a-1) = n*c +b
    (a-1)+b = n*c
    b = n*c-a+1


    if fast and slow can meet, we can get a integer b when n is increasing where n is an integer starting from 0. Actually, the b is the first integer that is bigger than 0:

    b = n*c-a+1 //write it on paper, compare b with code's result


    if fast's speed is t times of slow's speed, we get:

    (fast total running length - running part of linear length) % c = b
    (t*((a-1)+b) - (a-1))%c = b

    Most general equation:

    b = n/(t-1) * c - a + 1 //1.fast&slow start from head, 2.t times, 3.a&c are known, 4.n from 0
                            //5.if b>c, b=b%c

    **(If we want to use a as the running part of linear length, we need a dummy head.)

    If there is anything wrong, please figure it out. Welcome to write your ideas below.

  • 0

    More general: if fast runs f steps and slow runs s steps(f>s, f>0, s>0)...I will try this later.

  • 0

    It really helps, thx.

Log in to reply

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