Dado k listas vinculadas, cada una de tamaño n y cada lista está ordenada en orden no decreciente, combínelas en una sola lista vinculada ordenada (orden no decreciente) e imprima la lista vinculada ordenada como salida.
Ejemplos:
Input: k = 3, n = 4 list1 = 1->3->5->7->NULL list2 = 2->4->6->8->NULL list3 = 0->9->10->11->NULL Output: 0->1->2->3->4->5->6->7->8->9->10->11 Merged lists in a sorted order where every element is greater than the previous element. Input: k = 3, n = 3 list1 = 1->3->7->NULL list2 = 2->4->8->NULL list3 = 9->10->11->NULL Output: 1->2->3->4->7->8->9->10->11 Merged lists in a sorted order where every element is greater than the previous element.
Fuente: Merge K sorted Linked Lists | Método 2
Una solución eficiente para el problema se ha discutido en el Método 3 de esta publicación.
Enfoque: esta solución se basa en el enfoque MIN HEAP utilizado para resolver el problema ‘combinar k arrays ordenadas’ que se analiza aquí .
MinHeap: un Min-Heap es un árbol binario completo en el que el valor de cada Node interno es menor o igual que los valores de los elementos secundarios de ese Node. Asignar los elementos de un montón a una array es trivial: si un Node se almacena en el índice k, entonces su hijo izquierdo se almacena en el índice 2k + 1 y su hijo derecho en el índice 2k + 2.
- Cree un montón mínimo e inserte el primer elemento de todas las listas vinculadas ‘k’.
- Siempre que el montón mínimo no esté vacío, realice los siguientes pasos:
- Elimine el elemento superior del montón mínimo (que es el mínimo actual entre todos los elementos del montón mínimo) y agréguelo a la lista de resultados.
- Si existe un elemento (en la misma lista vinculada) junto al elemento que apareció en el paso anterior, insértelo en el montón mínimo.
- Devuelve la dirección del Node principal de la lista fusionada.
A continuación se muestra la implementación del enfoque anterior:
Javascript
<script>
// Javascript implementation to merge
// k sorted linked lists using MIN HEAP method
class Node
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
// Function to merge k sorted
// linked lists
function mergeKSortedLists(arr, k)
{
let head = null, last = null;
// priority_queue 'pq' implemeted
// as min heap with the help of
// 'compare' function
let pq = [];
// Push the head nodes of all
// the k lists in 'pq'
for (let i = 0; i < k; i++)
if (arr[i] != null)
pq.push(arr[i]);
pq.sort(function(a, b)
{
return a.data - b.data;
});
// loop till 'pq' is not empty
while (pq.length != 0)
{
// Get the top element of 'pq'
let top = pq[0];
pq.shift();
// Check if there is a node next
// to the 'top' node in the list
// of which 'top' node is a member
if (top.next != null)
// Push the next node in 'pq'
pq.push(top.next);
// if final merged list is empty
if (head == null)
{
head = top;
// Points to the last node so far
// of the final merged list
last = top;
}
else
{
// Insert 'top' at the end of the
// merged list so far
last.next = top;
// Update the 'last' pointer
last = top;
}
pq.sort(function(a,b){return a.data-b.data;});
}
// Head node of the required merged list
return head;
}
// Function to print the singly linked list
function printList(head)
{
while (head != null)
{
document.write(head.data + " ");
head = head.next;
}
}
// Utility function to create a
// new node
function push(data)
{
let newNode = new Node(data);
newNode.next = null;
return newNode;
}
// Driver code
// Number of linked lists
let k = 3;
// Number of elements in each list
let n = 4;
// An array of pointers storing the
// head nodes of the linked lists
let arr = new Array(k);
arr[0] = new Node(1);
arr[0].next = new Node(3);
arr[0].next.next = new Node(5);
arr[0].next.next.next = new Node(7);
arr[1] = new Node(2);
arr[1].next = new Node(4);
arr[1].next.next = new Node(6);
arr[1].next.next.next = new Node(8);
arr[2] = new Node(0);
arr[2].next = new Node(9);
arr[2].next.next = new Node(10);
arr[2].next.next.next = new Node(11);
// Merge all lists
let head = mergeKSortedLists(arr, k);
printList(head);
// This code is contributed by avanitrachhadiya2155
</script>
Producción:
0 1 2 3 4 5 6 7 8 9 10 11
Análisis de Complejidad:
- Complejidad temporal: O(N * log k) u O(n * k * log k), donde ‘N’ es el número total de elementos entre todas las listas vinculadas, ‘k’ es el número total de listas y ‘ n’ es el tamaño de cada lista enlazada.
La operación de inserción y eliminación se realizará en min-heap para todos los N Nodes.
La inserción y la eliminación en un montón mínimo requieren un tiempo de registro k. - Espacio Auxiliar: O(k).
La cola de prioridad tendrá como máximo ‘k’ número de elementos en cualquier momento, por lo tanto, el espacio adicional requerido para nuestro algoritmo es O(k).
Consulte el artículo completo sobre Fusionar k listas ordenadas enlazadas | ¡ Establezca 2 (Usando Min Heap) para obtener más detalles!
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA