eeliminar repeticoes em listas ligadas

[suzy]

malta

é o seguinte, tenho uam lista ligada simples, e quero eliminar os nomes que se repetem.

ora bem, á medida que vou percorrendo a lista ligada, tenho de comparar de o nome do no inicial com os nomes dos outros nós se for igual elimina, sendo assim em cada iteracção.

é assim o raciocionio??

obrigada

[falk0n]

penso que o que estas a dizer irá ter uma complexidade de O(n^2).

se tiveres hipotese de teres feito uma hashtable, iria iterando a lista e inserindo na hashtable qdo existisse uma colisão e em que o valor fosse igual ao valor da lista retiraria esse valor da lista, depois de iterar toda a lista apagaria a hashtable da memoria e assim com uma complexidade O(n) conseguiria fazer esse processo, ter  uma lista sem repeticoes.

se não interessa a complexidade do algoritmo, penso que sim possas fazer dessa maneira.

boas programacoes

[QuickFire]

Outra solução simples seria manipular a forma como inseres na lista, podes inserir já de acordo com o teu problema.

Claro que ias ficar com uma inserção mais cara, mas poupas no resto.

Mas pessoalmente penso que ia para uma hashtable também...

[TheDark]

malta

é o seguinte, tenho uam lista ligada simples, e quero eliminar os nomes que se repetem.

ora bem, á medida que vou percorrendo a lista ligada, tenho de comparar de o nome do no inicial com os nomes dos outros nós se for igual elimina, sendo assim em cada iteracção.

é assim o raciocionio??

obrigada

Acho que estás correcta. Em cada iteração tens 2 apontadores: o primeiro percorre os nós da lista um a um, a partir do 1º nó, e o segundo percorre-os também um a um, mas a partir do nó seguinte ao apontado pelo primeiro apontador. Depois é só compará-los, como disseste.

falk0n e QuickFire: tenho quase a certeza que a ajuda que ela está a pedir é para um trabalho escolar, e que tem que usar unicamente a estrutura indicada 😄

[Triton]

Bem, há 3 dias tinha um projecto para entregar que percorria uma lista toda à procura de duplicados no momento da inserção, e demorava 2 minutos num caso teste que tinha de passar em menos de 10 segundos. No meu caso estava a fazer sort da lista antes de fazer output, e o que fiz foi no momento do output, testar se o valor do elemento da lista actual era igual ao seguinte. Só com esta optimização o código passou a resolver o caso mais lento em 2 segundos. 😄

[nata79]

o raciocinio da suzy penso k tá correcto mas tb é sempre bom ler outras soluções... eu nesse caso o k faria era, partindo do principio que a inserção é feita por ti, manipula-la de forma a nao inserir conteudos repetidos. se a lista tiver ordenada axo k até é relativamente eficiente e facil de implementar...