Linked List Cycle

Q: Qual é a complexidade de tempo e espaço de Linked List Cycle?

Ambas as abordagens levam tempo O(n) , pois cada nó é percorrido um número limitado de vezes. Marcar os nós visitados requer O(n) de memória extra. Os ponteiros rápido e lento de Floyd precisam de O(1) : dois números de nós.

Q: Por que o ponteiro rápido não pode pular por cima do ponteiro lento?

Dentro do ciclo, a cada rodada, fast avança dois nós e slow , um; assim, a distância que fast ainda precisa percorrer para alcançar slow diminui exatamente uma unidade. Uma distância que diminui uma unidade por rodada segue a sequência 3, 2, 1, 0 e não pode passar de zero, então os dois ponteiros se encontram em um nó.

FácilPonteiros rápido e lento Lista ligada

+10

Uma lista encadeada é armazenada no array next: o nó i aponta para o nó next[i], e -1 significa que a lista termina ali. A cabeça é o nó 0. Siga os links a partir da cabeça e retorne true se voltar a um nó que já visitou, ou false se chegar ao fim. Nós que o percurso nunca alcança não contam, mesmo que apontem uns para os outros em um ciclo.

Função

hasCycle(next: integer-array) → boolean

nextinteger-array: o link de cada nó: next[i] é o nó após o nó i, ou -1
Retornaboolean: true se o percurso a partir do nó 0 revisitar um nó, false se chegar a -1

Restrições

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
Vários nós podem apontar para o mesmo nó, e alguns nós podem ser inacessíveis a partir da cabeça.

Exemplos

Entrada: next = [1, 2, 3, 1]
Saída: true
Explicação: O percurso vai de 0 a 1, 2, 3 e depois volta a 1. O nó 1 é visitado duas vezes, então a lista tem um ciclo que passa pelos nós 1, 2 e 3.

Entrada: next = [2, -1, 1]
Saída: false
Explicação: O percurso segue 0, 2, 1 e então chega a -1: três nós diferentes e depois o fim, portanto não há ciclo.

Entrada: next = [-1, 2, 1]
Saída: false
Explicação: O nó 0 aponta para -1, então a lista tem um nó. Os nós 1 e 2 apontam um para o outro em um loop, mas o percurso a partir da cabeça nunca chega até eles.

+16 testes ocultos ao enviar

Para ir além

Você também consegue encontrar o nó onde o ciclo começa, ainda usando memória extra O(1)?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Uma lista sem ciclo chega a -1 após n links, mas uma lista com ciclo nunca termina, então você não pode esperar pelo fim. Você precisa de uma maneira de perceber que o percurso está dando voltas. Lembrar de cada nó que você visita faz isso usando O(n) de memória. Os ponteiros rápido e lento de Floyd fazem isso com dois inteiros, porque um ponteiro que se move duas vezes mais rápido precisa alcançar o lento dentro de um loop.

Marque os nós que você visita

Intuição

Comece pelo nó 0 e marque cada nó ao sair dele. Se você chegar a um nó que já está marcado, o percurso voltou a ele e, a partir daí, se repete para sempre: isso é um ciclo. No exemplo 1, você marca 0, 1, 2 e 3, e o link do nó 3 leva ao nó 1, que está marcado.

Os nós são numerados de 0 a n-1, então um array booleano de comprimento n serve como conjunto de nós visitados. Em uma lista encadeada construída com objetos, você colocaria as referências dos nós em um conjunto hash; a ideia é a mesma.

Cada nó é marcado no máximo uma vez, e o percurso para na primeira repetição ou em -1, então leva no máximo n etapas: tempo O(n) e memória O(n) para as marcações.

Algoritmo

Crie um array de booleanos visited de comprimento n, todos falsos.
Defina node = 0.
Enquanto node não for -1, retorne true se visited[node] já for verdadeiro.
Caso contrário, defina visited[node] e avance para next[node].
Quando o percurso chegar a -1, retorne false.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

