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.
Javascript
<script>
// Javascript program to merge k sorted
// arrays of size n each
// A Linked List node
class Node
{
// Utility function to create a new node.
constructor(key)
{
this.data = key;
this.next = null;
}
}
let head;
let temp;
/* Function to print nodes in a
given linked list */
function printList(node)
{
while(node != null)
{
document.write(node.data + " ");
node = node.next;
}
document.write("<br>");
}
// The main function that takes an array
// of lists arr[0..last] and generates
// the sorted output
function mergeKLists(arr, last)
{
// Traverse form second list to last
for (let i = 1; i <= last; i++)
{
while(true)
{
// head of both the lists,
// 0 and ith list.
let head_0 = arr[0];
let 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];
}
// 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
head = mergeKLists(arr, k - 1);
printList(head);
// This code is contributed by unknown2108
</script>
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.
Javascript
<script>
// JavaScript program to merge k sorted
// arrays of size n each
class Node
{
constructor(val)
{
this.data = val;
this.next = null;
}
}
/* Takes two lists sorted in increasing order,
and merge their nodes together to make one
big sorted list. Below function takes O(Log n)
extra space for recursive calls, but it can be
easily modified to work with same time and
O(1) extra space */
function SortedMerge(a, b)
{
var 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
function mergeKLists(arr, last)
{
// repeat until only one list is left
while (last != 0)
{
var 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];
}
/* Function to print nodes in a given
linked list */
function printList(node)
{
while (node != null)
{
document.write(node.data + " ");
node = node.next;
}
}
// Number of linked lists
var k = 3;
// Number of elements in each list
var n = 4;
// An array of pointers storing the
// head nodes of the linked lists
var arr = 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
var head = mergeKLists(arr, k - 1);
printList(head);
// This code is contributed by gauravrajput1
</script>
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