Invertir una lista vinculada en Python

Una lista enlazada es una estructura de datos lineales en informática que proporciona adición y eliminación de elementos en tiempo constante. Está formado por nodos.

Un solo nodo almacena algunos datos y la dirección del siguiente nodo. El siguiente nodo almacena sus datos y la dirección del siguiente nodo. Un solo nodo solo conoce el nodo al que está apuntando. No tiene información sobre los nodos que apuntan a él.

Esta estructura nos permite agregar nuevos nodos y eliminar nodos existentes en tiempo constante, dado el nodo anterior, a diferencia de los arreglos, donde tenemos que copiar un arreglo a un nuevo arreglo o cambiar los elementos de un arreglo para crear espacio para agregar y eliminar.

En las matrices, se puede acceder a los elementos en tiempo constante con la ayuda de los índices. Pero con las listas enlazadas, se tarda O(n) en acceder a un elemento, donde n es la longitud de la lista enlazada.

Dado que una lista enlazada es similar a un array en términos de estructura (lineal), también podemos realizar operaciones como ordenar, filtrar y buscar en listas enlazadas. Podemos utilizar algoritmos de clasificación y búsqueda, como la clasificación por burbujas, la clasificación por inserción, la clasificación por fusión, la clasificación rápida, la clasificación por selección, la búsqueda binaria y la búsqueda lineal en listas enlazadas.

Este artículo mostrará cómo revertir una lista enlazada usando Python. Tenga en cuenta que el fragmento de código considera una clase Node que representa un bloque de una lista vinculada.

La clase Node tendrá el siguiente aspecto.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

Invertir una lista vinculada en Python

Consulte el siguiente código de Python para invertir una lista vinculada en Python.

def reverse(head: Node) -> Node:
    previous = None
    current = head
    next = None

    while current is not None:
        next = current.next
        current.next = previous
        previous = current
        current = next

    head = previous
    return head

Para comprender el código, considere una lista enlazada de ejemplo, 1 -> 2 -> 3 -> 4 -> 5 -> None.

Primero, declaramos tres variables, previous, current y next, que apuntan a None, el encabezado de la lista enlazada de entrada, y None, respectivamente. A continuación, declaramos un bucle while que finaliza cuando el nodo current apunta a None.

Para cada iteración:

• Almacenamos el siguiente nodo del nodo current en el nodo next.
• Establecer el siguiente nodo del nodo current al nodo previous.
• Restablecer el nodo previous al nodo current.
• Restablecer el nodo current al nodo next.

La siguiente tabla representa cómo cambian los valores de las variables, a saber, previous, current y next, cuando se aplica el algoritmo para el ejemplo anterior.

Las celdas de la tabla anterior muestran el valor almacenado por un nodo.