« Merge K sorted Linked List
Divide and conquer approach
1#include <iostream>2#include <iomanip>3#include <algorithm>4#include <string>5#include <cstring>6#include <vector>7#include <cmath>8#include <map>9#include <climits>10// climits for INT_MIN11#include <unordered_map>12using namespace std;1314class Node15{16public:17 int data;18 Node *next;1920 Node()21 {22 this->data = 0;23 this->next = NULL;24 }2526 Node(int data)27 {28 this->data = data;29 this->next = NULL;30 }31};3233void printList(Node *node)34{35 while (node != NULL)36 {37 cout << node->data << endl;38 node = node->next;39 }40}4142Node *SortedMerge(Node *a, Node *b)43{44 Node *result = NULL;45 if (a == NULL)46 return (b);47 else if (b == NULL)48 return (a);4950 if (a->data <= b->data)51 {52 result = a;53 result->next = SortedMerge(a->next, b);54 }55 else56 {57 result = b;58 result->next = SortedMerge(a, b->next);59 }6061 return result;62}6364Node *mergeKLists(Node *arr[], int last)65{66 while (last != 0)67 {68 int i = 0, j = last;69 while (i < j)70 {71 arr[i] = SortedMerge(arr[i], arr[j]);72 i++, j--;73 if (i >= j)74 {75 last = j;76 }77 }78 }7980 return arr[0];81}82int main()83{84 int k = 3;85 int n = 4;86 Node *arr[k];8788 arr[0] = new Node(1);89 arr[0]->next = new Node(3);90 arr[0]->next->next = new Node(5);91 arr[0]->next->next->next = new Node(7);9293 arr[1] = new Node(-1);94 arr[1]->next = new Node(4);95 arr[1]->next->next = new Node(6);96 arr[1]->next->next->next = new Node(8);9798 arr[2] = new Node(0);99 arr[2]->next = new Node(9);100 arr[2]->next->next = new Node(10);101 arr[2]->next->next->next = new Node(11);102103 // Merge all lists104 Node *head = mergeKLists(arr, k - 1);105106 printList(head);107 return 0;108}
Time Complexity:
O(N Klog K), As outer while loop in function mergeKLists() runs log K times and every time it processes N*K elements.
Auxiliary Space:
O(N K), Because recursion is used in SortedMerge() and to merge the final 2 linked lists of size N/2, N recursive calls will be made.
Merge K sorted linked lists by Selecting min of top element:
1#include <iostream>2#include <iomanip>3#include <algorithm>4#include <string>5#include <cstring>6#include <vector>7#include <cmath>8#include <map>9#include <climits>10// climits for INT_MIN11#include <unordered_map>12using namespace std;1314class Node15{16public:17 int data;18 Node *next;19 Node(int data)20 {21 this->data = data;22 this->next = NULL;23 }24};2526void printList(Node *node)27{28 while (node != NULL)29 {30 cout << node->data << endl;31 node = node->next;32 }33}3435Node *mergeKLists(Node *arr[], int k)36{37 Node *head = NULL;38 while (1)39 {40 int a = 0;41 Node *curr;42 int z;43 int min = INT_MAX;4445 for (int i = 0; i < k; i++)46 {47 if (arr[i] != NULL)48 {49 a++;50 if (arr[i]->data < min)51 {52 min = arr[i]->data;53 z = i;54 }55 }56 }57 if (a != 0)58 {59 arr[z] = arr[z]->next;60 Node *temp = new Node(min);61 if (head == NULL)62 {63 curr = head = temp;64 }65 else66 {67 curr->next = temp;68 curr = temp;69 }70 }71 else72 {73 return head;74 }75 }76}77int main()78{79 int k = 3;80 int n = 4;8182 Node *arr[k];83 arr[0] = new Node(1);84 arr[0]->next = new Node(3);85 arr[0]->next->next = new Node(5);86 arr[0]->next->next->next = new Node(7);8788 arr[1] = new Node(-1);89 arr[1]->next = new Node(4);90 arr[1]->next->next = new Node(6);91 arr[1]->next->next->next = new Node(8);9293 arr[2] = new Node(0);94 arr[2]->next = new Node(9);95 arr[2]->next->next = new Node(10);96 arr[2]->next->next->next = new Node(11);9798 Node *head = mergeKLists(arr, k - 1);99100 printList(head);101 return 0;102}
Time complexity:
O(NK2), There are NK nodes in total and to find the smallest node it takes K times so for the NK nodes it will take NK*K time.
Auxiliary Space:
O(N)
Naive approach
1#include <iostream>2#include <iomanip>3#include <algorithm>4#include <string>5#include <cstring>6#include <vector>7#include <cmath>8#include <map>9#include <climits>10// climits for INT_MIN11#include <unordered_map>12using namespace std;1314class Node15{16public:17 int data;18 Node *next;1920 Node()21 {22 this->data = 0;23 this->next = NULL;24 }2526 Node(int data)27 {28 this->data = data;29 this->next = NULL;30 }31};3233void printList(Node *node)34{35 while (node != NULL)36 {37 cout << node->data << endl;38 node = node->next;39 }40}4142Node *mergeKLists(Node *arr[], int count)43{44 if (count == 0)45 {46 Node *x = new Node();47 return x;48 }49 Node *head_main = arr[0];50 for (int i = 1; i <= count; i++)51 {52 Node *head_0 = head_main;53 while (true)54 {55 Node *head_i = arr[i];5657 if (head_i == NULL)58 {59 break;60 }6162 if (head_0->data >= head_i->data)63 {64 arr[i] = head_i->next;65 head_i->next = head_0;66 arr[0] = head_i;67 head_main = head_i;68 head_0 = head_main;69 }70 else71 {72 while (head_0->next != NULL)73 {74 if (head_i->data <= head_0->next->data)75 {76 arr[i] = head_i->next;77 head_i->next = head_0->next;78 head_0->next = head_i;79 break;80 }81 head_0 = head_0->next;8283 if (head_0->next == NULL)84 {85 arr[i] = head_i->next;86 arr[i] = NULL;87 head_0->next = head_i;88 break;89 }90 }91 }92 }93 }94 return head_main;95}9697int main()98{99 int k = 3;100 int n = 4;101 Node *arr[k];102103 arr[0] = new Node(1);104 arr[0]->next = new Node(3);105 arr[0]->next->next = new Node(5);106 arr[0]->next->next->next = new Node(7);107108 arr[1] = new Node(-1);109 arr[1]->next = new Node(4);110 arr[1]->next->next = new Node(6);111 arr[1]->next->next->next = new Node(8);112113 arr[2] = new Node(0);114 arr[2]->next = new Node(9);115 arr[2]->next->next = new Node(10);116 arr[2]->next->next->next = new Node(11);117118 // Merge all lists119 Node *head = mergeKLists(arr, k - 1);120121 printList(head);122 return 0;123}