Hey! It's day 9 of 10days coding challenge with I4G. Today's task was to write a code that can merge k sorted lists.
Thought process:
Understanding of problem: **The task here requires us to merge k sorted lists into one. Each of the list is already sorted but needs to be merged into a single sorted list.
**Solution: Since each list is already sorted, the problem is easier to tackle. There are several approaches to this problem such as divide and conquer, merging the list one by one, comparing each list one by one, using brute force and using priority queue.
In my own solution here, I used priority queue. The node of each list was compared, and the minimum node was added to the queue, until the queue was not empty. Then the minimum node was extracted and stored in our result list. And the result list is return.
Algorithm:
- Create a priority queue.
- Add the first node from all the lists into the priority queue.
- Loop until the priority queue is not empty
- Get the minimum node from the queue and add it to our result list.
- Add the next node (if present) from the extracted node list.
- Return the resultant list.
Checkout the full code here: https://leetcode.com/submissions/detail/810988090/
Top comments (0)