Dois Ponteiros: Lento e Rápido
Aplique o padrão de ponteiros lento e rápido para remover duplicatas in-place, mover zeros e particionar arrays em torno de um valor pivô.
Dois Ponteiros: Lento e Rápido é uma aula grátis de Coding Interview Prep no CoddyKit. Esta é a aula 4 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.
Ponteiros lento e rápido explicados
O padrão de ponteiros lento e rápido (também chamado de tartaruga e lebre) usa dois ponteiros que se movem em velocidades diferentes pela mesma sequência. Diferentemente dos ponteiros de extremidades opostas, ambos começam no início. O ponteiro lento avança uma posição por vez; o ponteiro rápido avança duas (ou mais). A diferença de velocidade cria invariantes úteis: o ponteiro lento acompanha um “prefixo válido”, enquanto o ponteiro rápido examina posições adiante em busca de condições.
# Slow pointer marks the write position;
# Fast pointer scans for next non-duplicate.
def remove_duplicates(nums):
if not nums: return 0
slow = 0 # next position to write a unique value
for fast in range(1, len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1 # new length
nums = [1, 1, 2, 3, 3, 3, 4]
k = remove_duplicates(nums)
print(nums[:k]) # [1, 2, 3, 4]Remover duplicatas de vetor ordenado
Em um vetor ordenado, as duplicatas são adjacentes. O ponteiro lento acompanha o último valor único escrito; o ponteiro rápido examina as posições seguintes. Sempre que o ponteiro rápido encontra um valor diferente de nums[slow], avance o ponteiro lento e copie o novo valor. Este algoritmo no próprio vetor executa-se em tempo O(n) com O(1) de espaço extra — uma pergunta padrão de entrevistas que testa o domínio do padrão de ponteiros de leitura e escrita.
def remove_duplicates_v2(nums):
slow = 0
for fast in range(len(nums)):
if nums[fast] != nums[slow]:
slow += 1
nums[slow] = nums[fast]
return slow + 1
# Allow at most 2 occurrences
def remove_duplicates_k2(nums):
slow = 0
for fast in range(len(nums)):
if slow < 2 or nums[fast] != nums[slow - 2]:
nums[slow] = nums[fast]
slow += 1
return slow
print(remove_duplicates_k2([1,1,1,2,2,3]))
# Result: 5, nums[:5] = [1,1,2,2,3]Mover zeros com ponteiros lento e rápido
Mova todos os zeros para o final, preservando a ordem relativa dos elementos diferentes de zero. O ponteiro lento marca a próxima posição para um elemento diferente de zero. O ponteiro rápido procura valores diferentes de zero. Quando o ponteiro rápido encontra um, copie-o para a posição do ponteiro lento e avance ambos. Depois da varredura, preencha com zeros as posições do ponteiro lento até o final. Tempo O(n), espaço O(1).
def move_zeroes(nums):
slow = 0 # next position for a non-zero
for fast in range(len(nums)):
if nums[fast] != 0:
nums[slow] = nums[fast]
slow += 1
# Fill rest with zeroes
while slow < len(nums):
nums[slow] = 0
slow += 1
nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print(nums) # [1, 3, 12, 0, 0]Particionar vetor em torno de um pivô
A etapa de particionamento da ordenação rápida reorganiza os elementos no próprio vetor, de modo que todos os valores < pivô fiquem antes dos valores >= pivô. O esquema de Lomuto usa um ponteiro lento (que marca a última posição de um elemento pequeno) e um ponteiro rápido (que percorre o vetor para a frente). Quando o ponteiro rápido encontra um elemento pequeno, incremente o ponteiro lento e troque os elementos. Isso executa-se em tempo O(n) com O(1) de espaço extra.
def lomuto_partition(nums, low, high):
pivot = nums[high]
slow = low - 1 # last position of small element
for fast in range(low, high):
if nums[fast] <= pivot:
slow += 1
nums[slow], nums[fast] = nums[fast], nums[slow]
# Place pivot in final position
nums[slow+1], nums[high] = nums[high], nums[slow+1]
return slow + 1 # pivot's final index
arr = [3, 1, 4, 1, 5, 9, 2, 6]
p = lomuto_partition(arr, 0, len(arr)-1)
print(arr) # elements before p are <= pivotEncontrar o meio de uma lista encadeada
Com ponteiros lento e rápido em uma lista encadeada, o ponteiro rápido avança dois nós por passo e o ponteiro lento avança um. Quando o ponteiro rápido chega ao final, o ponteiro lento está no meio. Essa abordagem de uma única passagem, em O(n), é muito mais simples do que contar os nós e depois percorrer metade da lista. Ela é usada como uma subetapa da ordenação por intercalação de listas encadeadas e da detecção de palíndromos em listas encadeadas.
class Node:
def __init__(self, val, nxt=None):
self.val = val
self.next = nxt
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # slow is at middle
# Build 1->2->3->4->5
h = Node(1, Node(2, Node(3, Node(4, Node(5)))))
mid = find_middle(h)
print(mid.val) # 3 (middle of 5 nodes)Detecção de ciclo: tartaruga e lebre de Floyd
O algoritmo de detecção de ciclos de Floyd posiciona os ponteiros lento e rápido no início de uma lista encadeada. O ponteiro lento avança um nó; o rápido avança dois. Se existir um ciclo, o ponteiro rápido acabará alcançando o lento e ambos se encontrarão dentro do ciclo. Se o ponteiro rápido alcançar o valor nulo, não há ciclo. O encontro é garantido porque o ponteiro rápido ganha uma posição sobre o lento a cada iteração — em um ciclo de comprimento k, eles se encontram em até k passos depois que o ponteiro lento entra no ciclo.
class ListNode:
def __init__(self, val=0, nxt=None):
self.val = val
self.next = nxt
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # identity check (same object)
return True
return False
# 1->2->3->4->2 (cycle at node 2)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n1.next=n2; n2.next=n3; n3.next=n4; n4.next=n2
print(has_cycle(n1)) # TrueEncontrar o ponto de entrada do ciclo
Depois de detectar um ciclo, quando os dois ponteiros se encontram, reposicione um deles no início. Em seguida, avance ambos os ponteiros uma posição por vez. Eles se encontrarão no ponto de entrada do ciclo. Isso usa a propriedade matemática de que a distância do início até a entrada do ciclo é igual à distância do ponto de encontro até a entrada do ciclo (módulo o comprimento do ciclo). Esse é um belo resultado matemático que aparece com frequência em problemas difíceis de entrevistas.
def detect_cycle(head):
slow = fast = head
# Phase 1: detect
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
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow # cycle entry node
# Using same cycled list as previous scene
print(detect_cycle(n1).val) # 2 (cycle entry)Ponteiros lento e rápido para números felizes
Os ponteiros lento e rápido aplicam-se, além de listas encadeadas, a qualquer processo que forme ciclos. Um “número feliz” percorre ciclos baseados em somas dos quadrados dos dígitos — se n não for feliz, a sequência eventualmente entra em um ciclo. Detecte o ciclo com o ponteiro lento (um passo = um quadrado de dígito) e o rápido (dois passos). Se eles se encontrarem em 1, n é feliz; caso contrário, ele está preso em um ciclo que não contém 1. Este é o algoritmo de Floyd aplicado a uma lista encadeada virtual de valores.
def is_happy(n):
def next_val(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
slow = n
fast = next_val(n)
while fast != 1 and slow != fast:
slow = next_val(slow)
fast = next_val(next_val(fast))
return fast == 1
print(is_happy(19)) # True (1->9->...->1)
print(is_happy(2)) # False (enters a cycle)Enésimo nó a partir do fim da lista
Encontre o enésimo nó a partir do fim de uma lista encadeada em uma única passagem usando dois ponteiros. Avance o ponteiro rápido n posições. Depois, avance ambos os ponteiros juntos até que o rápido chegue ao final — o lento estará no enésimo nó a partir do fim. Para excluir esse nó, mantenha um ponteiro “anterior” uma posição atrás do lento. Este é um problema clássico de lista encadeada em uma única passagem que evita contar primeiro o comprimento total.
def remove_nth_from_end(head, n):
dummy = ListNode(0)
dummy.next = head
fast = slow = dummy
# Advance fast n+1 steps
for _ in range(n + 1):
fast = fast.next
# Advance together
while fast:
slow = slow.next
fast = fast.next
# slow.next is the nth from end
slow.next = slow.next.next
return dummy.next
# Build 1->2->3->4->5, remove 2nd from end
h2 = ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))
result = remove_nth_from_end(h2, 2)
# Should give 1->2->3->5Ponteiros lento e rápido em problemas de cadeias de caracteres
O raciocínio de ponteiros lento e rápido também se aplica a problemas de vetores e cadeias de caracteres. Ao compactar uma cadeia codificada por comprimento de sequência, o ponteiro lento marca a posição de escrita e o ponteiro rápido percorre até o final de cada sequência. Quando todos os caracteres da sequência forem iguais ao caractere na posição lenta, avance o ponteiro rápido; caso contrário, registre a sequência e atualize o ponteiro lento. Isso alcança O(n) em uma única passagem com espaço O(1).
def compress(chars):
slow = fast = 0
while fast < len(chars):
char = chars[fast]
count = 0
# Count the run
while fast < len(chars) and chars[fast] == char:
fast += 1
count += 1
chars[slow] = char
slow += 1
if count > 1:
for c in str(count):
chars[slow] = c
slow += 1
return slow
chars = list('aabcccccaa')
print(compress(chars)) # 6
print(chars[:6]) # ['a','2','b','c','5','a']... wait
# Actually: ['a','2','b','c','5','a','2']Escolhendo entre ponteiros lento e rápido e de extremidades opostas
Use ponteiros de extremidades opostas quando o problema envolver pares cuja soma atinge um alvo, verificações de palíndromos ou o estreitamento de uma janela pelos dois lados. Use ponteiros lento e rápido quando precisar de um ponteiro de escrita (para remover ou mover elementos), ao processar a estrutura de uma lista encadeada (meio, ciclo) ou ao detectar ciclos em qualquer sequência de valores. Ambos eliminam laços aninhados e alcançam O(n) — o fator decisivo é a estrutura do percurso.
# Pattern matcher:
# 1. Sorted array, target sum -> OPPOSITE ENDS
# 2. Remove/filter elements in-place -> SLOW-FAST (read-write)
# 3. Linked list middle/cycle -> SLOW-FAST (1x vs 2x speed)
# 4. Detect cycle in value sequence -> SLOW-FAST (Floyd)
# Example: given sorted array, remove val in-place
def remove_sorted(nums, val):
slow = 0
for fast in range(len(nums)):
if nums[fast] != val:
nums[slow] = nums[fast]
slow += 1
return slow
nums = [0,1,2,2,3,0,4,2]
print(remove_sorted(nums, 2)) # 5Verificação rápida
Teste sua compreensão dos conceitos de Estruturas de Dados & Algoritmos — Preparação para Entrevistas de Programação desta lição.
Recapitulação da lição
Nesta lição, você aprendeu: o padrão lento-rápido (leitura-escrita) mantém um ponteiro de escrita na próxima posição válida enquanto um ponteiro rápido percorre o vetor para a frente — a base da remoção, eliminação de duplicatas e movimentação de zeros no próprio vetor, a tartaruga e a lebre de Floyd detectam ciclos em tempo O(n) e espaço O(1) explorando a diferença de velocidade entre dois ponteiros e depois de detectar um ciclo, reposicionar um ponteiro no início e avançar ambos na mesma velocidade encontra a entrada do ciclo devido a uma igualdade de distâncias demonstrável. A seguir, exploraremos a API de cadeias de caracteres do Python para entrevistas.
Perguntas Frequentes
A aula “Dois Ponteiros: Lento e Rápido” é grátis?
Sim — o texto completo de “Dois Ponteiros: Lento e Rápido” é 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 “Dois Ponteiros: Lento e Rápido”?
Aplique o padrão de ponteiros lento e rápido para remover duplicatas in-place, mover zeros e particionar arrays em torno de um valor pivô. 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 4 de 4.
Quanto tempo leva a aula “Dois Ponteiros: Lento e Rápido”?
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
- Fundamentos de Arrays e Operações In-Place
- Somas de Prefixos e Totais Acumulados
- Dois Ponteiros: Extremidades Opostas
- Dois Ponteiros: Lento e Rápido