обнаружение запуска цикла в отдельно связанном списке ссылок?

void loopstartpoint(Node head){
    Node slow = head.next;;
    Node fast = head.next.next;

    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;

        if(slow==fast){
            System.out.println("Detected loop ");
            break;
        }
    }

    slow=head;
    while(slow!=fast){
        slow= slow.next;
        fast = fast.next;
    }
    System.out.println("Starting position of loop is "+slow.data);
}

1. Действуйте, как обычно, чтобы найти петлю. то есть. Имейте два указателя, увеличивайте один за один шаг, а другой за два шага. Если они оба встретятся через некоторое время, есть цикл.

2. Держите один из указателей фиксированным, чтобы получить общее количество узлов в цикле, скажем L.

3. Теперь с этой точки (увеличьте второй указатель на следующий узел в цикле) в цикле сторнируйте связанный список и сосчитайте количество пройденных узлов, скажем, X.

4. Теперь, используя второй указатель (цикл разорван) из той же точки цикла, просмотрите связанный список и посчитайте количество оставшихся узлов, скажем, Y

5. Цикл начинается после ((X + Y) -L) \ 2 узлов. Или он начинается с (((X + Y) -L) \ 2 + 1) -го узла.

Ну, я попробовал способ, используя один указатель ... Я попробовал метод в нескольких наборах данных .... Поскольку память для каждого из узлов связанного списка распределяется в возрастающем порядке, поэтому при обходе связанный список из заголовка связанного списка, если адрес узла становится больше, чем адрес узла, на который он указывает, мы можем определить, есть ли цикл, а также начальный элемент цикла.

Это код для поиска начала цикла в связанном списке:

public static void findStartOfLoop(Node n) {

    Node fast, slow;
    fast = slow = n;
    do {
        fast = fast.next.next;
        slow = slow.next;
    } while (fast != slow);       

    fast = n;
    do {
        fast = fast.next;
        slow = slow.next;
    }while (fast != slow);

    System.out.println(" Start of Loop : " + fast.v);
}

Действуйте в обычном порядке, который вы будете использовать, чтобы найти петлю. то есть. Имейте два указателя, увеличивайте один за один шаг (slowPointer) и другой за два шага (fastPointer). Если они оба встретятся через некоторое время, есть цикл.

Как вы, возможно, уже поняли, что местом встречи является k Шаг до начала цикла.

где k - размер не зацикленной части списка.

теперь медленно передвигаются к началу цикла

держите Fast в точке столкновения

, каждый из них k STep от начала цикла (Slow от начала списка, где fast k шаг до начала цикла - нарисуйте рис, чтобы получить ясность)

Теперь двигайте их с той же скоростью - они должны встретиться в начале цикла

например

slow=head
while (slow!=fast)
{
     slow=slow.next;
     fast=fast.next;
}

Сначала мы попытаемся выяснить, есть ли петля в списке или нет. Если цикл существует, то мы пытаемся выяснить начальную точку цикла. Для этого мы используем два указателя, а именно slowPtr и fastPtr. При первом обнаружении (проверка на наличие петли) fastPtr перемещается сразу на два шага, но slowPtr перемещается на один шаг вперед сразу.

slowPtr   1   2   3   4   5   6   7
fastPtr   1   3   5   7   9   5   7

Ясно, что если в списке есть петли, то они встретятся в точке (точка 7 на изображении выше), потому что указатель fastPtr работает в два раза быстрее, чем другой.

Теперь мы подошли ко второй проблеме нахождения начальной точки цикла.

Предположим, они встречаются в точке 7 (как упомянуто на изображении выше). Затем slowPtr выходит из цикла и стоит в начале списка, значит, в точке 1, но fastPtr все еще в точке встречи (точка 7). Теперь мы сравниваем значение обоих указателей, если они одинаковые, то это начальная точка цикла, в противном случае мы перемещаемся на один шаг вперед (здесь fastPtr также перемещается на один шаг каждый раз) и сравниваем снова, пока не найдем ту же точку.

slowPtr   1   2   3   4
fastPtr   7   8   9   4

Теперь возникает один вопрос, как это возможно. Так что есть хорошее математическое доказательство.

Предположим:

m => length from starting of list to starting of loop (i.e 1-2-3-4)
l => length of loop (i.e. 4-5-6-7-8-9)
k => length between starting of loop to meeting point (i.e. 4-5-6-7)

Total distance traveled by slowPtr = m + p(l) +k
where p => number of repetition of circle covered by slowPtr

Total distance traveled by fastPtr = m + q(l) + k
where q => number of repetition of circle covered by fastPtr

Since,
fastPtr running twice faster than slowPtr

Hence,
Total distance traveled by fastPtr = 2 X Total distance traveled by slowPtr
i.e
m + q(l) + k = 2 * ( m + p(l) +k )
or, m + k = q(l) - p(l)
or, m + k = (q-p) l
or, m = (q-p) l - k

So,
If slowPtr starts from beginning of list and travels "m" length then, it will reach to Point 4 (i.e. 1-2-3-4)