Dois ponteiros, rápido e lento (detecção de ciclo de Floyd)

Intuição

Inicie dois ponteiros na cabeça. slow segue um elo por rodada e fast segue dois. Se a lista terminar, fast chega a -1 primeiro e você retorna false. Se houver um ciclo, fast entra nele primeiro e continua circulando até que slow também chegue.

Quando ambos estiverem no ciclo, a cada rodada fast ganha exatamente um nó em relação a slow. A distância que fast ainda precisa percorrer para alcançar slow diminui em um a cada rodada, então chega a zero e os ponteiros ficam no mesmo nó. Avançando um nó de cada vez, fast nunca pode pular slow.

No exemplo 1, após uma rodada, slow está no nó 1 e fast no nó 2. Após duas rodadas, slow está no nó 2 e fast passou pelos nós 3 e 1. Após três rodadas, ambos estão no nó 3, então a resposta é true.

slow precisa de no máximo n rodadas para entrar no ciclo e, assim que estiver nele, os ponteiros se encontram antes de completar uma volta, então o tempo é O(n). A única memória usada são dois números de nós.

Algoritmo

Defina slow = 0 e fast = 0.
Enquanto fast não for -1 e next[fast] não for -1, mova slow um elo e fast dois elos.
Após cada movimento, retorne true se estiverem no mesmo nó.
Quando o loop parar, fast encontrou o fim: retorne false.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

Armadilhas e casos extremos

Os bugs aqui dizem respeito ao fim da lista e a quais nós contam.

Mover fast por dois links sem verificar ambos. fast e next[fast] devem ser nós reais antes de você ler next[next[fast]]; caso contrário, você lê next[-1], o que causa uma falha na maioria das linguagens e retorna silenciosamente o último elemento em Python.
Comparar os ponteiros antes de movê-los. Ambos começam no nó 0, então uma verificação no início do loop indica um ciclo em todas as listas.
Examinar o array inteiro em vez do percurso. Em [-1, 2, 1], os nós 1 e 2 formam um loop, mas o percurso a partir da cabeça termina imediatamente, então a resposta é false. Também é errado verificar se um valor se repete em next: em [4, 4, 4, 4, -1], vários nós apontam para o nó 4, mas não há ciclo.
Presumir que um ciclo precisa voltar à cabeça. Em [1, 2, 3, 4, 4], o último nó aponta para si mesmo, assim como a cabeça em [0].

Perguntas frequentes4

Como funciona a detecção de ciclos de Floyd?

Dois ponteiros começam na cabeça: um avança um elo por etapa, o outro, dois. Sem um ciclo, o mais rápido chega ao fim. Com um ciclo, ambos acabam dentro dele; o mais rápido diminui a distância em um nó por etapa, e eles se encontram no mesmo nó.

Qual é a complexidade de tempo e espaço de Linked List Cycle?

Ambas as abordagens levam tempo O(n), pois cada nó é percorrido um número limitado de vezes. Marcar os nós visitados requer O(n) de memória extra. Os ponteiros rápido e lento de Floyd precisam de O(1): dois números de nós.

Por que o ponteiro rápido não pode pular por cima do ponteiro lento?

Dentro do ciclo, a cada rodada, fast avança dois nós e slow, um; assim, a distância que fast ainda precisa percorrer para alcançar slow diminui exatamente uma unidade. Uma distância que diminui uma unidade por rodada segue a sequência 3, 2, 1, 0 e não pode passar de zero, então os dois ponteiros se encontram em um nó.

Você consegue detectar o ciclo contando os passos?

Nesta representação em array, sim: uma lista sem ciclo chega a -1 em até n elos, então percorrer n elos sem chegar ao fim comprova que há um ciclo, usando memória O(1). Ela precisa do número de nós, que uma lista formada por ponteiros não fornece, e contar os nós primeiro nunca termina quando há um ciclo. O método de Floyd não precisa de contagem.

Python

def hasCycle(next):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

next = [1, 2, 3, 1]

Esperado

true