¿Cómo purgar una lista vinculada en $ mathcal {o} (n log n) $ time?

Question

Me preguntaba cómo eliminar los valores duplicados de una lista vinculada en $ mathcal {o} (n lg n) $ time. Tengo la idea de que al usar la clasificación de fusiones cuando queremos comparar elementos para elegir el pequeño, si son igual avanzados en el puntero y solo considere un elemento. ¿Alguna alternativa?

Answer 1

1. Ordene la lista vinculada en $ o (n log n) $ time.
2. Realice cada elemento de la lista en su pedido y elimine el elemento, si es el mismo que el anterior en $ o (n) $ tiempo.

La complejidad total es $ O (n log n) $, que es lo que está buscando.

Answer 2

Puede hacerlo en $ o (n) $ de la siguiente manera.

1) Construya una tabla hash atravesando la lista vinculada y agregando sus elementos a la tabla hash. En cada iteración, busque en la tabla hash para el elemento actual que se considera en la iteración. Si no se encuentra el elemento, agregue a la tabla hash el valor del elemento como la clave y 1 como el valor correspondiente. Si en su lugar encuentra el elemento (que se ha insertado en una iteración anterior), simplemente agregue 1 al valor correspondiente y actualice la entrada de tabla hash (actualizando correctamente la multiplicidad del elemento). Al final, su tabla hash contendrá como máximo las entradas de $ n $ (esto corresponde al caso de que el elemento en la lista vinculada es distinto), o menos de $ n $ elementos, con al menos una de las entradas que muestran una multiplicidad mayor que uno. Esto lleva $ o (n) $ tiempo ya que en cada una de las $ n $ iteraciones, el trabajo realizado en la tabla hash es $ o (1) $.

2) Ahora, atraviese la tabla hash y cree una nueva lista vinculada agregando un nodo para cada elemento encontrado. Esto toma como máximo $ o (n) $ ya que la tabla hash contiene como máximo $ n $ elementos, el trabajo realizado en cada elemento de la tabla hash es $ o (1) $ y agregar un nodo a la nueva lista toma $ O (1) $.

Por lo tanto, la complejidad total es como máximo $ o (n) $.