Dadas K listas enlazadas ordenadas de tamaño N cada una, combínelas e imprima la salida ordenada.
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.
Método 1 (Simple):
Enfoque:
una solución simple es inicializar el resultado como la primera lista. Ahora recorra todas las listas a partir de la segunda lista. Inserte cada Node de la lista recorrida actualmente en el resultado de forma ordenada.
C++
// C++ program to merge k sorted
// linked lists of size n each
#include <bits/stdc++.h>
using namespace std;
// A Linked List node
struct Node
{
int data;
Node* next;
};
/* Function to print nodes in a
given linked list */
void printList(Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
// The main function that takes an
// array of lists arr[0..last] and
// generates the sorted output
Node* mergeKLists(Node* arr[],
int last)
{
// Traverse form second list to last
for (int i = 1; i <= last; i++)
{
while (true)
{
// Head of both the lists,
// 0 and ith list.
Node *head_0 = arr[0],
*head_i = arr[i];
// Break if list ended
if (head_i == NULL)
break;
// Smaller than first element
if (head_0->data >= head_i->data)
{
arr[i] = head_i->next;
head_i->next = head_0;
arr[0] = head_i;
}
else
// Traverse the first list
while (head_0->next != NULL)
{
// Smaller than next element
if (head_0->next->data >=
head_i->data)
{
arr[i] = head_i->next;
head_i->next = head_0->next;
head_0->next = head_i;
break;
}
// go to next node
head_0 = head_0->next;
// if last node
if (head_0->next == NULL)
{
arr[i] = head_i->next;
head_i->next = NULL;
head_0->next = head_i;
head_0->next->next = NULL;
break;
}
}
}
}
return arr[0];
}
// Utility function to create
// a new node.
Node* newNode(int data)
{
struct Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
// 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];
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 all lists
Node* head = mergeKLists(arr, k - 1);
printList(head);
return 0;
}
Producción:
0 1 2 3 4 5 6 7 8 9 10 11
Análisis de Complejidad:
- Complejidad del tiempo: O(nk 2 )
- Espacio Auxiliar: O(1).
Como no se requiere espacio adicional.
Método 2: montón mínimo .
Una mejor solución es usar una solución basada en Min Heap que se analiza aquí para arreglos. La complejidad temporal de esta solución sería O(nk Log k)
Método 3: divide y vencerás .
En esta publicación, se analiza el enfoque Divide and Conquer . Este enfoque no requiere espacio adicional para el almacenamiento dinámico y funciona en O(nk Log k).
Se sabe que la fusión de dos listas enlazadas se puede realizar en tiempo O(n) y espacio O(n).
- La idea es emparejar K listas y fusionar cada par en tiempo lineal usando el espacio O(n).
- Después del primer ciclo, se dejan listas K/2 cada una de tamaño 2*N. Después del segundo ciclo, se dejan listas K/4 cada una de tamaño 4*N y así sucesivamente.
- Repita el procedimiento hasta que solo nos quede una lista.
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to merge k sorted
// linked lists of size n each
#include <bits/stdc++.h>
using namespace std;
// A Linked List node
struct Node
{
int data;
Node* next;
};
/* Function to print nodes in a
given linked list */
void printList(Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Takes two lists sorted in increasing order,
and merge their nodes together to make one
big sorted list. Below function takes O(n)
extra space for recursive calls, */
Node* SortedMerge(Node* a, Node* b)
{
Node* result = NULL;
// Base cases
if (a == NULL)
return (b);
else if (b == NULL)
return (a);
// Pick either a or b, and recur
if (a->data <= b->data)
{
result = a;
result->next = SortedMerge(a->next, b);
}
else
{
result = b;
result->next = SortedMerge(a, b->next);
}
return result;
}
// The main function that takes an
// array of lists arr[0..last] and
// generates the sorted output
Node* mergeKLists(Node* arr[], int last)
{
// Repeat until only one list is left
while (last != 0)
{
int i = 0, j = last;
// (i, j) forms a pair
while (i < j)
{
// merge List i with List j and
// store merged list in List i
arr[i] = SortedMerge(arr[i], arr[j]);
// consider next pair
i++, j--;
// If all pairs are merged, update
// last
if (i >= j)
last = j;
}
}
return arr[0];
}
// Utility function to create
// a new node.
Node* newNode(int data)
{
struct Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
// 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];
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 all lists
Node* head = mergeKLists(arr, k - 1);
printList(head);
return 0;
}
Producción:
0 1 2 3 4 5 6 7 8 9 10 11
Análisis de Complejidad:
Suponiendo que N(n*k) es el número total de Nodes, n es el tamaño de cada lista vinculada y k es el número total de listas vinculadas.
- Complejidad de tiempo: O(N*log k) u O(n*k*log k)
Como ciclo while externo en la función mergeKLists() ejecuta log k veces y cada vez que procesa n*k elementos. - Espacio auxiliar: O(N) u O(n*k)
Debido a que la recursividad se usa en SortedMerge() y para fusionar las 2 listas enlazadas finales de tamaño N/2, se realizarán N llamadas recursivas.
Consulte el artículo completo sobre las listas enlazadas ordenadas de Merge K | ¡ Establezca 1 para 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