LeetCode problem 23 Merge k Sorted Lists [Divide and conquer][Min-Heap](Java)

Source Url:https://leetcode.com/problems/merge-k-sorted-lists/

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[  
  1->4->5,  
  1->3->4,  
  2->6
]
Output:
1->1->2->3->4->4->5->6

I don’t know how to merge k lists, but we know how to merge two lists from problem 21. So we can merge the first two lists and merge others one by one. This is the brute force solution.

Brute force solution

mergeTwoList function from problem 21.

Divide and conquer solution

How to use Divide and conquer approach to solve this problem? We can naturally think about divide the lists to two half, then divide it again and again, until there are only two linked lists. Then we can use the mergeTwoList function from problem 21. And we return to combine the results. So this is just like Mergesort from book Introduction to Algorithms, and we already know how to write. Our solution is almost identical to our Mergesort code.

Min-heap solution

In this solution we use a min-heap, it is almost identical to max-heap. We only need to change serval lines to make a max-heap to become min-heap. We use the code described in “Heap and Heap-Sort algorithm“.

Our method is: First, move all data from lists to an array, then use the array to build a min-heap. Finally, we output the current minimum number in a loop, make a LinkedList and return it.

This is the code (Code about min-heap you can find in GitHub files):

Github address: https://github.com/tinyfool/leetcode/tree/master/src/p0023

Want to know details of the Divide and conquer, check my post: Leetcode problems of Divide and conquer.

Want to know detail of heap and heapsort, check my post:Heap and Heap-Sort algorithm.

2 thoughts to “LeetCode problem 23 Merge k Sorted Lists [Divide and conquer][Min-Heap](Java)”

  1. Greetings fom California! I’m bored to tears aat work so I decided
    to chneck out your blog on my iphone during lunch break.
    I really like the information you present here aand can’t wait to take a look when I get home.
    I’m surprised at how quick your blog loaded on my celll phone ..
    I’m not even using WIFI, just 3G .. Anyhow, superb site!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.