24 de Março
Ciclo em lista encadeada
Como detectar ciclo com ponteiro rápido e ponteiro lento e entender por que velocidades diferentes acabam se encontrando.
Lista Encadeada Intermediario 15 min TypeScript
Dada uma lista encadeada, retorne true se ela tiver ciclo e false caso contrario.
No problema original, você recebe head. Aqui no SeniorPath, os testes usam:
values: os valores da lista em ordempos: o indice para onde o ultimo no aponta
Se pos = -1, a lista termina em null.
Exemplo:
Input: values = [3, 2, 0, -4], pos = 1
Output: true
Isso representa o ultimo no apontando para o no de indice 1.
O que perceber antes de codar
- Os valores dos nos não importam para detectar ciclo. O que importa e a estrutura.
- Se não existe ciclo, a caminhada acaba em `-1`.
- Se existe ciclo, um ponteiro rápido eventualmente alcanca o lento.
Erros comuns
- esquecer que `pos = -1` significa sem ciclo
- mover o ponteiro rápido sem tratar o caso em que ele já chegou ao fim
Passo 1 - Ignorar o formato e focar na estrutura
O problema real continua sendo de lista encadeada com ciclo.
Aqui, os testes usam values e pos porque um objeto com referência ciclica não entra bem em JSON.
Isso muda a forma do input, mas não muda a ideia central:
- existe um "próximo"
- esse próximo ou termina
- ou entra em loop
Passo 2 - Escrever a versão inicial mais direta
A leitura natural e:
- comece do primeiro no
- guarde quais indices já foram visitados
- se visitar um de novo, ha ciclo
Funciona bem.
O custo e a memória extra.
Passo 3 - Entender a intuição do Floyd
Se existe um ciclo e:
- um ponteiro anda devagar
- o outro anda rápido
em algum momento o rápido alcanca o lento dentro da volta.
Se não existe ciclo, o rápido chega ao fim.
Passo 4 - Pensar no "próximo" como uma função
No nosso formato, o próximo indice e:
index + 1, enquanto não chegou no ultimo nopos, quando esta no ultimo no-1, se não existe ciclo
O algoritmo continua o mesmo.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function hasCycle(values: number[], pos: number): boolean {
// `pos` is the index where the tail points back to, or -1 if there is no cycle
// sua solução aqui
return false
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n)
Espaço: O(1)
Solução 1 - Guardar visitados em um conjunto hash
Boa versão inicial porque deixa claro o significado de “detectar ciclo”.
function nextIndex(index: number, size: number, pos: number): number {
if (index === -1 || size === 0) {
return -1
}
if (index < size - 1) {
return index + 1
}
return pos
}
export function hasCycle(values: number[], pos: number): boolean {
const visited = new Set<number>()
let current = values.length === 0 ? -1 : 0
while (current !== -1) {
if (visited.has(current)) {
return true
}
visited.add(current)
current = nextIndex(current, values.length, pos)
}
return false
}Funciona, mas usa memória proporcional ao caminho percorrido.
Solução 2 - Floyd com dois ponteiros
Agora você detecta o ciclo sem guardar visitados.
function nextIndex(index: number, size: number, pos: number): number {
if (index === -1 || size === 0) {
return -1
}
if (index < size - 1) {
return index + 1
}
return pos
}
export function hasCycle(values: number[], pos: number): boolean {
let slow = values.length === 0 ? -1 : 0
let fast = values.length === 0 ? -1 : 0
while (fast !== -1) {
slow = nextIndex(slow, values.length, pos)
fast = nextIndex(nextIndex(fast, values.length, pos), values.length, pos)
if (slow !== -1 && slow === fast) {
return true
}
}
return false
}O ponto forte aqui e o raciocínio sobre movimento, não o formato do input.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial guarda os nos visitados em um
conjunto hash, mas a solução melhor usa o algoritmo de Floyd comdois ponteiros. Se existir ciclo, um ponteiro rápido inevitavelmente encontra o lento. Se não existir, o rápido chega ao fim. Assim eu detecto ciclo emO(n)comO(1)de memória extra.
Isso mostra que você:
- sabe justificar
dois ponteirossem frase decorada - entende por que o encontro acontece
- reconhece quando um conjunto de visitados pode virar um algoritmo melhor
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- detectar ciclo em estrutura com relação de próximo
- encontrar ponto de encontro em percurso circular
- resolver variações de
lista encadeadacomdois ponteiros - reconhecer quando velocidades diferentes revelam estrutura escondida
O ponto não e decorar esse problema.
O ponto e entender por que dois ponteiros conseguem provar a existencia de um loop.