Как найти длину связанного списка, в котором есть циклы?

Question

Это был один из заданных вопросов на собеседовании. Как найти длину связанного списка, в котором есть цикл. Я знаю, как рассчитать, есть ли в связанном списке цикл или нет, используя технику Заяц и Черепаха. Я даже знаю, как рассчитать длину, сохраняя адреса в хэш-сет. Время работы алгоритма должно быть O (n).

Но я не смог сказать, как рассчитать длину связанного списка без использования внешнего пространства O (n). Пожалуйста, помогите мне. Спасибо.

Answer 1

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

Для получения начальной точки вам нужен только O (1) пробел.

Предположим, ваши два указателя, быстрый и медленный, встречаются в «узле t».

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

Место встречи является начальным узлом цикла.

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

Answer 2

После того, как вы обнаружили цикл, вам нужно вычислить длину цикла и позицию, в которой он начинается. Их сумма равна общему количеству отдельных узлов в списке. Подробности, например, здесь: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare

Answer 3

1. Применить Алгоритм черепахи и зайца и остановиться, когда персонажи встретятся
2. Продолжайте итерацию по списку только с черепахой и переворачивайте каждую ссылку, которую он пройдет

Количество обратных ссылок - это длина цикла

Answer 4

Вот математическое обоснование правильности популярного алгоритма зайца и черепахи для определения длины связанного списка.

Answer 5

Определить точку петли По (Подход медленного и быстрого указателя) найти узел обнаружения петель

Теперь возьмите указатели P1 и P2, P1 в узле обнаружения петель и P2, начиная с заголовка связанного списка Пройдите по обоим указателям по одному

Оба указателя встречаются в узле, из-за чего в связанном списке есть петля

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

Взять два указателя P1 и P2 в точке обнаружения петли. Поместите указатель P1 в то же место и переместите P2 вперед на один шаг за раз. Повторяйте, пока оба указателя не встретятся вместе. Сохраняйте переменную count для каждой итерации, которая дает длину цикла. Допустим, длина L1

Снова возьмите два указателя P1 и P2. P1 в начале связанного списка и P2 в точке обнаружения петли. Перемещайте оба указателя по одному шагу за раз. Повторяйте, пока оба указателя не встретятся вместе. Эта процедура эквивалентна той, которую мы используем для вычисления узла, который вызывает цикл в связанном списке. Сохраняйте переменную count для каждой итерации равной длине списка до точки слияния. Допустим, длина L2 Теперь длина списка, содержащего цикл, равна L1 + L2

.

Answer 6

не пойдет ли в бесконечный цикл? если 1 2 3 ... 9 10 образуют цикл, который начинается с 1. Предположим, когда указатель от начального узла достигает 1, другой указатель находится на узле 8. Затем они перемещаются как указатель1: - 1 2 3 4 5 .. указатель2: - 8 9 10 1 2 .. ясно, что они никогда не будут равны.