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

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

Ответ 1

Я слышал этот точный вопрос в качестве вопроса опроса интервью.

Самое элегантное решение:

Поместите оба указателя в первый элемент (назовите их A и B)

Затем продолжайте цикл:

Переход к следующему элементу
Перейти к следующему элементу снова
Передвинуть B к следующему элементу

Каждый раз, когда вы обновляете указатель, проверяйте идентичность A и B. Если в какой-то момент указатели А и В идентичны, то у вас есть петля. Проблема с этим подходом состоит в том, что вы можете в конечном итоге перемещаться по циклу дважды, но не более чем дважды с указателем A

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

Самый эффективный способ сделать это с большим объемом памяти - это указать указатели на элементы в и массиве, отсортировать их, а затем искать повторение.

Ответ 2

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

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

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

Ответ 3

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

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

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

ЭТО СРЕДА, P и Q встречаются в точке, равной количеству шагов (или нескольких, чтобы быть общим, см. случай, упомянутый ниже) в цикле. Теперь, в MEETPOINT, оба 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 'от 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'

Ответ 4

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

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

Ответ 5

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

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

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

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

сохранить Fast в точке столкновения

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

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

например,

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

Ответ 6

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

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

Ответ 7

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

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

Ответ 8

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

Ответ 9

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

Ответ 10

Продолжайте обычным способом, чтобы использовать цикл. то есть. Имейте два указателя, увеличивайте один за один шаг и прочее за два шага. Если они когда-нибудь встречаются, есть цикл.
Держите один из указателей фиксированным, получите общее количество узлов в цикле, скажем L.
Теперь с этой точки (приращиваем второй указатель на следующий node в цикле) в цикле обратный связанный список и подсчитываем количество пройденных узлов, например X.
Теперь, используя второй указатель (цикл разбит) из той же точки в цикле travrse связанный список и подсчитайте количество оставшихся узлов, скажем, Y
Цикл начинается после узлов ((X + Y) -L)\2. Или он начинается с (((X + Y) -L)\2 + 1) th node.

Ответ 11

Продолжайте обычным способом, чтобы использовать цикл. то есть. У вас есть два указателя, увеличивайте один за один шаг и прочее за два шага. Если они встречаются в какой-то момент, есть цикл.
Держите один из указателей фиксированным, получите общее количество узлов в цикле, скажем L.
Теперь с этой точки (приращиваем второй указатель на следующий node в цикле) в цикле обратный связанный список и подсчитываем количество пройденных узлов, например X.
Теперь, используя второй указатель (цикл разбит) из той же точки в цикле travrse связанный список и подсчитайте количество оставшихся узлов, скажем, Y
Цикл начинается после узлов ((X + Y) -L)\2. Или он начинается с (((X + Y) -L)\2 + 1) th node.

Ответ 12

Лучший ответ, который я нашел, был здесь:
tianrunhe: find-loop-start-point-in-a-round-linked-list

'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

Ответ 13

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

Ответ 14

обнаружение цикла
копировать каждый элемент в набор. Если обнаружен дубликат, что начало цикла