Detecção de Ciclos com o Algoritmo de Floyd
Detecte ciclos usando ponteiros lento e rápido, encontre o ponto de entrada do ciclo e prove matematicamente a correção do algoritmo.
Detecção de Ciclos com o Algoritmo de Floyd é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Coding Interview Prep, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Coding Interview Prep inclui 4 aulas no total.
O que é um Ciclo em uma Lista Encadeada?
Um ciclo em uma lista encadeada ocorre quando o ponteiro next de um nó aponta de volta para um nó visitado anteriormente, criando um laço infinito. Percorrer uma lista desse tipo com um laço while head faria a execução continuar para sempre. A detecção de ciclos é um problema clássico de entrevistas e a base de algoritmos de ponteiros mais avançados.
A abordagem ingênua armazena cada nó visitado em um conjunto e verifica se ele pertence ao conjunto — tempo O(n), espaço O(n). O algoritmo de Floyd resolve o mesmo problema em tempo O(n) e espaço O(1), que é o que os entrevistadores esperam.
Algoritmo de Ponteiros Lento e Rápido de Floyd
A detecção de ciclos de Floyd (a «tartaruga e a lebre») usa dois ponteiros: o ponteiro lento avança uma etapa por vez, enquanto o rápido avança duas. Se não existir um ciclo, o ponteiro rápido alcançará o valor nulo primeiro. Se existir um ciclo, o ponteiro rápido eventualmente alcançará o lento dentro do ciclo, e ambos se encontrarão no mesmo nó. Esse encontro prova que existe um ciclo.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
# Build: 3 -> 2 -> 0 -> -4 -> (back to 2)
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1] # cycle: -4 -> 2
print(hasCycle(nodes[0])) # TruePor que os Ponteiros Lento e Rápido Sempre se Encontram
De modo informal: depois que ambos os ponteiros entram no ciclo, a distância entre eles muda em 1 a cada passo (o ponteiro rápido ganha 2, o lento ganha 1, então a diferença diminui em 1 a cada rodada). Por fim, a diferença chega a 0 — eles estão no mesmo nó. De modo mais formal, se o ciclo tiver comprimento C, a diferença máxima dentro dele será C-1, e a diferença diminuirá em 1 a cada passo; portanto, eles se encontrarão em até C passos depois que ambos entrarem no ciclo.
Total de passos antes do encontro: no máximo O(n + C) = O(n), pois C <= n.
# Visualise convergence: simulate gap in cycle
cycle_length = 5
for start_gap in range(1, cycle_length + 1):
gap = start_gap
steps = 0
while gap != 0:
gap = (gap - 1) % cycle_length
steps += 1
print(f'Start gap {start_gap}: meet after {steps} step(s)')Encontrando o Ponto de Entrada do Ciclo
Depois de detectar um ciclo, o algoritmo de Floyd também pode encontrar o nó de entrada (onde o ciclo começa). Depois que os ponteiros lento e rápido se encontrarem dentro do ciclo, reposicione um ponteiro no início e mantenha o outro no ponto de encontro. Em seguida, avance ambos uma etapa por vez. Eles se encontrarão exatamente no nó de entrada do ciclo. Isso funciona porque a distância do início até a entrada é igual à distância do ponto de encontro até a entrada (módulo o comprimento do ciclo).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detectCycle(head):
slow = fast = head
# Phase 1: detect meeting point
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # no cycle
# Phase 2: find entry
pointer = head
while pointer is not slow:
pointer = pointer.next
slow = slow.next
return pointer # cycle entry node
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1] # entry is nodes[1] (val=2)
entry = detectCycle(nodes[0])
print(entry.val) # 2Prova Matemática do Nó de Entrada
Seja F = distância do início até a entrada do ciclo, C = comprimento do ciclo e a = distância da entrada até o ponto de encontro dentro do ciclo. Quando se encontram: o ponteiro lento percorreu F + a passos; o ponteiro rápido percorreu F + a + n*C passos (n voltas completas à frente). Como rápido = 2 * lento: 2(F+a) = F+a+nC → F = nC - a. Isso significa que a distância do início até a entrada é igual à distância do ponto de encontro até a entrada (módulo C). Reposicionar um ponteiro no início e avançar ambos em 1 faz com que eles convirjam no nó de entrada.
# Verify with our example: F=1 (head to node 2), C=3 (cycle: 2->0->-4->2), a=?
# Meeting inside cycle after F+a slow steps
# Let us measure a by counting from entry to meeting point
# In practice the code handles this automatically
F = 1 # head(3) to entry(2)
C = 3 # cycle length 2->0->-4
# n=1: F = 1*C - a => a = C - F = 3 - 1 = 2
a = C - F
print(f'F={F}, C={C}, a={a}')
print(f'After meeting, {F} more steps reach entry: {F == C - a or F % C == (C - a) % C}')Medição do Comprimento do Ciclo
Depois de obter o ponto de encontro dentro do ciclo (fase 1 do algoritmo de Floyd), você pode medir o comprimento do ciclo: mantenha um ponteiro parado e avance o outro até que se encontrem novamente. O número de passos realizados é igual ao comprimento do ciclo. Isso é útil em problemas que solicitam explicitamente o comprimento do ciclo.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def cycle_length(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # found meeting point
length = 1
fast = fast.next
while fast is not slow:
fast = fast.next
length += 1
return length
return 0 # no cycle
nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2] # cycle: 3->4->5->3, length=3
print(cycle_length(nodes[0])) # 3Número Feliz (Detecção de Ciclo sem uma Lista)
O algoritmo de Floyd não se limita a listas encadeadas. LeetCode 202, «Número feliz», pergunta se a substituição repetida de n pela soma dos quadrados de seus algarismos eventualmente chega a 1. Se entrar em um ciclo que não inclua 1, o processo ficará em um laço infinito. Você pode modelar isso como uma travessia virtual de uma lista encadeada, em que o «próximo» de cada nó é o próximo valor calculado — e então aplicar o algoritmo de Floyd para detectar o ciclo.
def isHappy(n):
def next_val(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
slow, fast = n, next_val(n)
while fast != 1 and slow != fast:
slow = next_val(slow)
fast = next_val(next_val(fast))
return fast == 1
print(isHappy(19)) # True (1->81+1=82->68->100->1)
print(isHappy(2)) # False (enters cycle)Detecção Ingênua Baseada em Conjunto versus Floyd
A abordagem baseada em conjuntos armazena cada nó visitado em um conjunto e verifica se ele pertence ao conjunto antes de visitá-lo. Ela usa tempo O(n) e espaço O(n). O algoritmo de Floyd também usa tempo O(n), mas apenas espaço O(1) — nenhuma estrutura de dados adicional. Em ambientes com memória limitada (sistemas embarcados e núcleos de sistemas operacionais), a garantia de espaço O(1) é importante. Às vezes, os entrevistadores solicitam explicitamente espaço O(1) como pergunta complementar depois que você apresenta a solução com conjunto.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Naive O(n) space approach
def hasCycle_set(head):
seen = set()
while head:
if id(head) in seen:
return True
seen.add(id(head))
head = head.next
return False
# Floyd's O(1) space approach
def hasCycle_floyd(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
print('Both implementations give the same result')Casos-limite na Detecção de Ciclos
Há três casos-limite a tratar. Primeiro, lista vazia: head is None — a condição do laço de Floyd fast and fast.next é encerrada imediatamente, retornando falso. Segundo, um único nó sem ciclo: fast.next é nulo, o laço termina e retorna falso. Terceiro, um único nó com ciclo: o ponteiro seguinte do nó aponta para si mesmo — os ponteiros lento e rápido começam ambos no início; após uma etapa, o ponteiro rápido continua no início, e o lento também está no início. Portanto, eles coincidem já na primeira iteração.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
# Edge cases
print(hasCycle(None)) # False: empty
node = ListNode(1)
print(hasCycle(node)) # False: single, no cycle
node.next = node
print(hasCycle(node)) # True: single node cycleCiclo de Lista Encadeada II: LeetCode 142
LeetCode 142, «Ciclo de Lista Encadeada II», solicita o nó onde o ciclo começa (ou nulo se não houver ciclo). Esta é a aplicação direta do algoritmo de Floyd em duas fases. Os entrevistadores fazem essa pergunta como complemento à detecção básica de ciclos. A solução completa: a fase 1 encontra o ponto de encontro dentro do ciclo; a fase 2 reposiciona um ponteiro no início e avança ambos até que se encontrem — esse ponto de encontro é a entrada do ciclo.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detectCycle(head):
slow = fast = head
# Phase 1
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None
# Phase 2
ptr = head
while ptr is not slow:
ptr = ptr.next
slow = slow.next
return ptr
nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2] # cycle entry: node with val=3
entry = detectCycle(nodes[0])
print(entry.val) # 3Por que o Algoritmo de Floyd é Melhor que a Abordagem com Conjunto
Embora ambas as abordagens usem tempo O(n), o fator constante difere na prática. A abordagem com conjunto precisa calcular um valor de dispersão para cada ponteiro de nó (calcular o valor, consultar a tabela de dispersão e armazenar o ponteiro), enquanto o algoritmo de Floyd realiza apenas desreferenciações de ponteiros — muito mais barato por etapa. Mais importante, a garantia de espaço O(1) permite que o algoritmo de Floyd seja executado em listas de comprimento arbitrariamente grande sem risco de esgotar a memória.
Mencionar espontaneamente essa vantagem de espaço em uma entrevista demonstra uma compreensão profunda das compensações algorítmicas, além da notação Big-O básica.
Verificação Rápida
Teste sua compreensão dos conceitos de Estruturas de Dados e Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da Lição
Nesta lição, você aprendeu: o algoritmo de ponteiros lento e rápido de Floyd detecta ciclos em tempo O(n) e espaço O(1), a fase 2 (reposicionar um ponteiro no início e avançar ambos em 1) encontra o nó exato de entrada do ciclo e a mesma técnica se aplica além das listas encadeadas a qualquer sequência implícita em que o «próximo» seja uma função. A seguir, abordaremos a mesclagem de listas ordenadas, a divisão de listas em pontos médios e a localização do n-ésimo nó a partir do fim.
Perguntas Frequentes
A aula “Detecção de Ciclos com o Algoritmo de Floyd” é grátis?
Sim — o texto completo de “Detecção de Ciclos com o Algoritmo de Floyd” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Coding Interview Prep, atualize para CoddyKit PRO. O curso de Coding Interview Prep inclui 4 aulas no total.
O que vou aprender em “Detecção de Ciclos com o Algoritmo de Floyd”?
Detecte ciclos usando ponteiros lento e rápido, encontre o ponto de entrada do ciclo e prove matematicamente a correção do algoritmo. Você pratica Coding Interview Prep com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Coding Interview Prep?
Nenhuma experiência prévia é necessária. Coding Interview Prep no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Detecção de Ciclos com o Algoritmo de Floyd”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Coding Interview Prep?
Sim. Cada aula de Coding Interview Prep inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Classe Node e Construção de Listas
- Revertendo uma Lista Encadeada
- Detecção de Ciclos com o Algoritmo de Floyd
- Intercalar, Dividir e Encontrar o N-ésimo a Partir do Fim