Lista Enlazada, problemas comunes #1

Hola. Hemos aprendido bastante sobre listas enlazadas. Creo que es hora de poner este conocimiento en práctica. ¿Por qué hacemos esto? 🤔. Es fácil, resolviendo problemas comunes.

Problema #1, invertir una lista enlazada ↩️

Este problema es muy común en muchas entrevistas de trabajo, y el concepto es fácil de entender. Consiste en cambiar la dirección de la referencia de cada nodo hacia el anterior, es decir, invertir la lista enlazada 🤌, podría haber dicho eso desde el principio y ahorrarme muchas palabras. Para invertir una lista enlazada seguimos unos pasos específicos.

Solución

1. Crea una referencia temporal al head actual de la lista enlazada, esta referencia sería una variable llamada temp.

2. Cambia la referencia del tail al head, y del head al tail.

3. Establece dos nuevas variables:

• La variable “after” apuntará a la siguiente referencia de la variable temp. Esta variable nos ayuda a seguir recorriendo la lista después de cambiar la referencia hacia el nodo anterior. ¿Ves por qué se llama after? 😎.

• La variable “before” apuntará al nodo anterior para cambiar la referencia del .next hacia el nodo temp. Cuando declaramos la variable before, le damos el valor None.

1. Recorre la lista enlazada, y en este punto es donde empieza la magia. Los siguientes pasos hay que seguirlos al pie de la letra.

• Pon la variable after apuntando a temp.next.

• Pon la referencia de temp.next hacia “before”.

• Pon la referencia de before hacia temp.

• Pon la referencia de temp hacia “after”. Y eso es todo. Para entender mejor el proceso que acabamos de describir, mira la siguiente imagen.

Código

class LinkedList:

    #   previous code

	def reverse(self) -> None:
        """
        Invert the order of the linked list

        Return
            None
        """
        temp        = self.head
        self.head   = self.tail
        self.tail   = temp
        after       = temp.next
        before      = None
        for _ in range(self.length):
            after       = temp.next
            temp.next   = before
            before      = temp
            temp        = after

Problema #2, encontrar el nodo del medio 🔢

Este problema consiste en devolver el nodo del medio de una lista enlazada sin usar el atributo length de nuestra clase. Si la lista enlazada tiene un número par de nodos, debemos devolver el primer nodo de la segunda mitad de la lista.

Solución

Antes de describir los pasos de la solución, hay que entender el enfoque que vamos a usar para encontrar el nodo del medio. Imagina que tienes 2 carros en una carrera, el primero lo llamamos “rápido” y el segundo “lento”. El carro rápido avanza el doble de rápido que el segundo. Para resumir la historia, es obvio que el carro “rápido” llegará primero a la meta, y en el momento en que el carro rápido alcance al carro lento, este estará en la mitad del camino. Espero que se entienda ✌️. Así que convirtamos esta “historia solución” en código.

Crea dos variables:

• Slow. Esta variable referenciará el head de la lista enlazada.

• Fast. Esta variable referenciará 2 nodos por delante de slow. Si el head de la lista enlazada es None, devuelve None. Recorre la lista enlazada hasta que la variable fast referencie None. Cuando fast referencie None, devuelve la variable slow.

Para tener una mejor idea de lo que estamos haciendo, mira la siguiente imagen:

Código

class LinkedList:

    #   previous code

	def find_middle_node(self) -> any:
        """
        Return the middle node of a linked list.
        If the linked list has an even number of nodes,
        return the first node of the second half of the list.

        Return
            Any
        """
        slow = self.head
        fast = self.head.next

        if self.head == None:
            return None

        while fast is not None:

            slow = slow.next
            fast = fast.next

            if fast is None:
                return slow

            fast = fast.next

        return slow

Problema #3, ¿la lista enlazada tiene un ciclo? 🤔 🔄

Crea un método que detecte la presencia de un ciclo en una lista enlazada usando el algoritmo de detección de ciclos de Floyd, también conocido como el algoritmo de “la tortuga y la liebre”.

Solución

El enfoque de esta solución es parecido al del problema anterior. Establecemos 2 variables, slow y fast. Fast se mueve 2 nodos por delante de slow. Si la lista enlazada no tiene ciclo, en algún momento fast llegará a None. Si la lista enlazada tiene un ciclo, en algún momento las referencias de slow y fast recorrerán la lista y estas dos variables apuntarán al mismo nodo. En ese punto detectamos el ciclo 🪤.

Vamos al código:

Código

class LinkedList:

    #   previous code

	def has_loop(self) -> bool:
        """
        This method detect if the linked list contain a loop

        Return
            Bool
        """

        slow = self.head
        fast = self.head.next

        if self.head == None:
            return False

        while fast is not None and fast.next is not None:

            slow = slow.next
            fast = fast.next.next

            if fast == slow:
                return True

        return False

La canción del post

Ahí vamos
Déjame atravesar el viento sin documentos
Que lo haré por el tiempo que tuvimos
Porque no queda salida, porque pareces dormida
Porque buscando tu sonrisa estaría toda mi vida
· Sin Documentos, Los Rodríguez