Pular para o conteúdo

Ciclo em uma cadeia

Fácil#fast-slow-pointers#cycle-detection~15 min

A missão

Problema

Você recebe o head de uma cadeia de nós simplesmente encadeada. Em algum ponto, um nó pode apontar de volta para um nó anterior, o que faz o percurso girar para sempre em vez de chegar ao fim. Retorne True se a cadeia tiver um ciclo assim e False se, seguindo as ligações, você acabar chegando a None. Nos exemplos, a cadeia é descrita pelos seus valores mais pos, o índice para o qual o último nó aponta de volta, ou -1 se não houver ciclo.

Exemplos

Input:  values = [3, 2, 0, -4], pos = 1
Output: True
Por quê: o último nó aponta de volta para o nó que guarda 2
Input:  values = [1, 2], pos = -1
Output: False
Por quê: o percurso termina depois do segundo nó
Input:  values = [7], pos = 0
Output: True
Por quê: edge case: um único nó que aponta para si mesmo

Dicas

0 / 3

Tempo-alvo
O(n)
Espaço-alvo
O(1)

Travou na ideia, e não no código? Detectar um ciclo explica isso.

Python 3Ctrl+Enter executa