Linked List Cycle

Дан указатель на голову списка. Нужно определить есть ли цикл.

Начало цикла искать не нужно, только сам факт.

Решение #

Тривиальное решение — складывать узлы в сет. Можно написать для разминки, но ожидается решение без дополнительной памяти, скорее всего на собеседовании спросят именно его.

Есть известный алгоритм с двумя указателями, который легко пишется, но не все понимают почему это работает. Ожидается, что кандидат даст если не формальное доказательство корректности, то хотя бы некоторые «околоматематические рассуждения».

Именно это я и постарался сделать. Но сперва суть решения с двумя указателями. Заводим «быстрый» и «медленный» указатели на начало списка. Медленный движется на каждый следующий узел, а быстрый — через один. В какой-то момент указатели встречаются если цикл есть, а иначе быстрый указатель дойдёт раньше до конца списка.

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! 🤗

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