Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6
This problem can be solved by below given ways:
- Using Map
- Using mergeSort or Divide and Conquer
- Using Recursive
- Using Priority Queue
Here we shall discuss 2 solutions
- Using merge sort or Divide and Conquer
- Using Recursive
- Using Priority Queue <Will be updated later>
Before looking to the solution, have a look at the previous example where we have merged 2 sorted Linked Lists.
Solution in C++
/* * File : merge_k_sorted_list.cpp */ #include<iostream> #include<vector> using namespace std; struct Node { int data; struct Node* next; }; void insert_at_begenning ( struct Node **head_pointer, int data) { // allocate memory for new node struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node)); // assign the data to new node temp_node->data = data; // initialize the new node to point to NULL temp_node->next = NULL; // if this is the first pointer, then this is the head pointer if (*head_pointer == NULL) { *head_pointer = temp_node; } else { // point the next of the present pointer to the head pointer temp_node->next = *head_pointer; //then move the reference of head pointer to the current pointer *head_pointer = temp_node; } } void display_list(struct Node **head_pointer) { // take a reference to head pointer for navigation struct Node *temp = *head_pointer; while(temp != NULL) { if(temp->next != NULL) printf("%d -> ", temp->data); else printf("%d", temp->data); //navigate to next pointer temp = temp->next; } printf("\n"); } /*Functions for getting result through merge sort START*/ Node* merge_2_lists(Node* l1, Node* l2) { if(!l1) return l2; if(!l2) return l1; if(l1->data < l2->data) { l1->next = merge_2_lists(l1->next, l2); return l1; } else { l2->next = merge_2_lists(l1, l2->next); return l2; } } Node* partition_merge_sort(vector<Node*>& lists, int start, int end) { if(start == end) { return lists[start]; } if(start < end) { int mid = (end+start)/2; Node* l1 = partition_merge_sort(lists, start, mid); Node* l2 = partition_merge_sort(lists, mid+1, end); return merge_2_lists(l1, l2); } return NULL; } Node* merge_list_through_merge_sort(vector<Node*>& lists) { return partition_merge_sort(lists, 0, lists.size()-1); } /*Functions for getting result through merge sort END*/ /*Functions for getting result through recursion START*/ Node* merge_list_through_recursive(vector<Node*>& lists) { if(lists.empty()) return NULL; while(lists.size() > 1) { lists.push_back(merge_2_lists(lists[0], lists[1])); lists.erase(lists.begin()); lists.erase(lists.begin()); } return lists[0]; } /*Functions for getting result through recursion END*/ int main() { vector<Node*> list; struct Node *list_1 = NULL; struct Node *list_2 = NULL; struct Node *list_3 = NULL; struct Node *result_list_through_merge_sort = NULL; insert_at_begenning(&list_1,7); insert_at_begenning(&list_1,5); insert_at_begenning(&list_1,3); insert_at_begenning(&list_1,1); insert_at_begenning(&list_2,8); insert_at_begenning(&list_2,6); insert_at_begenning(&list_2,4); insert_at_begenning(&list_2,2); insert_at_begenning(&list_3,18); insert_at_begenning(&list_3,16); insert_at_begenning(&list_3,14); insert_at_begenning(&list_3,12); cout<<"List 1 is\n"; display_list(&list_1); cout<<"\nList 2 is\n"; display_list(&list_2); cout<<"\nList 3 is\n"; display_list(&list_3); list.push_back(list_1); list.push_back(list_2); list.push_back(list_3); //result_list_through_merge_sort = merge_list_through_merge_sort(list); //cout<<"\nThe result through merge sort is "<<endl; result_list_through_merge_sort = merge_list_through_recursive(list); cout<<"\nThe result through recursive is "<<endl; //result_list_through_merge_sort = merge_list_through_merge_sort(list); //cout<<"\nThe result through merge sort is "<<endl; display_list(&result_list_through_merge_sort); cout<<endl; return 0; }
Output:
List 1 is 1 -> 3 -> 5 -> 7 List 2 is 2 -> 4 -> 6 -> 8 List 3 is 12 -> 14 -> 16 -> 18 The result through recursive is 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 12 -> 14 -> 16 -> 18