Projete um algoritmo, em pseudocódigo, que receba uma lista ligada simples L com n nós e remova todos os nós…

Questão

Projete um algoritmo, em pseudocódigo, que receba uma lista ligada simples L com n nós e remova todos os nós cujos valores aparecem mais de uma vez (manter apenas valores que ocorrem exatamente uma vez). Descreva estruturas auxiliares, passos e analise complexidade temporal e espacial.

✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.

Resposta esperada

1) Estrutura auxiliar: dicionário (hash map) counts que mapeia valor -> frequência. 2) 1ª passagem: percorrer L e para cada nó counts[val]++ (O(n) tempo). 3) 2ª passagem: usar ponteiro prev=null, cur=L.head; para cada cur: se counts[cur.val]>1 então remover cur ajustando prev.next; senão prev=cur; avançar cur (remover atual cuida de liberar nó). Isso é O(n) tempo adicional. 4) Complexidade: tempo O(n), espaço O(n) para o hash map; operação in-place na lista quanto à reorganização de ponteiros, sem copiar todos os nós. Pseudocódigo resumido: counts = {}; for node in L: counts[node.val] += 1; prev = null; cur = L.head; while cur != null: if counts[cur.val] > 1: if prev == null: L.head = cur.next else prev.next = cur.next cur = cur.next else: prev = cur; cur = cur.next Observações: se restrição de espaço proibir estrutura auxiliar, pode-se ordenar os valores ou usar algoritmo quadrático de comparação par a par; isso aumenta tempo para O(n^2) e evita espaço extra.

Explicação

A solução proposta utiliza um dicionário para contar a frequência de cada valor na lista, permitindo identificar quais devem ser removidos em uma segunda passagem. A abordagem é eficiente, com complexidade de tempo linear, já que cada nó é percorrido duas vezes, e a complexidade espacial é linear devido ao armazenamento das frequências. Além disso, a manipulação da lista é feita in-place, evitando a necessidade de estruturas auxiliares adicionais, exceto o dicionário.

Raio-X da questão

Questões parecidas com resolução

• Projete um algoritmo em pseudocódigo que receba uma lista L de n inteiros (com repetições possíveis) e retorne uma nova…
• Projete um algoritmo, em pseudocódigo, que receba uma lista ligada simples L com n nós e reorganize os nós in-place para…
• Projete um algoritmo em pseudocódigo que receba uma lista L de n inteiros e retorne uma nova lista em que todos os…
• Projete um algoritmo em pseudocódigo que remova duplicatas de uma lista de registros usando uma tabela hash; descreva a…
• Projete em pseudocódigo uma função recursiva remover_unicos(L) que recebe uma lista L de inteiros e retorna uma nova…
• Projete em pseudocódigo um algoritmo que receba uma lista de nomes de alunos (dados) e retorne a mesma lista sem…

Todas as questões de Algoritmos