Lista Enlazada, problemas comunes #2

🌎🧭🌝

El mundo vira sin saber donde se mete

¡Hola a todos! En este post cerramos nuestro recorrido por las listas enlazadas. Cubrimos bastante terreno, y espero que te haya quedado un buen entendimiento. Pero basta de hablar, vamos a practicar.

Si necesitas repasar algo sobre listas enlazadas, no dudes en volver a los posts anteriores. Ahora, para afianzar lo aprendido, vamos a resolver 3 problemas más de listas enlazadas.

Bueno, ¿listo para poner a prueba tus habilidades con listas enlazadas? Vamos con estos problemas.

Problema #4, encontrar el k-ésimo nodo desde el final 🛫🛬

El objetivo es encontrar el k-ésimo nodo desde el final de una lista enlazada sin calcular la longitud total de la lista. Este enfoque es más eficiente en espacio, sobre todo en listas muy largas.

Para resolver este problema vamos a usar el enfoque de los dos punteros:

1. Inicializa dos punteros: *fast: este puntero avanzará k nodos por delante al inicio. *slow: este puntero empieza en el head de la lista enlazada.

2. Mueve el puntero fast k nodos hacia adelante:

• Avanza el puntero fast k posiciones, revisando si llega al final de la lista (null). Si llega antes de dar k pasos, la lista tiene menos de k nodos, y la función puede devolver un error o None.

1. Mueve ambos punteros juntos:

• Una vez que fast está k nodos por delante, empieza a mover fast y slow un nodo a la vez.

1. slow llega al k-ésimo nodo desde el final:

• Cuando fast llega al final de la lista (null), slow estará apuntando al k-ésimo nodo desde el final de la lista enlazada.

Por qué funciona:

Para el momento en que fast llega al final, slow ya se movió k posiciones desde el head, quedando apuntando al k-ésimo nodo desde el final. Aquí el desglose de la lógica 🧐: Imagina que la lista enlazada tiene 8 nodos y quieres encontrar el 3er nodo desde el final 🛫🛬. Mueve el puntero fast 3 nodos hacia adelante (llega al 4to nodo). Ahora, empieza a mover ambos punteros juntos. Cuando fast llega al final (8vo nodo), slow estará en el 5to nodo (que es el 3er nodo desde el final).

Código

class LinkedList:

    #   previous code

    def find_kth_from_end(self, k) -> any:
        """
        This method return the Kth node from the end of the linked list

        Return
            Node
        """
        slow = fast = self.head

        for _ in range(k):
            if fast is None:
                return None
            fast = fast.next

        while fast:
            slow = slow.next
            fast = fast.next

        return slow

Problema #5, eliminar duplicados de una lista enlazada 💼

Vamos a ver cómo eliminar nodos duplicados de una lista enlazada simple que contiene enteros. Lo lograremos usando un set, que ofrece búsquedas eficientes para saber si ya vimos un elemento.

Enfoque:

1. Inicializa un set vacío: este set guardará los valores únicos vistos hasta el momento mientras recorremos la lista enlazada.

2. Recorre la lista enlazada: usa un loop para recorrer cada nodo de la lista.

3. Revisa duplicados en el set:

• Para el nodo actual, revisa si su valor ya existe en el set.

• Si el valor no está en el set, es único. Añade ese valor al set y pasa al siguiente nodo.

• Si el valor está en el set, es un duplicado. En ese caso, elimina el nodo duplicado actual. A esta altura ya sabes cómo eliminar un nodo, así que nos saltamos la explicación en este post.

Ventajas de usar un Set 🦖:

• Búsquedas eficientes 🔬: los sets ofrecen búsquedas en tiempo constante, lo que hace eficiente revisar duplicados.

• Complejidad espacial ⏱️: el set suele usar espacio proporcional a la cantidad de elementos únicos encontrados, lo que lo hace eficiente en espacio cuando hay muchos duplicados.

Código

class LinkedList:

    #   previous code

    def remove_duplicates(self):
        """
        This method detect if the linked list contain a loop

        Return
            Bool
        """
        values = set()
        previus = None
        current = self.head

        while current:
            if current.value in values:
                previus.next = current.next
                self.length -= 1
            else:
                values.add(current.value)
                previus = current
            current = current.next

Problema #6, eliminar duplicados de una lista enlazada 💼

¡El último! 🍾

Implementa un método llamado reverse_between dentro de una clase de lista enlazada. Este método recibe dos enteros, start_index y end_index, como argumentos. Su tarea es invertir el orden de los nodos en la lista enlazada, comenzando en el nodo con índice start_index y terminando en el nodo con índice end_index (inclusive).

Enfoque:

1. Caso base: revisa si la lista tiene menos de dos elementos (length <= 1) y sale si es así, porque no hay nada que invertir.

2. Nodo auxiliar: crea un help_node temporal con valor 0 y pone su puntero next apuntando al head de la lista real. Este nodo ayuda a mantener el inicio de la parte no invertida.

3. Recorre hasta el índice de inicio: usa un loop para avanzar start_index veces con previous_node hasta llegar al nodo anterior a la posición donde empieza la inversión.

4. Nodo actual: pone current_node en el nodo del índice de inicio (el que se va a invertir).

5. Invierte la sublista: recorre (end_index - start_index veces) para invertir la porción de la lista enlazada entre start_index y end_index:

• node_to_move: guarda el siguiente nodo del nodo actual.

• current_node.next: apunta al nodo después de la sección invertida.

• node_to_move.next: se pone igual al previous_node.next actual, para insertar el nodo movido al inicio de la porción invertida.

• previous_node.next: se pone igual a node_to_move para actualizar el punto de inicio de la porción invertida.

1. Actualiza el head: por último, actualiza el head de la lista para que apunte a help_node.next, que ahora es el inicio de toda la lista después de la inversión.

Código

class LinkedList:

    #   previous code

    def reverse_between(self, start_index, end_index):
        """
        This method reverse elements between a start and end index

        Return
            None
        """

        if self.length <= 1:
            return

        help_node       = Node(0)
        help_node.next  = self.head
        previous_node   = help_node

        for _ in range(start_index):
            previous_node.next

        current_node = previous_node.next

        for _ in range(end_index - start_index):
            node_to_move        = current_node.next
            current_node.next   = node_to_move.next
            node_to_move.next   = previous_node.next
            previous_node.next  = node_to_move

        self.head = help_node.next

La canción del post

Terminamos una sección del blog, y para celebrarlo hay que poner una de mis canciones favoritas de todos los tiempos.

🌎🧭🌝

Una tormenta solar
Quemándonos el costado
Moviéndonos hasta lograr
No estar en ningún lado
La luna, la luna
La luna que guía y encandila
Y el corazón que finge decisión
Pero vacila.
La noche cumple solo lo que no promete
La brújula se mueve
Estamos en 1987
Reír y reír y reír
En el eco del abismo
La lógica de confundir
Espejo y espejismo
La luna, la luna,
La luna lamiéndonos la fiebre
Y el corazón que solo se encuentra
Si antes se pierde.
El mundo vira sin saber donde se mete
La brújula se mueve
Estamos en 1987
· 1987, Campo ft. Jorge Drexler