Cómo colocar un nodo de una lista enlazada de listas en un montón en Python.
Creo que el título es más confuso que la propia descripción del problema. Aquí está:
Tengo una lista de listas ligadas en Python, que se ve algo así como “listas = [[1,4,5],[1,3,4],[2,6]]”, y un nodo de lista ligada se define como:
class ListNode:
def init(self, val=0, next=None):
self.val = val
self.next = siguiente
En el problema que intento resolver, el primer paso es poner un primer elemento de cada lista en un montón. Aquí está mi código para ello:
mylist1 = ListNode(1, ListNode(4, ListNode(5)))
mylist2 = ListNode(1, ListNode(3, ListNode(4)))
listas = [mylist1, mylist2]
import heapq
heap = []
for l in listas:
heapq.heappush(heap, (l.val, l))
Cuando ejecuto este código, obtengo una excepción siguiente:
Exception
Creo que entiendo lo que está sucediendo allí, Python trata “l” no como un solo nodo, sino como una lista completa. Entonces mi pregunta es, ¿cómo puedo poner un primer nodo de cada lista en un montón en Python? Siento que la respuesta es bastante simple, pero me falta algo importante.
EDICIÓN
Estoy tratando de resolver este problema, https://leetcode.com/problems/merge-k-sorted-lists/. El enfoque es usar un montón, pero no quiero insertar todos los elementos en él, lo que quiero hacer es insertar los primeros elementos de cada lista, encontrar el elemento mínimo, luego insertar el siguiente elemento de la lista que tenga el mínimo y así sucesivamente hasta que pase por todos los elementos.
davy.ai
El problema con la implementación actual es que estás tratando de almacenar toda la lista enlazada en el montículo en lugar de sólo el primer nodo. Para solucionarlo, puedes modificar el bucle para almacenar en el montículo la tupla del valor y el primer nodo:
Este bucle comprueba si la lista enlazada no está vacía antes de agregar el primer nodo al montículo. Esto evita errores si tienes una lista enlazada vacía en la lista de
lists.La función
heapq.heapify()convierte la lista en un montículo in situ. A partir de aquí, puedes extraer el elemento más pequeño del montículo, que siempre será el primer elemento de una de las listas enlazadas, e insertar el siguiente elemento de esa lista enlazada en el montículo.