Объяснение поиска начального узла цикла в связанном списке

Учитывая связанный список с циклом, рассмотрим 2 указателя - один указатель (медленный указатель) движется со скоростью, а другой указатель (быстрый указатель) перемещается со скоростью 2 * с. Учитывая цикл в связанном списке, эти два указателя обязательно встретятся в точке внутри цикла.

Расстояние, пройденное медленным указателем до места встречи:

D(slow)=x+t1*(y+z)
t1: rounds of loop taken by slow pointer till slow and fast pointer meet at a point
D(fast)=x+t2*(y+z)
t2 : rounds taken by fast pointer till slow and fast pointer meet at a point

И медленному, и быстрому указателю требуется одинаковое количество времени, чтобы достичь точки встречи.

Time taken by slow pointer=Time taken by fast pointer
(since Time= Distance/speed)
(x+t1*(loop)+y)/s =(x+ t2*(loop)+y)/2s
2(x+t1*(loop)+y)= x+t2*(loop)+y
2x-x+ (t1-t2)*(loop)+2y-y=0
x+ (t1-t2)*(loop)+y=0
since loop= y+z
x+(t1-t2)*(y+z)+y=0
x+(t1-t2+1)*y+(t1-t2)*z=0
x=(t2-t1)*z +(t2-t1-1)*y -------(i)

Здесь слишком много уравнений, правда?

Рассмотрим пример:

Обозначения (D представляет x, K представляет y и M представляет z)

Здесь x = 8, y = 1 и z = 2

быстрый указатель запускается в цикле 3 раза, пока не достигнет точки встречи, следовательно, t2 = 3

медленный указатель достигает точки встречи до завершения цикла, следовательно, t1 = 0

из уравнения (i)

x=(t2-t1)*z +(t2-t1-1)*y

мы знаем, x = 8

давайте найдем RHS и проверим, если LHS = RHS?

расчет стоимости на правой стороне:

(t2-t1)*z+(t2-t1–1)*y (substituting values: t2=3, t1=0, z=2, y=1)
  (3-0)*2+(3 -0-1)*1
=  3*2+(2)*1
=  8

Итак, расстояние от заголовка связанного списка = расстояние от точки встречи до встречи обоих указателей. Если мы начнем указатель с заголовка связанного списка, а другой - с точки встречи, то где они встретятся?

цикл: z + y

ПРА: (t2-t1) * z + (t2-t1–1) * y (считается, что мы находимся в точке встречи)

Давайте изменим перспективу и сделаем y шагов назад, и мы достигнем начальной точки цикла, верно?

теперь правая часть RHS становится: (t2-t1) * z + (t2-t1–1) * y + y (считается, что мы находимся в начальной точке, и поскольку расстояние y уже было покрыто указателем, поэтому оно не было включено. Но теперь, когда мы меняем перспективу проблемы и считаем, что она начинается с начала цикла, нам нужно добавить y к правой стороне. Простая математика)

=> (t2-t1)*z+(t2-t1)*y

=> (t2-t1)*(y+z)

= ›(T2-t1) * (цикл)

Теперь это всегда будет в исходной позиции, независимо от того, что такое t2 и t1, поскольку цикл будет завершен полностью.

и поскольку LHS = RHS (как уже доказано)

Таким образом, легко заметить, что если мы начнем указатель с заголовка связанного списка, а другой - с точки встречи связанного списка, указатели пройдут одинаковое расстояние и встретятся в начальном узле списка.

Вот реализация описанного выше подхода на java:

public Node detectCycle(Node head) {
        Node slow=head ,fast=head;
     
        while(fast!=null && fast.next!=null && slow.next!=null)
        {
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
                    break;
            
            
        }
        if(fast==null || fast.next==null) //if there is no loop
            return null;
        else
        {
            slow=head; //starting the pointer from head
            while(slow!=fast)
            {
                slow=slow.next;
                fast=fast.next;
            }
            return slow;
        }
        
    }

Сложность по времени - O (n), а сложность по пространству - O (1)

Удачного кодирования и приятной отладки :)