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:
Java
// Java implementation to merge
// k sorted linked lists
// Using MIN HEAP method
import java.util.PriorityQueue;
import java.util.Comparator;
public class MergeKLists
{
// Function to merge k sorted
// linked lists
public static Node mergeKSortedLists(
Node arr[], int k)
{
Node head = null, last = null;
// priority_queue 'pq' implemeted
// as min heap with the
// help of 'compare' function
PriorityQueue<Node> pq =
new PriorityQueue<>(new Comparator<Node>()
{
public int compare(Node a, Node b)
{
return a.data - b.data;
}
});
// Push the head nodes of all
// the k lists in 'pq'
for (int i = 0; i < k; i++)
if (arr[i] != null)
pq.add(arr[i]);
// Loop till 'pq' is not empty
while (!pq.isEmpty())
{
// Get the top element of 'pq'
Node top = pq.peek();
pq.remove();
// 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.add(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;
}
}
// Head node of the required merged list
return head;
}
// Function to print the singly linked list
public static void printList(Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
}
// Utility function to create
// a new node
public Node push(int data)
{
Node newNode = new Node(data);
newNode.next = null;
return newNode;
}
public static void main(String args[])
{
// Number of linked lists
int k = 3;
// Number of elements in each list
int n = 4;
// An array of pointers storing the
// head nodes of the linked lists
Node arr[] = new Node[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
Node head = mergeKSortedLists(arr, k);
printList(head);
}
}
class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
next = null;
}
}
// This code is contributed by Gaurav Tiwari
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