Алгоритм обнаружения циклически связанных списков

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

Увеличение первого медленного указателя на 1 имеет смысл, так что мы итерируем все элементы, которые мы будем сравнивать со вторым указателем. НО ПОЧЕМУ БЫСТРЫЙ УКАЗАТЕЛЬ НЕОБХОДИМО БЫТЬ ПРЕДУСМОТРЕН ТОЛЬКО НА 2. Почему мы можем увеличивать его на 3 или 4 или более ????

И есть способ рассчитать, что должно быть «нет». из хэп (если не 2) более быстрого указателя по отношению к количеству элементов в списке ???

источник

2012-06-15 Vince

возможно дубликат [Зачем увеличивать указатель на два Находя цикла в связанном списке, почему нет 3,4,5?] (http://stackoverflow.com/questions/5130246/why-increase-pointer-by-two-while-finding-loop-in-linked-list-why- not-3-4-5) – templatetypedef

Кроме того, не используйте ОЧЕНЬ ГРОМКОГО ВЕРХНЕЙ ЧАСТИ ПИСЬМА В ВАШЕМ ОТВЕТЕ ИЛИ ПОВТОРЕННОМ УРОВНЕ !!! Он читает, как будто вы кричите на нас. Для акцента лучше использовать * курсив * или ** жирный **, чтобы привлечь внимание. – templatetypedef

Вопрос должен быть исправлен. Более быстрый указатель используется для определения цикла в связанном списке, а не для определения того, является ли список круговым или нет.Разница в том, что в круговом списке последний узел всегда указывает на голову. В тех случаях, когда цикл может указывать на любой промежуточный узел – fayyazkl

Вы можете использовать 3, 4 или все, что хотите, но это самый быстрый способ с 2, потому что предположим, что вы находитесь в цикле с шагом 2 в первый раз :(D - указатель, который идет 2 шага, а S - обычный указатель.
Случай 1)

step 1 :x - D - x - S - x - x ... 
step 2 :x - x - x - D - S - x ... 
step 3 :x - x - x - x - x - SD (match)

Случай 2)

step 1: x - D - S - x this is the step 2 from case 1 and we can see that this is step 2 and we also have a match

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

Случай 1)

step 1 : x - D - x - x - S ... 
    step 2 : x - x - x - x - D - S ... 
    step 3 : x - x - x - x - x - x - S - D ... (D is passing S and it needs at least another loop to meet S)

Случай 2)

step 1 : x - D - x - S -.. 
step 2 : x - x - x - x - SD (match)

случай 3)

step 1: x - D - S - .. 
step 2: x - x - x - S - D ... (D is passing S and it needs at least another loop to meet S)

И из-за того, что 2 лучше, чем 3, 4 или все, что вы хотите, потому что все числа, превышающие 2, имеют шанс встретиться 1/(N-1) в первый раз.
Другой способ объяснить это: для D и S и шаг N, если расстояние между S и D равно N - 1, мы имеем совпадение (D идет N шагов и шаг S 1 и D = S), другой путь D проходит через S, поэтому мы имеем шанс 1/(N-1) встретить S и D в первый раз, и из-за этого, если N = 2, мы имеем 1/1 = 100%, если N = 3, мы имеем 1/2 = 50%.
Надеюсь, это помогло.

источник

2012-06-15 11:12:42 Mark

2, не обязательно является «самым быстрым» размером шага. Как быстро встречаются указатели, зависит не только от размера шага, но и от длины цикла. Может случиться так, что с шагом size = 4 и длиной цикла = 3 «быстрый» указатель станет равным «медленному» указателю сразу после одной итерации. Но, конечно, более длительные шаги требуют дополнительного времени. –

Если вы используете 3 или 4 в качестве размера шага, вам нужно добавить проверки для всех особых случаев, когда продвижение по 3 может привести к нулевому значению первого или второго узла.

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

Это просто больше кода, больше условий для обработки, ошибкам и выглядит менее элегантно, чтобы использовать более чем в 2 раза без увеличения производительности с точки зрения Big O

источник

2012-06-18 07:20:07 fayyazkl

Алгоритм обнаружения циклически связанных списков

ответ

Смежные вопросы