Introdução
Bem-vindos ao 12º artigo da série “Preparação para Entrevistas” no nosso blog, onde focamos em desmistificar os desafios comuns enfrentados em entrevistas técnicas nas grandes empresas de tecnologia. Hoje, vamos explorar um problema frequente: detectar a presença de um ciclo em uma lista encadeada. Listas encadeadas é um conceito básico em ciência da computação e detectar ciclos em listas é uma pergunta clássica em entrevistas para posições de desenvolvimento de software. Como todos os outros artigos desta série, entender como abordar este problema não só prepara você para esses desafios técnicos, mas também aprimora sua habilidade de pensar em soluções eficientes e otimizadas.
Explicação do Problema
O problema que estamos abordando é identificar se uma lista encadeada contém um ciclo. Uma lista encadeada é uma estrutura de dados linear, na qual cad nó, contém um valor e um ponteiro para o próximo nó na sequência. Em um cenário ideal, uma lista encadeada termina com um nó apontando para null, indicando o final da lista. No entanto, se um nó aponta de volta para um nó anterior na lista, cria-se um ciclo, o que pode levar a problemas como loops infinitos.
Abaixo está uma ilustração que demonstra visualmente uma lista encadeada com um ciclo:
Note que um dos nós aponta de volta para um nó anterior, formando um ciclo. Este é o problema que precisamos detectar e resolver.
Solução 1: Utilizando um Set para Armazenar Nós Visitados
Uma abordagem eficaz para detectar um ciclo em uma lista encadeada é utilizar uma estrutura de dados Set para manter o registro dos nós já visitados. À medida que percorremos a lista, cada nó visitado é adicionado ao Set. Se em algum momento encontrarmos um nó que já está no Set, isso indica que encontramos um ciclo.
Implementação Java e Python
import java.util.HashSet;
import java.util.Set;
public class CicloListaEncadeada {
public static boolean containsCiclo(No inicio) {
// Cria um Set para armazenar os nós visitados.
Set<No> visitados = new HashSet<>();
No noAtual = inicio;
while(noAtual != null) {
// Verifica se o nó atual já foi visitado.
if (visitados.contains(noAtual)) {
// Se o nó atual já foi visitado, um ciclo foi encontrado.
return true;
}
// Adiciona o nó atual ao conjunto de visitados.
visitados.add(noAtual);
noAtual = noAtual.proximo;
}
return false;
}
}
class No {
int valor;
No proximo;
public No(int valor) {
this.valor = valor;
this.proximo = null;
}
}class No:
def __init__(self, valor):
self.valor = valor
self.proximo = None
class CicloListaEncadeada:
@staticmethod
def containsCiclo(inicio):
# Cria um Set para armazenar os nós visitados.
visitados = set()
# Inicializa o nó atual com o nó de início.
no_atual = inicio
# Itera através da lista encadeada.
while no_atual:
# Verifica se o nó atual já foi visitado.
if no_atual in visitados:
# Se o nó atual já foi visitado, um ciclo foi encontrado.
return True
# Adiciona o nó atual ao conjunto de visitados.
visitados.add(no_atual)
no_atual = no_atual.proximo
return FalseAnálise da Complexidade
Complexidade de Tempo
- Operações de Inserção e Busca no
Set: Tanto a inserção (add) quanto a busca (contains) em um conjunto/Settêm uma complexidade de tempo média de O(1). Isso se deve à natureza do hashing, que permite operações de acesso rápido. - Iteração Sobre a Lista Encadeada: Cada nó na lista é visitado exatamente uma vez. Durante a visita de cada nó, realizamos uma operação de busca e possivelmente uma de inserção no
Set. - Tempo Total: Portanto, para uma lista encadeada com
nnós, a complexidade total de tempo é O(n), pois cada nó é acessado uma vez e para cada nó, as operações noSetsão realizadas em tempo constante.
Complexidade de Espaço
A solução proposta usa um conjunto (Set em Java ou set em Python) para rastrear os nós já visitados na lista encadeada. Vamos analisar sua complexidade em termos de tempo e espaço:
- Armazenamento dos Nós Visitados: O espaço adicional usado é para armazenar os nós já visitados no
Set. No pior caso, quando não há ciclo, todos os nós serão inseridos noSetantes que a lista seja completamente percorrida. - Espaço Total: Portanto, a complexidade de espaço é O(n) no pior caso, onde
né o número total de nós na lista encadeada.
Solução 2: Utilizando Dois Ponteiros
x`Esta solução envolve o uso de dois ponteiros que se movem através da lista em velocidades diferentes – um mais rápido(2 nós) e outro mais lento. Se houver um ciclo na lista, eventualmente o ponteiro mais rápido alcançará o ponteiro mais lento, indicando a presença de um ciclo.
Implementação Java e Python
public class CicloListaEncadeada {
public static boolean containsCiclo(No inicio) {
if (inicio == null) return false;
No lento = inicio;
No rapido = inicio.proximo;
while (rapido != null && rapido.proximo != null) {
if (rapido == lento) {
return true; // Ciclo detectado
}
lento = lento.proximo; // Move um passo
rapido = rapido.proximo.proximo; // Move dois passos
}
return false; // Sem ciclo
}
}
class No {
int valor;
No proximo;
public No(int valor) {
this.valor = valor;
this.proximo = null;
}
}
class No:
def __init__(self, valor):
self.valor = valor
self.proximo = None
class CicloListaEncadeada:
@staticmethod
def containsCiclo(inicio):
if inicio is None:
return False
lento = inicio
rapido = inicio.proximo
while rapido is not None and rapido.proximo is not None:
if rapido == lento:
return True # Ciclo detectado
lento = lento.proximo # Move um passo
rapido = rapido.proximo.proximo # Move dois passos
return False # Sem cicloAnálise de Complexidade
Complexidade de Tempo
- Iteração com Dois Ponteiros: Nesta solução, usamos dois ponteiros que se movem em velocidades diferentes pela lista encadeada (um “lento” e um “rápido”).
- Cenário sem Ciclo: No pior caso, quando não há ciclo, o ponteiro rápido alcançará o final da lista. Como o ponteiro rápido se move dois passos de cada vez e o ponteiro lento se move um passo de cada vez, o número máximo de iterações será menor do que 2n, onde n é o número de nós na lista. Isso porque o ponteiro rápido avança mais rápido em direção ao final da lista.
- Cenário com Ciclo: Em uma lista com ciclo, os ponteiros rapidamente entrarão no ciclo, e o ponteiro rápido eventualmente alcançará o ponteiro lento dentro do ciclo. O número de iterações necessárias para que isso aconteça depende do tamanho do ciclo e da posição do início do ciclo na lista, mas será significativamente menor que 2n.
Portanto, a complexidade de tempo, em geral, é O(n), onde n é o número de nós na lista.
Complexidade de Espaço
- Uso de Ponteiros: A principal vantagem desta solução é que ela usa apenas um espaço constante adicional, independentemente do tamanho da lista encadeada. Apenas dois ponteiros adicionais são usados, independentemente do número de nós na lista.
- Complexidade de Espaço Total: Assim, a complexidade de espaço é O(1), o que significa que o espaço utilizado não aumenta com o tamanho da lista encadeada.
Conclusão
Neste artigo, exploramos duas abordagens eficientes para detectar a presença de um ciclo em uma lista encadeada, um problema comum em entrevistas técnicas para posições em grandes empresas de tecnologia.
- A Solução 1, utilizando um
Setpara armazenar os nós visitados, oferece simplicidade e eficiência em termos de tempo de execução, mas requer espaço adicional proporcional ao tamanho da lista. - Já a Solução 2, aplicando o método de dois ponteiros, é extremamente eficiente em termos de espaço, usando apenas um espaço constante, e também oferece uma boa eficiência de tempo.
Ambas as soluções têm suas vantagens e podem ser escolhidas com base nas necessidades específicas do problema e nas restrições de recursos.
Esperamos que este artigo ajude você a se preparar melhor para suas próximas entrevistas técnicas.
👨💻🚀 Gostou do conteúdo? Comente abaixo suas experiências e dúvidas! Não esqueça de compartilhar com amigos que também estão se preparando para entrevistas. 👩💻🚀
Referências
Cracking the Coding Interview’ é um best-seller renomado e um favorito pessoal – um livro indispensável na preparação para entrevistas técnicas!
Designing Data-Intensive Applications: é uma referência para criar aplicações escaláveis, robustas e de alto desempenho!
Pingback: Cycle Detection in Linked Lists: Essential Algorithms Unveiled - Art of Coding