Обнаружение начала петли в списке ссылок на отдельные ссылки?
https://stackoverflow.com/questions/1536944
-
20-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Есть ли способ узнать начало цикла в списке ссылок, используя Не более двух указателей?Я не хочу посещать каждый узел и отмечать его и сообщать о первом узеле, уже увиденном. Есть ли другой способ сделать это?
Решение
Я слышал этот точный вопрос как вопрос интервью.
Самое элегантное решение - это:
Поместите оба указателя в первый элемент (назовите их A и B)
Затем продолжайте цикл ::
- Перенеситесь к следующему элементу
- Снова перейти к следующему элементу
- Продвигать B к следующему элементу
Если вы хотите найти элемент, в котором указаны два указателя, это сложнее. Я бы вышел из конечности и сказал, что невозможно сделать только с двумя указателями, если вы не готовы повторить следуя связанного списка большим количеством раз.
Наиболее эффективный способ сделать это с большим количеством памяти - поместить указатели на элементы в массивах, сортировать его, а затем искать повтор.
Другие советы
Шаг 1: Продолжайте обычным способом, вы будете использовать для поиска петли, т.е. есть два указателя, увеличить один на одном шаге, а другой - на два шага, если они оба встречаются через некоторое время, есть цикл.
Шаг 2: Заморозить один указатель, где он находился, и увеличивает другой указатель на один шаг, подсчитывая шаги, которые вы делаете, и когда они оба снова встретятся, счет даст вам длину цикла (это то же самое, что подсчет количества элементов в круговой ссылке список).
Шаг 3: Сбросьте оба указателя на начало списка ссылок, увеличьте один указатель на длину времени цикла, а затем запустите второй указатель. Увеличьте оба указателя за один шаг, и когда они снова встретятся, это станет началом петли (это то же самое, что найти Nтурнир Элемент из конца списка ссылок).
Математическое доказательство + решение
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-это «NK» шаги позади Beginloop сейчас.
Когда P переехал бы из Begnloop в MeetPont, он прошел бы «MK» шаги. За это время Q прошел бы 2 (Mk) 'шаги. Но, поскольку они встретились, и Q начал «nk» шаги позади начала, так что, эффективно, '2 (mk) - (nk)' должен быть равен '(mk)', так что,
=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m
Это означает, что P и Q встречаются в точке, равном количеству шагов (или множественным, чтобы быть общим, см. Случай, упомянутый ниже) в цикле. Теперь, в The Meetpoint, как P, так и Q представляют собой шаги «n- (mk)» позади, т.е. «K», шаги позади, как мы видели n = m. Итак, если мы снова начнем с заголовка, и Q с точки встречи, но на этот раз с темпом, равным P, P и Q, теперь будут встречаться только в Beartloop.
Общий случай: скажем, k = nx + y, y <n <n(Следовательно, k%n = y)
Когда указатель 'P' будет в Beginloop (то есть он бы путешествовал «k»), Q прошел бы «2k» шаги. Таким образом, фактически Q опережает '2k-k = k' шаги от P, когда P входит в петлю. Но обратите внимание, что «K» больше, чем «n», что означает, что Q сделал бы несколько раундов петли. Таким образом, фактически, Q-это «n- (k%n)» шаги позади Beginloop сейчас.
Когда P переехал бы из Begnloop, чтобы встретиться с точки зрения, он бы прошел шаги «MK». (Следовательно, фактически, MeetPoint будет на «(Mk)%N 'шагах впереди BeginLoop сейчас.) В это время Q проходил бы« 2 (Mk) »шаги. Но, поскольку они встретились, и Q запустил «n- (k%n)» шаги позади начала, так что, фактически, новая позиция q (что является '(2 (mk) - (nk/%n))%n 'от beginloop) должен быть равен новой позиции p (что является' (mk)%n 'от begong 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'
Сначала мы пытаемся выяснить, есть ли в списке или нет. Если петля существует, мы пытаемся выяснить отправную точку петли. Для этого мы используем два указателя, а именно 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.
Продолжайте обычным способом, который вы будете использовать, чтобы найти петлю. т.е. Имейте два указателя, увеличение одного на одном шаге (медленная установка) и другие на два шага (Fast -Pointer), если они оба встречаются через некоторое время, есть цикл.
Как бы вы могли бы уже понять, что точка встречи - это k шаг перед главой петли.
где k-это размер не-контукой части списка.
Теперь двигайтесь медленно к головой петли
Сохраняйте быстро в точке столкновения
Каждый из них находится на шаге от начала петли (медленно от начала списка, где быстро k шаг перед головой петли- нарисуйте картинку, чтобы получить ясность)
Теперь перемещайте их с той же скоростью - они должны встретиться при старте петли
например
slow=head
while (slow!=fast)
{
slow=slow.next;
fast=fast.next;
}
Это код, чтобы найти начало цикла в Linded List:
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);
}
Есть два способа найти петли в списке ссылок. 1. Используйте два указателя One Advance One Step, а другие продвигайте два шага, если есть цикл, в какой -то точке оба указателя получают одинаковое значение и никогда не достигают нулевого. Но если в одной точке нет указателя петли, и оба указателя никогда не получают одинакового значения. Но при таком подходе мы можем получить туда, есть цикл в списке ссылок, но мы не можем сказать, где точно запустить цикл. Это также не эффективный способ.
- Используйте хэш -функцию таким образом, чтобы значение было уникальным. Если мы пытаемся вставить дубликат, он должен через исключение. Затем пройдите через каждый узел и протолкните адрес в хэш. Если указатель достигнет нулевого и никакого исключения из хэша означает, что в списке ссылок нет цикла. Если мы получаем какое -либо исключение от хэша, означает, что в списке есть цикл, и это ссылка, с которой начинается цикл.
Что ж, я попробовал путь, используя один указатель ... Я попробовал метод в нескольких наборах данных ... так как память для каждого из узлов связанного списка выделяется в порядке возрастания, поэтому при пересечении связанного списка из Глава связанного списка, если адрес узла становится больше, чем адрес узела, на который он указывает, мы можем определить, что есть цикл, а также начальный элемент цикла.
Лучший ответ, который я нашел, был здесь:
Tianrunhe: Lyplop-Panting-Point-A-A-Circular-Link-List
- 'M' - расстояние между головой и start_loop
- 'L' Длина петли
- 'D' Расстояние между Meeting_point и start_loop
P1 движется в V, а P2 движется при 2*V
Когда 2 указателя встречаются: прогон расстояния = m+ n*l -d = 2*(m+ l -d)
=> Что означает (не математическая продемонстрирована здесь), что, если P1 начнет с головы и P2, начинается с Meating_point, и они движутся в том же темпе, они встретятся с @ start_loop
Ссылаться на это Ссылка для комплексного ответа.
Продолжайте обычным способом, который вы будете использовать, чтобы найти петлю. т.е. Иметь два указателя, увеличить один на одном шаге, а другой - на два шага, если они оба встречаются через некоторое время, есть петля.
Держите один из указателей фиксированных Получите общее количество узлов в цикле, скажем, L.
Теперь с этого момента (увеличивает второй указатель на следующий узел в цикле) в цикле. Обратите внимание на связанный список и подсчитывайте количество пройденных узлов, скажем, x.
Теперь используя второй указатель (петля сломана) из той той точки в цикле Travrse Связанный список и подсчитайте количество оставшихся узлов, скажем, Y
Цикл начинается после ((x+y) -l) 2 узлов. Или он начинается в (((x+y) -l) 2+1) th node.
Продолжайте обычным способом, который вы будете использовать, чтобы найти петлю. т.е. Иметь два указателя, увеличить один на одном шаге, а другой - на два шага, если они оба встречаются через некоторое время, есть петля.
Держите один из указателей фиксированных Получите общее количество узлов в цикле, скажем, L.
Теперь с этого момента (увеличивает второй указатель на следующий узел в цикле) в цикле. Обратите внимание на связанный список и подсчитывайте количество пройденных узлов, скажем, x.
Теперь используя второй указатель (петля сломана) из той той точки в цикле Travrse Связанный список и подсчитайте количество оставшихся узлов, скажем, Y
Цикл начинается после ((x+y) -l) 2 узлов. Или он начинается в (((x+y) -l) 2+1) th node.
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);
}
- Обнаружение петли
- Скопируйте адрес каждого элемента в набор. Если найден дубликат, это начало петли
