← Back to Index

📚 Merge K Sorted Lists – Java Cheat Sheet

📌 What Is It?

The problem involves merging K sorted linked lists into one sorted linked list. This is a classic problem that can be solved efficiently using the K-Way Merge Pattern with a min-heap.

The min-heap helps us efficiently track the smallest elements across all lists, ensuring the merged list is sorted.

🧱 Pattern Template

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> minHeap = new PriorityQueue<>((a, b) -> a.val - b.val);

        // Step 1: Add the head of each list to the heap
        for (ListNode node : lists) {
            if (node != null) {
                minHeap.offer(node);
            }
        }

        // Step 2: Extract the smallest element and add the next node from the same list
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        while (!minHeap.isEmpty()) {
            ListNode smallest = minHeap.poll();
            current.next = smallest;
            current = current.next;

            if (smallest.next != null) {
                minHeap.offer(smallest.next);
            }
        }

        return dummy.next;
    }
}

📊 Time Complexity

• Heap Initialization: O(K log K) – Adding the head of each list to the heap.
• Heap Operations: O(N log K) – Extracting and adding elements to the heap, where N is the total number of nodes.
• Overall Complexity: O(N log K).

✅ Use Cases

• Merging multiple sorted linked lists
• Efficiently combining sorted data streams
• Applications in external sorting and database systems

📘 Common LeetCode Problems

• 23. Merge k Sorted Lists [Hard] Heap

🧪 Example: Merge K Sorted Lists

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]

Explanation:
- Add the head of each list to the heap: [1, 1, 2].
- Extract the smallest (1) and add the next node from the same list.
- Repeat until all nodes are merged into the result list.

▶️ View Animation

💡 Pro Tips

• Use a min-heap to efficiently track the smallest element among the lists.
• Edge cases: empty lists, lists of unequal lengths.
• Ensure the heap stores enough information to track the source of each element.