Обнаружение начала цикла в списке односвязных ссылок?

Question

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

Answer 1

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

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

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

Answer 2

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

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

Когда указатель «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 начал 'n-k' шаги позади BEGINLOOP, так что, эффективно, '2 (m-k) - (n-k)' должно быть равно '(m-k)' Итак,

=> 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 (Следовательно, 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'

Answer 3

Сначала мы попытаемся выяснить, есть ли петля в списке или нет. Если цикл существует, то мы пытаемся выяснить начальную точку цикла. Для этого мы используем два указателя, а именно 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.

Подробнее здесь

Answer 4

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

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

Answer 5

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

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

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

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

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

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

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

например

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

Answer 6

Лучший ответ, который я нашел, был здесь:
tianrunhe: начальная точка поиска цикла в круговом связанном списке

• 'm' - расстояние между HEAD и START_LOOP
• 'L' - длина петли
• 'd' - расстояние между MEETING_POINT и START_LOOP

• p1 движется при V, а p2 движется при 2 * V

  когда встречаются 2 указателя: пробег = m + n * L -d = 2 * (m + L -d)

  => что означает (математика здесь не показана), что если p1 начинается с HEAD, а p2 начинается с MEETING_POINT и они движутся с одинаковой скоростью, они встретятся с @ START_LOOP

Answer 7

Обратитесь к этой ссылке для полного ответа.

Answer 8

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

Answer 9

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

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

Answer 10

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