Remoção de Elmeentos em Lista Ligada
Dado o nó inicial (head) de uma lista ligada simples e um valor inteiro val, remova todos os nós cujo atributo val coincida com val fornecido e devolva a nova referência para o primeior nó.
Exemplo:
<strong>Entrada:</strong> head = [1,2,6,3,4,5,6], val = 6
<strong>Saída:</strong> [1,2,3,4,5]
<strong>Entrada:</strong> head = [], val = 1
<strong>Saída:</strong> []
Para simplificar a lógica, utiliza-se um nó virtual inicial (dummy_head). Sem ele, seria necessário um tratamento especial ao remover o primeiro nó, o que poderia exigir estruturas de controle adicionais. Com o nó auxiliar, o processo torna-se uniforme, evitando verificações complexas durante a iteração.
class No:
def __init__(self, valor=0, proximo=None):
self.valor = valor
self.proximo = proximo
class Solucao:
def eliminar_elementos(self, head, valor_alvo):
no_auxiliar = No(proximo=head)
ponteiro = no_auxiliar
while ponteiro.proximo:
if ponteiro.proximo.valor == valor_alvo:
ponteiro.proximo = ponteiro.proximo.proximo
else:
ponteiro = ponteiro.proximo
return no_auxiliar.proximo
Projeto de Lista Ligada Personalizada
Implemente uma lista ligada usando uma estrutura de nó único (com atribuots valor e proximo) ou dupla (incluindo também anterior). A classe deve suportar operações básicas como obtenção por índice, inserção e remoção.
Exemplo de uso:
lista = MinhaListaLigada()
lista.inserir_no_inicio(1)
lista.inserir_no_fim(3)
lista.inserir_no_indice(1, 2) # Lista torna-se 1→2→3
lista.obter(1) # Retorna 2
lista.remover_no_indice(1) # Lista torna-se 1→3
lista.obter(1) # Retorna 3
Implementação com Lista Simples
class No:
def __init__(self, valor=0, proximo=None):
self.valor = valor
self.proximo = proximo
class MinhaListaLigada:
def __init__(self):
self.no_sentinela = No()
self.tamanho = 0
def obter(self, indice):
if indice < 0 or indice >= self.tamanho:
return -1
atual = self.no_sentinela.proximo
for _ in range(indice):
atual = atual.proximo
return atual.valor
def inserir_no_inicio(self, valor):
novo_no = No(valor, self.no_sentinela.proximo)
self.no_sentinela.proximo = novo_no
self.tamanho += 1
def inserir_no_fim(self, valor):
atual = self.no_sentinela
while atual.proximo:
atual = atual.proximo
atual.proximo = No(valor)
self.tamanho += 1
def inserir_no_indice(self, indice, valor):
if indice < 0 or indice > self.tamanho:
return
atual = self.no_sentinela
for _ in range(indice):
atual = atual.proximo
novo_no = No(valor, atual.proximo)
atual.proximo = novo_no
self.tamanho += 1
def remover_no_indice(self, indice):
if indice < 0 or indice >= self.tamanho:
return
atual = self.no_sentinela
for _ in range(indice):
atual = atual.proximo
atual.proximo = atual.proximo.proximo
self.tamanho -= 1
Implementação com Lista Dupla
class NoDuplo:
def __init__(self, valor=0, anterior=None, proximo=None):
self.valor = valor
self.anterior = anterior
self.proximo = proximo
class MinhaListaDupla:
def __init__(self):
self.inicio = None
self.fim = None
self.tamanho = 0
def obter(self, indice):
if indice < 0 or indice >= self.tamanho:
return -1
if indice < self.tamanho // 2:
atual = self.inicio
for _ in range(indice):
atual = atual.proximo
else:
atual = self.fim
for _ in range(self.tamanho - indice - 1):
atual = atual.anterior
return atual.valor
def inserir_no_inicio(self, valor):
novo_no = NoDuplo(valor, None, self.inicio)
if self.inicio:
self.inicio.anterior = novo_no
else:
self.fim = novo_no
self.inicio = novo_no
self.tamanho += 1
def inserir_no_fim(self, valor):
novo_no = NoDuplo(valor, self.fim, None)
if self.fim:
self.fim.proximo = novo_no
else:
self.inicio = novo_no
self.fim = novo_no
self.tamanho += 1
def inserir_no_indice(self, indice, valor):
if indice < 0 or indice > self.tamanho:
return
if indice == 0:
self.inserir_no_inicio(valor)
elif indice == self.tamanho:
self.inserir_no_fim(valor)
else:
if indice < self.tamanho // 2:
atual = self.inicio
for _ in range(indice - 1):
atual = atual.proximo
else:
atual = self.fim
for _ in range(self.tamanho - indice):
atual = atual.anterior
novo_no = NoDuplo(valor, atual, atual.proximo)
atual.proximo.anterior = novo_no
atual.proximo = novo_no
self.tamanho += 1
def remover_no_indice(self, indice):
if indice < 0 or indice >= self.tamanho:
return
if indice == 0:
self.inicio = self.inicio.proximo
if self.inicio:
self.inicio.anterior = None
else:
self.fim = None
elif indice == self.tamanho - 1:
self.fim = self.fim.anterior
if self.fim:
self.fim.proximo = None
else:
self.inicio = None
else:
if indice < self.tamanho // 2:
atual = self.inicio
for _ in range(indice):
atual = atual.proximo
else:
atual = self.fim
for _ in range(self.tamanho - indice - 1):
atual = atual.anterior
atual.anterior.proximo = atual.proximo
atual.proximo.anterior = atual.anterior
self.tamanho -= 1
Inversão de Lista Ligada
Reverta a ordem dos nós em uma lista ligada simples, dada a referência para o primeiro nó. A lista invertida deve ser devolvida como nova cabeça.
Exemplo:
<strong>Entrada:</strong> head = [1,2,3,4,5]
<strong>Saída:</strong> [5,4,3,2,1]
Abordagem com Dois Ponteiros
Utilize dois ponteiros, um para o nó atual e outro para o nó anterior, percorrendo a lista e invertendo as referências passo a passo. Variáveis auxiliares armazenam o próximo nó temporariamente para evitar perda de conectividade.
class No:
def __init__(self, valor=0, proximo=None):
self.valor = valor
self.proximo = proximo
class Solucao:
def inverter_lista(self, head):
anterior = None
atual = head
while atual:
proximo_temp = atual.proximo
atual.proximo = anterior
anterior = atual
atual = proximo_temp
return anterior
Abordagem Recursiva
Implemente a inversão usando recursão, onde a função chama a si mesma até atingir o final da lista, então ajusta as referências durante o retorno da recursão.
class No:
def __init__(self, valor=0, proximo=None):
self.valor = valor
self.proximo = proximo
class Solucao:
def _inverter_recursivo(self, atual, anterior):
if atual is None:
return anterior
proximo_temp = atual.proximo
atual.proximo = anterior
return self._inverter_recursivo(proximo_temp, atual)
def inverter_lista(self, head):
return self._inverter_recursivo(head, None)