Merge ok Sorted Lists – DEV Neighborhood 👩‍💻👨‍💻

Day 9 of the #I4G10DaysOfCodeChallenge was to merge ok sorted lists.

You’re given an array of ok linked-lists lists, every linked-list is sorted in ascending order.

Merge all of the linked-lists into one sorted linked-list and return it.

Instance :

Enter: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Rationalization: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted listing:
1->1->2->3->4->4->5->6

Strategy:
The Divide and Conquer technique is roofed on this problem. This technique operates in O and does not require extra heap house (nk Log ok)
The merging of two linked lists might be completed in O(n) time and O(n) house, as is well-known.

1. The plan is to merge every pair in linear time utilising O(n) house after pairing up Okay lists.

2. Okay/2 lists, every of measurement 2*N, are left after the preliminary cycle. Okay/4 lists, every of measurement 4*N, are left after the second cycle.

3. Proceed the method till there is only one listing left.

Thank You❤️