Algoritmos de Java: fusionar k listas ordenadas (LeetCode)

Descripción de la tarea:

Se le proporciona una matriz de k listas de lists vinculadas, cada lista vinculada se ordena en orden ascendente.

Combine todas las listas vinculadas en una lista vinculada ordenada y devuélvala.

Ejemplo 1:

 Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: The linked-lists are: [ 1->4->5, 1->3->4, 2->6 ] merging them into one sorted list: 1->1->2->3->4->4->5->6

Solución:

Una lista enlazada es una estructura de datos que consiste en nodos conectados entre sí por uno (lista enlazada única) de dos punteros (lista enlazada doble). Cada nodo generalmente contiene algún valor y apunta al siguiente nodo. El primer nodo se llama Head y el último nodo se llama Tail. La cola como puntero siguiente generalmente tiene un valor nulo.

En esta tarea, estamos tratando con listas enlazadas ordenadas. Lo que significa que todos los valores en cada nodo están ordenados. Cada nodo en cada lista tiene un valor menor o igual que el valor en un nodo al que apunta. Para visualizarlo aquí hay un ejemplo de lista enlazada ordenada.

Teniendo una comprensión de lo que es la lista enlazada ordenada, podríamos resolver la versión más fácil de nuestro problema. ¿Cómo fusionarías 2 listas enlazadas ordenadas?

Y la respuesta es - extremadamente simple. Compara los encabezados de cada lista. Elija el nodo con el valor mínimo. Adjúntelo a su respuesta y ajuste el puntero al siguiente nodo en la lista de la que seleccionó un nodo. Hazlo hasta que una de las cabezas no sea igual a nula. Una vez que llegue a ese punto, simplemente puede adjuntar el resto a su respuesta.

Ahora estamos cerca de resolver el problema real. De la tarea más fácil, vemos que la clave de la solución es tomar el nodo con el valor más pequeño y adjuntarlo a la respuesta ajustando el puntero.

Teniendo una matriz de K encabezados de lista ordenados, podríamos iterarlo y cada vez elegir un nodo con el valor más pequeño. Resolvería el problema pero la complejidad del tiempo es terrible.

La mejor manera será tomar el encabezado de cada lista y agregarlo a una cola de prioridad. Priority Queue es otra estructura de datos que proporciona obtener el valor más pequeño o más grande en tiempo constante O(1). Y agregando o eliminando este valor en el tiempo O (log n), que es lo suficientemente bueno para nuestra tarea. A menudo, la cola de prioridad se denomina montón binario según la forma de almacenar elementos. Podría describirlo en un próximo artículo.

 public ListNode mergeKLists(ListNode[] lists) { if (lists == null || lists.length == 0) { return null; } ListNode dummy = new ListNode(0); ListNode prev = dummy; ListNode current; ListNode next; PriorityQueue<ListNode> minHeap = new PriorityQueue<>( Comparator.comparingInt(head -> head.val) ); for (ListNode node : lists) { if (node != null) { minHeap.add(node); } } while (!minHeap.isEmpty()) { current = minHeap.remove(); if (current == null) { continue; } next = current.next; current.next = null; prev.next = current; prev = current; if (next != null) { minHeap.add(next); } } return dummy.next; }

En la línea 8 creamos un nodo "ficticio", que será nuestro encabezado temporal. Nos ayudará a devolver fácilmente la cabeza real de las listas enlazadas ordenadas llamando a dummy.next

En las líneas 13 a 15 creamos una cola de prioridad. Necesitamos ordenar los elementos en él. Para este propósito proporcionamos Comparator.

En las líneas 17 a 23 agregamos todos los encabezados no nulos a la cola de prioridad.

En las líneas 25–42 tenemos el ciclo while principal que contiene la lógica principal.

Actualizamos el nodo actual eliminando el nodo con el valor mínimo de la parte superior de nuestra cola de prioridad. Luego actualizamos el siguiente puntero obteniendo el siguiente nodo del actual. También necesitamos actualizar el puntero anterior. Puede pensar en el puntero anterior como un puntero a la cola temporal de la lista enlazada que estamos construyendo. Y por último, pero no menos importante, si el siguiente enlace no es nulo, debemos devolverlo a la cola de prioridad.

Después de ejecutar los pasos anteriores en el ejemplo 1, obtendremos el estado representado a continuación. No lo aplané intencionalmente. Para mostrarle la transición del estado original al estado final

El algoritmo mencionado anteriormente nos da el siguiente resultado.

La complejidad de tiempo para nuestra solución es O(N log K) donde N - es el número total de nodos en todas las listas donde K - es el número de listas enlazadas ordenadas que tenemos.

La complejidad del espacio para nuestra solución es O(N) donde N - es el número total de nodos para crear una respuesta más O(K) donde K - es el número de listas enlazadas ordenadas que tenemos. De acuerdo con la notación O grande, podemos omitir O(K) porque podría ser igual o menor que O(N) en términos de varios elementos.

Espero que este artículo te haya ayudado a comprender la lógica que se esconde detrás de esta difícil tarea. ¡Gracias por leer! Esperamos sus comentarios. Hasta pronto ✌