Padrão 3: Ponteiros lento e rápido
Dois ponteiros que andam pela lista em velocidades diferentes revelam coisas surpreendentes: o meio da lista numa passada só, e se existe um ciclo — sem usar nenhuma memória extra.
Tente primeiro: Middle of the Linked List
Antes de ler a teoria, tente resolver. Pode começar pela força bruta, pode errar — a ideia é sentir o problema. A teoria vem logo abaixo.
Retorne o nó do meio de uma lista ligada (a partir dele até o fim). Se houver dois nós no meio, retorne o segundo.
Exemplo: 1 → 2 → 3 → 4 → 5 → meio é 3 (retorna 3 → 4 → 5). 1 → 2 → 3 → 4 → 5 → 6 → retorna 4 → 5 → 6.
Tentou? Dá para contar o tamanho e andar metade — duas passadas. A teoria abaixo faz numa passada só, com uma ideia que rende muito mais que achar o meio.
A teoria: velocidades diferentes
A ideia (também chamada "tartaruga e lebre"): dois ponteiros partem da cabeça,
mas fast anda dois nós por vez enquanto slow anda um.
slow: +1 por passo
fast: +2 por passo
Como fast cobre o dobro do caminho, quando ele chega ao fim, slow
cobriu exatamente metade — ou seja, está no meio. Uma passada, sem
contar nada antes:
(Com número par de nós, este código devolve o segundo dos dois nós do meio — combine a condição do laço conforme o enunciado pedir o primeiro ou o segundo.)
Por que é O(n) tempo e O(1) espaço?
fast percorre a lista uma vez (em passos de 2), então o laço roda ~n/2 vezes,
cada uma O(1) → O(n) de tempo. Dois ponteiros, nenhuma estrutura extra →
O(1) de espaço. A alternativa "contar e andar metade" é O(n) também, mas
faz duas passadas.
O grande truque: detecção de ciclo (Floyd)
E se a lista tiver um ciclo (algum next aponta para um nó anterior)? Um
laço while curr percorreria para sempre. Como detectar sem marcar nós nem
usar um conjunto (que custaria O(n) de memória)?
A sacada de Floyd: solte a tartaruga (slow, +1) e a lebre (fast, +2)
na pista. Se a pista é uma reta (sem ciclo), a lebre chega ao fim (None)
e acabou. Se a pista é circular, a lebre dá voltas e, cedo ou tarde,
alcança a tartaruga por trás — porque a cada passo a distância entre elas
diminui de 1. Se fast == slow em algum momento, há um ciclo.
Por que Floyd funciona (e é O(1) de espaço)
Se há ciclo, uma vez que as duas estão dentro dele, a cada passo a lebre se
aproxima da tartaruga em 1 posição (anda 2, ela anda 1). A distância só
diminui, então em no máximo "tamanho do ciclo" passos elas se encontram. Se
não há ciclo, a lebre alcança o None e o laço termina. Custa O(n) de
tempo e O(1) de espaço — a alternativa óbvia (guardar nós já vistos num
set) também é O(n) de tempo, mas gasta O(n) de memória. Floyd não gasta nenhuma.
Onde lento/rápido aparece
- Meio da lista (e daí: dividir a lista ao meio — base do merge sort em lista e do reorder).
- Detecção de ciclo e, num passo extra, achar onde o ciclo começa.
- N-ésimo a partir do fim (o gap fixo da aula anterior é um primo deste padrão).
🧠 Quiz de fixação
0/41. Por que, quando fast (passo 2) chega ao fim, slow (passo 1) está no meio?
2. Na detecção de ciclo de Floyd, por que slow e fast acabam se encontrando se há um ciclo?
3. Por que Floyd é preferível a guardar os nós visitados num conjunto (set)?
4. Como detectar ciclo num laço 'while fast and fast.next' garante terminação quando NÃO há ciclo?
Resumo
- Lento/rápido: fast anda 2, slow anda 1 → slow para no meio quando fast acaba. Uma passada, O(n)/O(1).
- Floyd (ciclo): se há ciclo, a lebre alcança a tartaruga; se não, a lebre acha o fim. O(n)/O(1), sem set.
- Base para dividir a lista, achar início do ciclo e "n-ésimo do fim".
Próxima aula: juntar duas listas ordenadas — merge.