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:
// C++ implementation to merge k
// sorted linked lists
// | Using MIN HEAP method
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
// Utility function to create
// a new node
struct Node* newNode(int data)
{
// Allocate node
struct Node* new_node = new Node();
// Put in the data
new_node->data = data;
new_node->next = NULL;
return new_node;
}
// 'compare' function used to build
// up the priority queue
struct compare
{
bool operator()(
struct Node* a, struct Node* b)
{
return a->data > b->data;
}
};
// Function to merge k sorted linked lists
struct Node* mergeKSortedLists(
struct Node* arr[], int k)
{
// Priority_queue 'pq' implemented
// as min heap with the help of
// 'compare' function
priority_queue<Node*, vector<Node*>, compare> pq;
// Push the head nodes of all
// the k lists in 'pq'
for (int i = 0; i < k; i++)
if (arr[i] != NULL)
pq.push(arr[i]);
// Handles the case when k = 0
// or lists have no elements in them
if (pq.empty())
return NULL;
struct Node *dummy = newNode(0);
struct Node *last = dummy;
// Loop till 'pq' is not empty
while (!pq.empty())
{
// Get the top element of 'pq'
struct Node* curr = pq.top();
pq.pop();
// Add the top element of 'pq'
// to the resultant merged list
last->next = curr;
last = last->next;
// Check if there is a node
// next to the 'top' node
// in the list of which 'top'
// node is a member
if (curr->next != NULL)
// Push the next node of top node
// in 'pq'
pq.push(curr->next);
}
// Address of head node of the required
// merged list
return dummy->next;
}
// Function to print the singly
// linked list
void printList(struct Node* head)
{
while (head != NULL)
{
cout << head->data << " ";
head = head->next;
}
}
// Driver code
int main()
{
// 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[k];
// Creating k = 3 sorted lists
arr[0] = newNode(1);
arr[0]->next = newNode(3);
arr[0]->next->next = newNode(5);
arr[0]->next->next->next = newNode(7);
arr[1] = newNode(2);
arr[1]->next = newNode(4);
arr[1]->next->next = newNode(6);
arr[1]->next->next->next = newNode(8);
arr[2] = newNode(0);
arr[2]->next = newNode(9);
arr[2]->next->next = newNode(10);
arr[2]->next->next->next = newNode(11);
// Merge the k sorted lists
struct Node* head = mergeKSortedLists(arr, k);
// Print the merged list
printList(head);
return 0;
}
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).
Este artículo es una contribución de Ayush Jauhari . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su artículo por correo a contribuya@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
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