Merge K Sorted Lists in Java: Explanation & Practice

Problem summary

Given an array of k sorted linked lists, merge them into one sorted list. Use min-heap for efficient merging.

Starter code

public class Main {
    public static void main(String[] args) {
        // lists = [[1,4,5],[1,3,4],[2,6]]
        // Use min-heap to always get smallest element
        // Print: 1 1 2 3 4 4 5 6
    }
}

Expected output and test cases

• Merge 3 lists

  1 1 2 3 4 4 5 6

• Empty list array

• Single list [[1]]

  1

Hints

1. Add head of each list to min-heap
2. Poll smallest, add to result, add its next to heap
3. Continue until heap is empty
4. Time: O(N log k) where N is total nodes, k is number of lists

Related Data Structures & Algorithms exercises

• Practice Word Search in Java
• Practice Kth Largest Element in Java
• Practice Top K Frequent Elements in Java

Practice all Data Structures & Algorithms exercises · Run this idea in the Java compiler