Saltar al contenido

Invertir una lista vinculada en Python

Tenemos la solución a este atolladero, o por lo menos eso esperamos. Si tienes interrogantes coméntalo, que con gusto te responderemos

Solución:

La respuesta aceptada no tiene ningún sentido para mí, ya que se refiere a un montón de cosas que no parecen existir (number, node, len como un número en lugar de una función). Dado que la tarea para la que esto fue probablemente ya pasó, publicaré lo que creo que es el código más efectivo.

Esto es para hacer una inversión destructiva, donde modifica los nodos de lista existentes:

def reverse_list(head):
    new_head = None
    while head:
        head.next, head, new_head = new_head, head.next, head # look Ma, no temp vars!
    return new_head

Una implementación menos sofisticada de la función usaría una variable temporal y varias declaraciones de asignación, que pueden ser un poco más fáciles de entender:

def reverse_list(head):
    new_head = None  # this is where we build the reversed list (reusing the existing nodes)
    while head:
        temp = head  # temp is a reference to a node we're moving from one list to the other
        head = temp.next  # the first two assignments pop the node off the front of the list
        temp.next = new_head  # the next two make it the new head of the reversed list
        new_head = temp
    return new_head

Un diseño alternativo sería crear una lista completamente nueva sin cambiar la anterior. Esto sería más apropiado si desea tratar los nodos de la lista como objetos inmutables:

class Node(object):
    def __init__(self, value, next=None): # if we're considering Nodes to be immutable
        self.value = value                # we need to set all their attributes up
        self.next = next                  # front, since we can't change them later

def reverse_list_nondestructive(head):
    new_head = None
    while head:
        new_head = Node(head.value, new_head)
        head = head.next
    return new_head

Encontré la respuesta de blckknght útil y ciertamente es correcta, pero me costó entender qué estaba sucediendo realmente, debido principalmente a que la sintaxis de Python permite intercambiar dos variables en una línea. También encontré los nombres de las variables un poco confusos.

En este ejemplo utilizo previous, current, tmp.

def reverse(head):
    current = head
    previous = None

    while current:
        tmp = current.next
        current.next = previous   # None, first time round.
        previous = current        # Used in the next iteration.
        current = tmp             # Move to next node.

    head = previous

Tomando una lista enlazada individualmente con 3 nodos (cabeza = n1, cola = n3) como ejemplo.

n1 -> n2 -> n3

Antes de entrar al while bucle por primera vez, previous se inicializa a None porque no hay ningún nodo antes de la cabeza (n1).

Me resultó útil imaginar las variables previous, current, tmp ‘moviéndose a lo largo’ de la lista enlazada, siempre en ese orden.

Primera iteración

previous = None

[n1] -> [n2] -> [n3]
current tmp
current.next = previous

Segunda iteración

[n1] -> [n2] -> [n3]
previous current tmp
current.next = previous

Tercera iteración

# next is None

[n1] -> [n2] -> [n3]
previous current
current.next = previous

Desde el while el bucle sale cuando current == None el nuevo encabezado de la lista debe establecerse en previous que es el último nodo que visitamos.

Editado

Agregar un ejemplo de trabajo completo en Python (con comentarios y útiles str representaciones). Estoy usando tmp en vez de next porque next es una palabra clave. Sin embargo, creo que es un nombre mejor y hace que el algoritmo sea más claro.

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

    def __str__(self):
        return str(self.value)

    def set_next(self, value):
        self.next = Node(value)
        return self.next


class LinkedList:
    def __init__(self, head=None):
        self.head = head

    def __str__(self):
        values = []
        current = self.head
        while current:
            values.append(str(current))
            current = current.next

        return ' -> '.join(values)

    def reverse(self):
        previous = None
        current = self.head

        while current.next:
            # Remember `next`, we'll need it later.
            tmp = current.next
            # Reverse the direction of two items.
            current.next = previous
            # Move along the list.
            previous = current
            current = tmp

        # The loop exited ahead of the last item because it has no
        # `next` node. Fix that here.
        current.next = previous

        # Don't forget to update the `LinkedList`.
        self.head = current


if __name__ == "__main__":

    head = Node('a')
    head.set_next('b').set_next('c').set_next('d').set_next('e')

    ll = LinkedList(head)
    print(ll)
    ll.revevse()
    print(ll)

Resultados

a -> b -> c -> d -> e
e -> d -> c -> b -> a

Aquí hay una forma de invertir la lista “en su lugar”. Esto se ejecuta en tiempo constante O (n) y utiliza cero espacio adicional.

def reverse(head):
  if not head:
    return head
  h = head
  q = None
  p = h.next
  while (p):
    h.next = q
    q = h
    h = p
    p = h.next
  h.next = q
  return h

Aquí hay una animación para mostrar el algoritmo en ejecución.
(# simboliza Nulo / Ninguno para fines de animación)

ingrese la descripción de la imagen aquí

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *