Ciclo em uma cadeia
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
Lembrar cada nó visitado funciona, mas custa memória para a cadeia inteira. Existe um jeito de perceber um ciclo sem guardar nada?
Imagine dois corredores em uma pista, um duas vezes mais rápido que o outro. Em uma estrada reta, eles nunca mais se encontram; em uma pista circular, eles precisam se encontrar.
Mova um ponteiro um passo por vez e outro dois passos por vez. Se o rápido passar do fim, não há ciclo; se os dois caírem no mesmo nó em algum momento, há.
- Tempo-alvo
- O(n)
- Espaço-alvo
- O(1)
Solução
Dois ponteiros começam no head, um avançando uma ligação por passo e o outro avançando duas. Sem ciclo, o ponteiro rápido chega ao fim e a resposta é False. Com ciclo, os dois ponteiros acabam girando dentro dele e, como a distância entre eles diminui uma ligação a cada passo, o ponteiro rápido precisa cair exatamente no lento. O tempo é O(n) e o espaço é O(1).
class Node:
def __init__(self, val): self.val, self.next = val, None
def build(values, pos): # the tail links back to index pos, or nowhere if -1
nodes = [Node(v) for v in values]
for a, b in zip(nodes, nodes[1:]): a.next = b
if nodes and pos >= 0: nodes[-1].next = nodes[pos]
return nodes[0] if nodes else None
def has_loop(head):
slow = fast = head
while fast and fast.next:
slow, fast = slow.next, fast.next.next # the gap closes by one link per step
if slow is fast:
return True
return False # the fast pointer found the end
print(has_loop(build([3, 2, 0, -4], 1))) # -> True
print(has_loop(build([1, 2], -1))) # -> False
print(has_loop(build([7], 0))) # -> TrueTravou na ideia, e não no código? Detectar um ciclo explica isso.