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.
Implementación:
C++
// C++ program to merge k sorted
// arrays 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 program to test
// above functions
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;
}
Java
// Java program to merge k sorted
// arrays 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 program to test
// above functions
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
Python3
# Python3 program to merge k # sorted arrays of size n each # A Linked List node class Node: def __init__(self, x): self.data = x self.next = None # Function to print nodes in # a given linked list def printList(node): while (node != None): print(node.data, end = " ") node = node.next # The main function that # takes an array of lists # arr[0..last] and generates # the sorted output def mergeKLists(arr, last): # Traverse form second # list to last for i in range(1, last + 1): while (True): # head of both the lists, # 0 and ith list. head_0 = arr[0] head_i = arr[i] # Break if list ended if (head_i == None): 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 != None): # 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 == None): arr[i] = head_i.next head_i.next = None head_0.next = head_i head_0.next.next = None break return arr[0] # Driver code if __name__ == '__main__': # Number of linked # lists k = 3 # Number of elements # in each list n = 4 # an array of pointers # storing the head nodes # of the linked lists arr = [None for i in range(k)] arr[0] = Node(1) arr[0].next = Node(3) arr[0].next.next = Node(5) arr[0].next.next.next = Node(7) arr[1] = Node(2) arr[1].next = Node(4) arr[1].next.next = Node(6) arr[1].next.next.next = Node(8) arr[2] = Node(0) arr[2].next = Node(9) arr[2].next.next = Node(10) arr[2].next.next.next = Node(11) # Merge all lists head = mergeKLists(arr, k - 1) printList(head) # This code is contributed by Mohit Kumar 29
C#
// C# program to merge k sorted
// arrays of size n each
using System;
// A Linked List node
public class Node
{
public int data;
public Node next;
// Utility function to create a new node.
public Node(int key)
{
data = key;
next = null;
}
}
public class GFG
{
static Node head;
/* Function to print nodes in
a given linked list */
static void printList(Node node)
{
while(node != null)
{
Console.Write(node.data + " ");
node = node.next;
}
Console.WriteLine();
}
// 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];
}
static public void Main ()
{
// Number of linked lists
int k = 3;
// 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 rag2127
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 program to test
// above functions
// 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 montón y funciona en O(nk Log k).
Se sabe que la fusión de dos listas enlazadas se puede realizar en O(n) tiempo y O(n) espacio.
- 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
// arrays 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 program to test above functions
int main()
{
int k = 3; // Number of linked lists
int n = 4; // Number of elements in each list
// 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;
}
Java
// Java program to merge k sorted arrays 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[])
{
int k = 3; // Number of linked lists
int n = 4; // Number of elements in each list
// 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
Python3
# Python3 program to merge k sorted # arrays of size n each # A Linked List node class Node: def __init__(self): self.data = 0 self.next = None # Function to print nodes in a # given linked list def printList(node): while (node != None): print(node.data, end = ' ') 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(Log n) extra space for recursive calls, # but it can be easily modified to work with # same time and O(1) extra space def SortedMerge(a, b): result = None # Base cases if (a == None): return(b) elif (b == None): 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 def mergeKLists(arr, last): # Repeat until only one list is left while (last != 0): 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 += 1 j -= 1 # If all pairs are merged, update last if (i >= j): last = j return arr[0] # Utility function to create a new node. def newNode(data): temp = Node() temp.data = data temp.next = None return temp # Driver code if __name__=='__main__': # Number of linked lists k = 3 # Number of elements in each list n = 4 # An array of pointers storing the # head nodes of the linked lists arr = [0 for i in range(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 head = mergeKLists(arr, k - 1) printList(head) # This code is contributed by rutvik_56
C#
// C# program to merge k sorted arrays of size n each
using System;
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) {
Console.Write(node.data + " ");
node = node.next;
}
}
public static void Main()
{
int k = 3; // Number of linked lists
//int n = 4; // Number of elements in each list
// 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);
}
}
public class Node {
public int data;
public Node next;
public Node(int data)
{
this.data = data;
}
}
/* This code contributed by PrinciRaj1992 */
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;
}
}
var k = 3; // Number of linked lists
var n = 4; // Number of elements in each list
// 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 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.
Fusionar k listas enlazadas ordenadas | Conjunto 2 (usando montón mínimo)
Este artículo es una contribución de Aditya Goel . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@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.
Método 4: seleccionar el mínimo del elemento superior de forma iterativa
Enfoque: seleccione el mínimo de los elementos superiores de forma iterativa, guárdelo en un nuevo Node e incremente el puntero del elemento mínimo.
Implementación:
C++
// C++ program to merge k sorted arrays of size n each
#include <bits/stdc++.h>
using namespace std;
// A Linked List node
struct Node
{
int data;
Node* next;
Node(int x)
{
data = x;
next = NULL;
}
};
/* Function to print nodes in a given linked list */
void printList(Node* node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
cout << endl;
}
/*Linked list Node structure
struct Node
{
int data;
Node* next;
Node(int x){
data = x;
next = NULL;
}
};
*/
class Solution
{
public:
// Function to merge K sorted linked list.
Node* mergeKLists(Node* arr[], int K)
{
Node* head = NULL;
while (1)
{
int a = 0;
int z;
Node* curr;
int min = INT_MAX;
for (int i = 0; i < K; i++)
{
if (arr[i] != NULL)
{
a++;
if (arr[i]->data < min)
{
min = arr[i]->data;
z = i;
}
}
}
if (a != 0)
{
arr[z] = arr[z]->next;
Node* temp = new Node(min);
if (head == NULL)
{
head = temp;
curr = temp;
}
else
{
curr->next = temp;
curr = temp;
}
}
else
{
return head;
}
}
}
};
// { Driver Code Starts.
// Driver program to test above functions
int main()
{
int t;
cin >> t;
while (t--)
{
int N;
cin >> N;
struct Node* arr[N];
for (int j = 0; j < N; j++)
{
int n;
cin >> n;
int x;
cin >> x;
arr[j] = new Node(x);
Node* curr = arr[j];
n--;
for (int i = 0; i < n; i++)
{
cin >> x;
Node* temp = new Node(x);
curr->next = temp;
curr = temp;
}
}
Solution obj;
Node* res = obj.mergeKLists(arr, N);
printList(res);
}
return 0;
}
// } Driver Code Ends
Producción
Complejidad temporal: O(n*k 2 )
Espacio auxiliar: O(n)
Tomemos un ejemplo para entender la Complejidad del Tiempo
array[0] = 0->1->2->NULO
array[1] = 3->4->5->NULO
array[2] = 6->7->8->NULO
norte = 3 k = 3
He tomado este ejemplo para que entiendas la complejidad de una manera fácil.
De acuerdo con el enfoque, encontramos 0 como el elemento mínimo en los primeros k Nodes, para encontrar esto tomaremos K tiempo.
De manera similar, encontramos 1 como mínimo en K tiempo, este proceso se ejecuta para N Nodes en la primera lista, por lo que el tiempo necesario será O (NK) para arr [0], después de esto, nuestro elemento mínimo vendrá en el resto dos listas, por lo que nuestro bucle funciona para K-1 y para la segunda lista, el tiempo necesario será N*K-1. Este proceso continuará hasta que fusionemos todos los Nodes de todas las listas.
Entonces la ecuación puede ser
NK + N*K-1 + N*K-2 + …… + N * 1
N(K+ K-1 + K-2 + … + 1)
Que es igual a O (N*K^2)
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