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

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

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

• It really helps, thx.

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