Merge k Sorted Lists

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

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

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

Example :

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Approach:
The Divide and Conquer strategy is covered in this challenge. This method operates in O and doesn't require additional heap space (nk Log k)
The merging of two linked lists can be accomplished in O(n) time and O(n) space, as is well known.

1. The plan is to merge each pair in linear time utilising O(n) space after pairing up K lists.

2. K/2 lists, each of size 2*N, are left after the initial cycle. K/4 lists, each of size 4*N, are left after the second cycle.

3. Continue the process until there is just one list left.

Thank You❤️

Comments

[Mfon.]

🤝🏾🏅