Псевдо логика для Обнаружения цикла в Единственном связанном списке

Question

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

узел_1 -> узел_2 -> узел_3 -> узел_4 -> узел_5 -> узел_3

Я хочу определить, существует ли цикл для какого-либо заданного связанного списка, принимая во внимание фактор производительности.

Answer 1

Инициализировать хеш.Переберите список.Для каждого узла, если он уже находится в хэше, верните LOOP.В противном случае добавьте его в хеш.Когда будет достигнут конец списка, верните NO_LOOP.

Примечание: вам не нужно помещать весь узел в хеш.Достаточно идентификатора или чего-то еще, что уникально идентифицирует узел.

Answer 2

function boolean hasLoop(Node startNode){
      Node slowNode = Node fastNode = startNode;
      while(true){
          if(slowNode)
             return false;
          else if(((slowNode==fastNode)&&fastNode!=startNode)||fastNode->next==slowNode)
              return true;
          else{
              slowNode=slowNode->next;
              fastNode=fastNode->next->next;
          }
      }
    }