Question

What if there are k sorted linked lists. Please design an algorithm to combine the k linked lists. Input: 1 +4 1 +3 2 +6 +5, +4, Output: 1 +1 +2 +3 +4+4 +5 +6. Implement pseudo code for function Merge-K(1) where l is [l1, l2, ..., lk]. 11 to lk are linked lists.

Answer 1

function main // declare a list called list1 4 // given an array of linked lists names // lists having k lists to merge 6 7 // list1 will be the merged list, //merge all lists with this. list1 = lists [0] // for all lists merge them with the merged list for i = 1 to k-1 list1 = merge_two_lists(list1, lists[i]) we one by one 10. 11 12 13 14 // finally return the merged list return list1 17 18 15 16 Ln


function merge_two_lists(list1, list2): initalize a result list, call it result 21 22 23 // describe the base cases if list1 is NULL: return list 2 if list2 is NULL: return list1 24 25 26 27 28 29 // if you reach here means you have elementsin both // the lists, so // two lists and move the pointer from that list to // the next element 30 pick the smaller element from the 31 32 33 34 if (list1->value <= list2->value): 35 result = list1 36 result ->next= merge_two_lists(list1->next, list2) 37 else: 38 result b; 39 result->next merge_two_lists(list1, list2->next) 40 41 42 43 return result

The merge two lists is a recursive paradigm to merge two given lists:

The code would work like this for the given sample list:

list1 - 1->4->5

merge_sorted)lists(list1 and lists[1] ) will be called which will merge

1->4->5 and 1->3->4

They are merged to give 1->1->3->4->4->5

Then 1->1->3->4->4->5 is merged wit 2-> 6

to get 1->1->2->3->4->4->5->6

if the answer helped you please upvote and if you have any doubts please comment i will surely help.

Code in text:

function main :
   // declare a list called list1
   // given an array of linked lists names
   // lists having k lists to merge

   // list1 will be the merged list, we one by one
   //   merge all lists with this.
   list1 = lists[0]
   // for all lists merge them with the merged list
   for i = 1 to k-1
       list1 = merge_two_lists(list1, lists[i])
// finally return the merged list
return list1

function merge_two_lists(list1, list2):
   initalize a result list, call it result

   // describe the base cases
   if list1 is NULL:
       return list 2
   if list2 is NULL:
       return list1

   // if you reach here means you have elements in both
   // the lists, so pick the smaller element from the
   // two lists and move the pointer from that list to
   // the next element

   if(list1->value <= list2->value):
       result = list1
       result->next = merge_two_lists(list1->next, list2)
   else :
       result = b;
result->next = merge_two_lists(list1, list2->next)

return result