Не могли бы вы объяснить, как работает приведенный ниже фрагмент для поиска цикла в связанном списке?

Question

Этот код предназначен для поиска цикла в одном связанном списке, и я узнал об этом из http://blog.ostermiller.org/find-loop-singly-linked-list, но не мог понять, почему код написан так, как он был написан.

Это решение было разработано Стивеном Остермиллером и доказано O (n) Даниэлем Мартином.

function boolean hasLoop(Node startNode){
  Node currentNode = startNode;
  Node checkNode = null;
  int since = 0;
  int sinceScale = 2;
  do {
    if (checkNode == currentNode) return true;
    if (since >= sinceScale){
        checkNode = currentNode;
        since = 0;
        sinceScale = 2*sinceScale;
    }
    since++;
  } while (currentNode = currentNode.next());
  return false;
}

Наконец это также было упомянуто:

Это решениеO (n), потому что Scale растет линейно с количеством вызовов функции next ().Поскольку Scale больше размера цикла, для обнаружения цикла может потребоваться еще n вызовов функции next ().

Answer 1

Это алгоритм поиска цикла Брента.https://en.wikipedia.org/wiki/Cycle_detection#Brent%27s_algorithm

Мне нравится больше, чем алгоритм Флойда для большинства целей.Это действительно работает за O (N) время:

• Требуется O (N) шагов, чтобы получить currentNode в циклической части списка.
• ЗатемO (N) больше шагов до since == sinceScale, а checkNode установлено на currentNode
• С этого момента checkNode и currentNode оба находятся в цикле,Когда sinceScale становится больше, частота, с которой checkNode сбрасывается, уменьшается.Когда он достаточно большой, checkNode будет оставаться постоянным до тех пор, пока currentNode не пройдет весь цикл и не будет обнаружен цикл.Масштабирование sinceScale на 2 каждый раз гарантирует, что это также происходит в O (N).

Для поиска циклов в связанном списке, либо алгоритм Флойда, либо алгоритм Брента работают нормально, но алгоритм Брентаудобнее во многих реальных ситуациях, когда переход из текущего состояния в следующее состояние дорог, и было бы нецелесообразно перемещать второй «медленный» указатель, который требует алгоритм Флойда.