and
fastPtr start from Point 7 and travels " (q-p) l - k " length then, it will reach to Point 4 (i.e. 7-8-9-4),
because "(q-p) l" is a complete circle length with " (q-p) " times.

Более подробно здесь

МАТЕМАТИЧЕСКАЯ ДОКАЗАТЕЛЬСТВО + РЕШЕНИЕ

Let 'k' be the number of steps from HEADER to BEGINLOOP.
Let 'm' be the number of steps from HEADER to MEETPOINT.
Let 'n' be the number of steps in the loop.
Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P.

ПРОСТОЙ СЛУЧАЙ: Когда k < N

Когда указатель «P» будет в BEGINLOOP (то есть он прошел бы «k» шагов), Q прошел бы «2k» шагов. Таким образом, по сути, Q опережает «2k-k = k» шагов от P, когда P входит в цикл, и, следовательно, Q сейчас находится на «n-k» шагах позади BEGINLOOP.

Когда P переместился бы из BEGINLOOP в MEETPONT, он прошел бы шаги «m-k». За это время Q прошел бы «2 (m-k)» шага. Но, поскольку они встретились, и Q начал «nk» на шаг позади BEGINLOOP, то есть «2 (mk) - (nk)» должно быть равно «(mk)». Итак,

=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m

Это означает, что P и Q встречаются в точке, равной количеству шагов (или кратным, чтобы быть общим, см. Случай, упомянутый ниже) в цикле. Теперь, в МЕТОЧНОЙ ТОЧКЕ, и P, и Q находятся на «n- (m-k)» шагах позади, то есть на «k» шагах позади, как мы видели n = m. Итак, если мы снова начнем P с HEADER, а Q с MEETPOINT, но на этот раз с темпом, равным P, P и Q будут теперь встречаться только в BEGINLOOP.

ОБЩИЙ СЛУЧАЙ: Скажите, k = nX + Y, Y < n (Следовательно, k% n = Y)

Когда указатель «P» будет в BEGINLOOP (то есть он прошел бы «k» шагов), Q прошел бы «2k» шагов. Таким образом, фактически Q опережает шаги «2k-k = k» от P, когда P входит в цикл. Но, пожалуйста, обратите внимание, что «k» больше, чем «n», что означает, что Q сделал бы несколько циклов цикла. Таким образом, по сути дела, Q сейчас находится на «n- (k% n)» шагах от BEGINLOOP.

Когда P переместился бы из BEGINLOOP в MEETPOINT, он бы прошел шаги «m-k». (Следовательно, по сути, MEETPOINT будет на «(m-k)% n» шагах впереди BEGINLOOP.) За это время Q прошел бы «2 (m-k)» шагов. Но, так как они встретились, и Q начал «n- (k% n)» шагов позади BEGINLOOP, то есть, фактически, новая позиция Q (которая является (2 (mk) - (nk /% n))% n 'from BEGINLOOP) должен быть равен новой позиции P (которая равна' (mk)% n 'из BEGIN LOOP).

Итак,

=> (2(m - k) - (n - k%n))%n = (m - k)%n
=> (2(m - k) - (n - k%n))%n = m%n - k%n
=> (2(m - k) - (n - Y))%n = m%n - Y   (as k%n = Y)
=> 2m%n - 2k%n - n%n + Y%n = m%n - Y
=> 2m%n - Y - 0 + Y = m%n - Y    (Y%n = Y as Y < n)
=> m%n = 0
=> 'm' should be multiple of 'n'

Есть два способа найти петли в списке ссылок. 1. Используйте два указателя, один шаг вперед, один шаг, а другой шаг вперед, если есть цикл, в какой-то момент оба указателя получают одинаковое значение и никогда не достигают нуля. Но если в одной точке указатель цикла не достигает нуля, и оба указателя никогда не получают одно и то же значение. Но при таком подходе мы можем получить цикл в списке ссылок, но мы не можем сказать, где именно начинается цикл. Это также не эффективный способ.

2. Используйте хеш-функцию таким образом, чтобы значение было уникальным. Incase, если мы пытаемся вставить дубликат, он должен через исключение. Затем пройдитесь по каждому узлу и вставьте адрес в хеш. Если указатель достигает нуля и нет исключений из хеша, это означает, что в списке ссылок нет цикла. Если мы получаем какое-либо исключение из хеша, это означает, что в списке есть цикл, и это ссылка, с которой начинается цикл.

Шаг 1: Действуйте в обычном порядке, вы будете использовать, чтобы найти цикл, т. Е. Иметь два указателя, увеличивая один за один шаг, а другой за два шага, если они оба встретятся через некоторое время, есть цикл.

Шаг 2: Заморозить один указатель там, где он был, и увеличить один указатель за один шаг, подсчитав шаги, которые вы делаете, и когда они оба встретятся снова, счет даст вам длину цикла (это то же самое, что подсчет количества элементов в круговом списке ссылок).

Шаг 3: Сбросить оба указателя на начало списка ссылок, увеличить на один указатель длину цикла, а затем запустить второй указатель. увеличивайте оба указателя за один шаг, и когда они встретятся снова, это будет начало цикла (это то же самое, что найти элемент n ^{th в конце списка ссылок).}