Invertir una lista enlazada en python

Me piden que invierta un que toma cabeza como parámetro donde como cabecera es una lista vinculada, por ejemplo: 1 -> 2 -> 3 que fue devuelto desde una función ya definida. Intenté implementar la función reverse_linked_list de esta manera:

def reverse_linked_list(head): temp = head head = None temp1 = temp.next temp2 = temp1.next temp1.next = None temp2.next = temp1 temp1.next = temp return temp2 pass class Node(object): def __init__(self,value=None): self.value = value self.next = None def to_linked_list(plist): head = None prev = None for element in plist: node = Node(element) if not head: head = node else: prev.next = node prev = node return head def from_linked_list(head): result = [] counter = 0 while head and counter < 100: # tests don't use more than 100 nodes, so bail if you loop 100 times. result.append(head.value) head = head.next counter += 1 return result def check_reversal(input): head = to_linked_list(input) result = reverse_linked_list(head) assert list(reversed(input)) == from_linked_list(result) 

Se llama de esta manera: check_reversal([1,2,3]) . La función que he escrito para revertir la lista está dando [3,2,1,2,1,2,1,2,1] y funciona solo para una lista de longitud 3. ¿Cómo puedo generalizarla para una lista de longitud? n ?

U puede usar la función mod para obtener el rest de cada iteración y obviamente ayudará a revertir la lista. Creo que eres un estudiante de Mission R y D

 head=None prev=None for i in range(len): node=Node(number%10) if not head: head=node else: prev.next=node prev=node number=number/10 return head 

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 se realizó esta tarea es probablemente hace mucho tiempo, publicaré lo que creo que es el código más efectivo.

Esto es para hacer una reversió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, lo que puede ser un poco más fácil 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 luché por entender lo que realmente estaba sucediendo, debido principalmente a la syntax de Python que permite el intercambio de dos variables en una línea. También encontré los nombres de las variables un poco confusos.

En este ejemplo uso previous, current, next .

  def reverse(head): current = head previous = None while current: next = current.next current.next = previous # None, first time round. previous = current # Used in the next iteration. current = next # 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 ingresar al bucle while por primera vez, el inicial se inicializa a None porque no hay ningún nodo antes del encabezado ( n1 ).

Me pareció útil imaginar las variables previous, current, next “moviéndose a lo largo” de la lista vinculada, siempre en ese orden.

Primera iteración

previous = None

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

Segunda iteración

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

Tercera iteración

 # next is None 

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

Dado que el bucle while sale cuando está current == None el nuevo encabezado de la lista debe configurarse como previous que es el último nodo que visitamos.

Aquí hay una manera de revertir 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 propósitos de animación)

introduzca la descripción de la imagen aquí

Parte de clase de nodo prestada de python.org interactivo: http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html

Creé la función invertida. Todos los comentarios en el bucle de retroceso significaron para bucles por primera vez. Entonces continúa.

 class Node(): def __init__(self,initdata): self.d = initdata self.next = None def setData(self,newdata): self.d = newdata def setNext(self,newnext): self.next = newnext def getData(self): return self.d def getNext(self): return self.next class LinkList(): def __init__(self): self.head = None def reverse(self): current = self.head >>> set current to head(start of node) previous = None >>> no node at previous while current !=None: >>> While current node is not null, loop nextt = current.getNext() >>> create a pointing var to next node(will use later) current.setNext(previous) >>> current node(or head node for first time loop) is set to previous(ie NULL), now we are breaking the link of the first node to second node, this is where nextt helps(coz we have pointer to next node for looping) previous = current >>> just move previous(which was pointing to NULL to current node) current = nextt >>> just move current(which was pointing to head to next node) self.head = previous >>> after looping is done, (move the head to not current coz current has moved to next), move the head to previous which is the last node. 

Probé un enfoque diferente, en lugar de reversión de la lista. Dada una lista 1,2,3,4

Si cambias sucesivamente los nodos cercanos, obtendrás la solución.

 len=3 (size-1) 2,1,3,4 2,3,1,4 2,3,4,1 len=2 (size-2) 3,2,4,1 3,4,2,1 len=1 (size-3) 4,3,2,1 

El código de abajo hace justamente eso. Outer for loop reduce sucesivamente el len de la lista para intercambiar. Mientras que el bucle intercambia los elementos de datos de los nodos.

 def Reverse(head): temp = head llSize = 0 while temp is not None: llSize += 1 temp = temp.next for i in xrange(llSize-1,0,-1): xcount = 0 temp = head while (xcount != i): temp.data, temp.next.data = temp.next.data, temp.data temp = temp.next xcount += 1 return head 

Esto podría no ser tan eficiente como otras soluciones, pero ayuda a ver el problema desde una perspectiva diferente. Espero que encuentres esto útil.

Aquí está toda la cosa en una hoja. Contiene la creación de una lista vinculada y un código para revertirla.

Incluye un ejemplo para que pueda copiar y pegar en un archivo .py inactivo y ejecutarlo.

 class Node(object): def __init__(self, value, next=None): self.value = value self.next = next def reverse(head): temp = head llSize = 0 while temp is not None: llSize += 1 temp = temp.next for i in xrange(llSize-1,0,-1): xcount = 0 temp = head while (xcount != i): temp.value, temp.next.value = temp.next.value, temp.value temp = temp.next xcount += 1 return head def printnodes(n): b = True while b == True: try: print n.value n = n.next except: b = False n0 = Node(1,Node(2,Node(3,Node(4,Node(5,))))) print 'Nodes in order...' printnodes(n0) print '---' print 'Nodes reversed...' n1 = reverse(n0) printnodes(n1) 
 def reverseLinkedList(head): current = head previous = None nextNode = None while current: nextNode = current.nextNode current.nextNode = previous previous = current current = nextNode return previous 

La mayoría de las respuestas anteriores son correctas, pero ninguna de ellas tenía el código completo, incluido el método de inserción antes y después del reverso, por lo que realmente podía ver las salidas y comparar. Es por eso que estoy respondiendo a esta pregunta. La parte principal del código, por supuesto, es el método reverse_list (). Esto está en Python 3.7 por cierto.

 class Node(object): def __incurrent__(self, data=None, next=None): self.data = data self.next = next class LinkedList(object): def __incurrent__(self, head=None): self.head = head def insert(self, data): tmp = self.head self.head = Node(data) self.head.next = tmp def reverse_list(self): current = self.head prev = None while current : #create tmp to point to next tmp = current.next # set the next to point to previous current.next = prev # set the previous to point to current prev = current #set the current to point to tmp current = tmp self.head = prev def print(self): current = self.head while current != None: print(current.data,end="-") current = current.next print(" ") lk = LinkedList() lk.insert("a") lk.insert("b") lk.insert("c") lk.print() lk.reverse_list() lk.print() 

salida:

 cba- abc-