Как найти длину связанного списка, который имеет циклы в ней?
Это было одним из вопросов интервью, которые задают. Как найти длину связанного списка, который имеет цикл в ней. Я знаю, как вычислить, имеет ли связанный список цикл или не использование метод Черепахи и Hare. Я даже знаю, как вычислить длину путем хранения адресов в hashset. Время выполнения Алгоритма должно быть O (n).
Но то, что я не смог сказать, - то, как вычислить длину связанного списка, не используя внешнее пространство O (n).Пожалуйста, помогите мне.Спасибо.
3 ответа
Я думаю, что если вы каким-то образом знаете начальный узел цикла, вы можете узнать длину цикла и, следовательно, общее количество узлов в связанном списке.
Чтобы получить начальную точку, вам нужно всего O (1) пробел.
Предположим, что ваши два указателя, быстрый и медленный, встретились в «узле t».
увеличивают один указатель, чтобы он указывал на следующий узел. , а другой указатель - на начало связанного списка. Теперь увеличивайте оба указателя, пока они не встретятся.
Точка встречи - начальный узел цикла.
Отсюда вы можете получить длину цикла повторным перемещением, так как вы знаете начальную точку цикла.
После обнаружения цикла необходимо вычислить его длину и позицию, с которой он начинается. Их сумма - это общее количество отдельных узлов в списке. Подробности для примера здесь: http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare
- Примените алгоритм Черепаха и Заяц и остановитесь, когда символы встречаются.
- Продолжайте итерацию по списку только с Черепахой и переверните каждую ссылку, которую она пройдет
Количество обратных ссылок - это длина cycle