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


  • 3
    M

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

    First,

    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:

                   b..3    
                   .   \     
                   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
    

    Then,

    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
    

    Generally,

    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
    M

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


  • 0
    I

    It really helps, thx.


Log in to reply
 

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