Tortoise and Hare – O algoritmo de detecção de ciclos de Floyd

O algoritmo Tortoise and Hare (também conhecido como Floyd’s Cycle Detection Algorithm) é uma técnica clássica usada para detectar ciclos em estruturas de dados, como linked lists. Este algoritmo é altamente eficiente, utilizando apenas duas variáveis para resolver problemas que, de outra forma, exigiriam estruturas auxiliares.

O Problema

Imagine que você tem uma lista e precisa responder à seguinte pergunta: “Essa lista possui um ciclo?”

Um ciclo ocorre quando, em vez de terminar em null (ou None), um nó da lista aponta para outro nó já visitado, criando um loop infinito. Detectar esses ciclos é fundamental para evitar bugs em diversos sistemas, como:

Algoritmos que processam listas ligadas ou árvores.
Detecção de loops em grafos direcionados.
Prevenção de loops infinitos em problemas de memória.

Como Funciona o Algoritmo

O algoritmo funciona utilizando dois ponteiros:

Tartaruga (slow pointer): Avança um nó por vez.
Lebre (fast pointer): Avança dois nós por vez.

Princípio básico:

Se não houver um ciclo, o ponteiro rápido eventualmente atingirá o final da lista.
Se houver um ciclo, os dois ponteiros irão se encontrar em algum ponto dentro do ciclo.

Passo a Passo

Inicialize os dois ponteiros, slow e fast, no início da lista.
Avance o ponteiro lento um nó por vez.
Avance o ponteiro rápido dois nós por vez.
Se os ponteiros se encontrarem, significa que existe um ciclo.
Se o ponteiro rápido atingir o final da lista (null), não há ciclo.

Implementação em Python

Abaixo está uma implementação simples e prática:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            return True

    return False

# Exemplo de uso:
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = head.next

print(has_cycle(head))

Complexidade

Tempo: O(n), onde n é o número de nós na lista. Cada nó é visitado no máximo uma vez.
Espaço: O(1), pois o algoritmo usa apenas duas variáveis para os ponteiros.

Aplicações Práticas

Blockchain: Detectar ciclos em cadeias de transações para garantir integridade.
Sistemas operacionais: Identificar dependências circulares em tabelas de alocação.
Problemas matemáticos: Resolver sequências repetitivas, como no problema do número feliz (Happy Number).
Encontrar duplicatas em arrays de forma eficiente

Por que “Tortoise and Hare”?

O nome do algoritmo vem da analogia com uma corrida entre uma tartaruga e uma lebre: enquanto a tartaruga avança devagar (um passo por vez), a lebre avança rápido (dois passos por vez). Eventualmente, em um percurso circular, a lebre alcança a tartaruga.

Conclusão

O algoritmo Tortoise and Hare é uma solução eficiente e elegante para a detecção de ciclos em listas ligadas e outros problemas semelhantes. Sua simplicidade e eficácia o tornam uma ferramenta indispensável para desenvolvedores que lidam com estruturas de dados dinâmicas. Experimente implementá-lo e veja como ele pode facilitar a solução de problemas complexos!