TOP 25 ALGORITMOS | Floyd’s Cycle Finding Array

#Estrutura de dados

É um algoritmo de ponteiro que usa apenas dois ponteiros, movendo-se pela sequência em velocidades diferentes. Este algoritmo é usado para encontrar um loop em uma lista encadeada. Ele usa dois ponteiros, um movendo-se duas vezes mais rápido que o outro. O mais rápido é chamado de ponteiro rápido e o outro é chamado de ponteiro lento.

📁 | Resumo

🤖 | Código

.
class Node {
  constructor(x) {
      this.data = x;
      this.next = null;
  }
}

// Função que retorna true se houver um loop em lista encadeada senão retorna false.
function detectLoop(head) {

  // Ponteiros rápidos e lentos apontam inicialmente para cabeça
  let slow = head, fast = head;

  // Loop que é executado enquanto os ponteiros rápido e lento estão não é nulo e não é igual
  while (slow !== null && fast !== null
         && fast.next !== null) {
      slow = slow.next;
      fast = fast.next.next;

      // Se o ponteiro rápido e lento apontar para o mesmo nó, então o ciclo é detectado
      if (slow === fast) {
          return true;
      }
  }
  return false;
}

// Crie uma lista linkada: 10 -> 20 -> 30 -> 40 -> 50 -> 60
let head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(50);
head.next.next.next.next.next = new Node(60);

head.next.next.next.next = head;

if (detectLoop(head))
  console.log("true");
else
  console.log("false");
.

🕰️ | Complexidade de Tempo

Como depende do número de nós, a complexidade de tempo será O(n).

📦 | Complexidade de Espaço

Como NÃO há necessidade de espaço temporário auxiliar, a complexidade de espaço será O(1).

✔️ | Vantagens

✦ Eficiente;

❌ | Desvantagens

✦ Nada intuitivo e nada fácil de implementar;