Hoje vamos explorar um problema clássico em estruturas de dados: identificar a existência de ciclos em listas ligadas e determinar o ponto de início desses ciclos.

Existem duas abordagens principais para resolver este desafio: uma utilizando um algoritmo matemático conhecido como algoritmo de Floyd (também chamado de "tartaruga e lebre"), e outra utilizando uma tabela de dispersão (hash table).

Vamos começar pela abordagem matemática, que é mais eficiente em termos de espaço.

Abordagem do Algoritmo de Floyd

O princípio por trás deste algoritmo é utilizar dois ponteiros que percorrem a lista em velocidades diferentes. Um ponteiro (lento) avança um nó por vez, enquanto o outro (rápido) avança dois nós por vez.

Se a lista contém um ciclo, esses dois ponteiros eventualmente se encontrarão dentro do ciclo. Para encontrar o ponto de início do ciclo, após a detecção do encontro, posicionamos um ponteiro no início da lista e movemos ambos os ponteiros um nó por vez até se encontrarem novamente.

A matemática por trás disso é fascinante:

• Seja x a distância do início da lista ao ponto de entrada do ciclo
• Seja y a distância do ponto de entrada do ciclo ao ponto de encontro
• Seja z a distância do ponto de encontro ao ponto de entrada do ciclo (completando o ciclo)

Quando os ponteiros se encontram:

• O ponteiro lento percorreu x + y nós
• O ponteiro rápido percorreu x + y + n(y + z) nós, onde n é o número de ciclos completados pelo ponteiro rápido

Como o ponteiro rápido se move duas vezes mais rápido que o ponteiro lento, temos:

2(x + y) = x + y + n(y + z)
x = (n - 1)(y + z) + z

Isso mostra que a distância do início da lista ao ponto de entrada do ciclo (x) é igual à distância do ponto de encontro ao ponto de entrada do ciclo (z) mais múltiplos do comprimento do ciclo.

A implementação em C++:

class Solucao {
public:
    NoLista* detectarCiclo(NoLista* cabeca) {
        if (cabeca == nullptr || cabeca->proximo == nullptr) {
            return nullptr;
        }
        
        NoLista* ponteiroLento = cabeca;
        NoLista* ponteiroRapido = cabeca;
        
        // Detectar ciclo
        do {
            ponteiroLento = ponteiroLento->proximo;
            ponteiroRapido = ponteiroRapido->proximo->proximo;
        } while (ponteiroRapido != nullptr && ponteiroRento != ponteiroLento);
        
        // Se não houver ciclo, retornar nulo
        if (ponteiroRapido == nullptr) {
            return nullptr;
        }
        
        // Encontrar o ponto de entrada do ciclo
        NoLista* inicio = cabeca;
        while (inicio != ponteiroLento) {
            inicio = inicio->proximo;
            ponteiroLento = ponteiroLento->proximo;
        }
        
        return inicio;
    }
};

Abordagem com Tabela de Dispersão

A segunda abordagem é mais simples de entender, embora utilize mais espaço. A ideia é percorrer a lista enquanto armazenamos cada nó visitado em uma tabela de dispersão.

Se durante a travessia encontramos um nó que já está na tabela, identificamos um ciclo e esse nó é o ponto de início do ciclo.

A implementação em C++:

class Solucao {
public:
    NoLista* detectarCiclo(NoLista* cabeca) {
        // Criar uma tabela de dispersão para armazenar nós visitados
        unordered_set<NoLista*> nosVisitados;
        
        // Percorrer a lista
        while (cabeca != nullptr) {
            // Verificar se o nó atual já foi visitado
            if (nosVisitados.find(cabeca) != nosVisitados.end()) {
                return cabeca; // Encontrado o início do ciclo
            }
            
            // Adicionar o nó atual à tabela de dispersão
            nosVisitados.insert(cabeca);
            
            // Mover para o próximo nó
            cabeca = cabeca->proximo;
        }
        
        // Se não houver ciclo, retornar nulo
        return nullptr;
    }
};

Ambas as abordagens são eficazes, mas a primeira é mais eficiente em termos de espaço (complexidade de espaço O(1)), enquanto a segunda é mais simples de implementar e entender (complexidade de tempo O(n)).