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.
Java
// Java program to merge k sorted
// linked lists of size n each
import java.io.*;
// A Linked List node
class Node
{
int data;
Node next;
// Utility function to create
// a new node.
Node(int key)
{
data = key;
next = null;
}
}
class GFG
{
static Node head;
static Node temp;
/* Function to print nodes in
a given linked list */
static void printList(Node node)
{
while(node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
System.out.println();
}
// The main function that takes an array
// of lists arr[0..last] and generates
// the sorted output
static 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];
Node 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
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
head = mergeKLists(arr, k - 1);
printList(head);
}
}
// This code is contributed by avanitrachhadiya2155
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.
Java
// Java program to merge k sorted
// linked lists of size n each
public class MergeKSortedLists
{
/* 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 */
public static 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
public static 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];
}
/* Function to print nodes in a
given linked list */
public static void printList(Node node)
{
while (node != null)
{
System.out.print(node.data + " ");
node = node.next;
}
}
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 = mergeKLists(arr, k - 1);
printList(head);
}
}
class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
}
}
// 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:
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