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

Questão

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 mover todos os elementos com valor par para o início da lista, preservando a ordem relativa dos pares entre si e dos ímpares entre si (estabilidade). Use variáveis explícitas, não aloque novos nós e indique complexidade temporal e espacial.

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

Resposta esperada

Pseudocódigo: função partition_pares_estavel(head): if head == nulo: retorne head even_head = nulo; even_tail = nulo odd_head = nulo; odd_tail = nulo atual = head enquanto atual != nulo: proximo = atual.proximo atual.proximo = nulo se (atual.valor % 2) == 0: se even_head == nulo: even_head = atual; even_tail = atual senão: even_tail.proximo = atual even_tail = atual senão: se odd_head == nulo: odd_head = atual; odd_tail = atual senão: odd_tail.proximo = atual odd_tail = atual atual = proximo // concatenar listas mantendo estabilidade se even_head != nulo: even_tail.proximo = odd_head retorne even_head senão: retorne odd_head Explicação e justificativa do projeto: - Variáveis usadas: atual, proximo (iteração); even_head/even_tail para sublista de pares; odd_head/odd_tail para sublista de ímpares. - Invariante durante o laço: nós já visitados estão repartidos em duas sublistas (pares e ímpares), cada sublista preservando a ordem original. - Não são alocados novos nós; apenas ajustam-se ponteiros .proximo, logo o algoritmo é in-place no sentido de não criar nós adicionais. - Complexidade temporal: percorre a lista uma vez ? O(n). - Complexidade espacial extra: utiliza um número constante de ponteiros ? O(1) espaço extra. - Casos de borda: lista vazia, todos pares, todos ímpares, único nó; o pseudocódigo trata esses casos naturalmente. Observação: mantém estabilidade porque novos nós são sempre anexados no final das sublistas na ordem em que são visitados.

Explicação

O algoritmo separa os nós em duas sublistas, uma para pares e outra para ímpares, preservando a ordem original de cada grupo ao anexar novos nós ao final das sublistas. Ele opera in-place, ajustando apenas os ponteiros sem criar novos nós, o que garante eficiência em termos de espaço. A complexidade temporal é linear, pois percorre a lista uma vez, e a complexidade espacial é constante, utilizando um número fixo de ponteiros.

Raio-X da questão

Questões parecidas com resolução

• Crie e descreva um algoritmo, em linguagem simples ou pictográfica, que ajude uma criança a decidir se deve levar um…
• Crie um algoritmo em linguagem oral ou escrita que controle a rega de um vaso por 7 dias: diariamente verificar se…
• Projete em pseudocódigo um algoritmo que reconstrua uma mensagem a partir de pacotes recebidos onde cada pacote contém…
• Elabore em pseudocódigo um algoritmo que, dado um vetor de registros 'tarefas' (descricao, duracao_horas, prioridade) e…
• Elabore em pseudocódigo um algoritmo que, dado um array de registros 'alunos' com campos (nome, notas[4]…
• Projete um algoritmo e descreva as estruturas de dados para implementar operações de desfazer/refazer (undo/redo) em um…

Todas as questões de Algoritmos