Feb 15, 2021 · 2 min read
Дан указатель на голову списка. Нужно определить есть ли цикл.
Начало цикла искать не нужно, только сам факт.
Решение #
Тривиальное решение — складывать узлы в сет. Можно написать для разминки, но ожидается решение без дополнительной памяти, скорее всего на собеседовании спросят именно его.
Есть известный алгоритм с двумя указателями, который легко пишется, но не все понимают почему это работает. Ожидается, что кандидат даст если не формальное доказательство корректности, то хотя бы некоторые «околоматематические рассуждения».
Именно это я и постарался сделать. Но сперва суть решения с двумя указателями. Заводим «быстрый» и «медленный» указатели на начало списка. Медленный движется на каждый следующий узел, а быстрый — через один. В какой-то момент указатели встречаются если цикл есть, а иначе быстрый указатель дойдёт раньше до конца списка.
var hasCycle = function(head) {
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow.next;
fast = fast.next.next;
if (slow === fast) {
return true;
}
}
return false;
};Итак, почему это работает?
Ключ — в скорости с которой указатели удаляются друг от друга. Давайте рассмотрим пример ниже:
С каждым следующим шагом расстояние между указателями увеличивается на один, верно? Можно посмотреть на эту ситуацию с другой стороны.
Если есть цикл, то быстрый указатель приближается к медленному с другой стороны, как бы нагоняя его. А уже это расстояние уменьшается на один. Ну тогда получается, что в какой-то момент это расстояние станет равным нулю, то есть указатели встретятся.
На самом деле, мы можем пустить медленный указатель прыгать через один узел, а быстрый через два — не важно, главное, чтобы расстояние менялось на один. В таком случае, они точно встретятся.
PS. Обсудить можно в телеграм-чате любознательных программистов. Welcome! 🤗
Подписывайтесь на мой твитер или канал в телеграме, чтобы узнавать о новых разборах задач.