How to Merge K Sorted Lists in Java (With Simple Examples)

When I first faced the problem of merging K sorted lists in Java, I knew I needed an efficient solution. Simply merging all lists and sorting them afterward wasn’t enough — I wanted an optimized approach. In this article, I’ll walk you through how I tackled this popular coding challenge, step-by-step, using priority queues. I’ll also provide detailed examples and explanations to make it as easy as possible to understand.

Why Merging K Sorted Lists Matters

In real-world applications like search engines, database merging, and file management systems, merging multiple sorted datasets efficiently is crucial. When each list is already sorted, re-sorting everything again is wasteful. I realized that the best approach should leverage the fact that the individual lists are already sorted.

The Basic Idea

My strategy was simple:

Use a PriorityQueue (min-heap) to always fetch the smallest current element across all the lists.
Add the next element from the list where the minimum was extracted.
Repeat until all elements are merged.

By always knowing the smallest available number, I could efficiently build the final sorted list.

Java Code Example: Merging K Sorted Linked Lists

First, I created a helper class to represent nodes of linked lists:


class ListNode {
    int val;
    ListNode next;
    ListNode(int val) {
        this.val = val;
    }
}

class ListNode {

int val;

ListNode next;

ListNode(int val) {

this.val = val;

}

Now here’s the main method I used to merge K sorted lists:


import java.util.PriorityQueue;

public class MergeKSortedLists {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists == null || lists.length == 0) return null;

        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);

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

        ListNode dummy = new ListNode(0);
        ListNode current = dummy;

        while (!heap.isEmpty()) {
            ListNode minNode = heap.poll();
            current.next = minNode;
            current = current.next;

            if (minNode.next != null) {
                heap.offer(minNode.next);
            }
        }

        return dummy.next;
    }
}

import java.util.PriorityQueue;

public class MergeKSortedLists {

public ListNode mergeKLists(ListNode[] lists) {

if (lists == null || lists.length == 0) return null;

PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);

// Add the head of each list to the heap

for (ListNode node : lists) {

if (node != null) {

heap.offer(node);

}

ListNode dummy = new ListNode(0);

ListNode current = dummy;

while (!heap.isEmpty()) {

ListNode minNode = heap.poll();

current.next = minNode;

current = current.next;

if (minNode.next != null) {

heap.offer(minNode.next);

}

return dummy.next;

}

How This Code Works (Step-by-Step)

Initialization:
I start by creating a PriorityQueue that sorts the nodes based on their values.
Loading Initial Elements:
I add the head node of each list to the heap. This way, I know the smallest first elements.
Building the Result:
In a loop, I take the smallest node out of the heap, attach it to the result list, and if the extracted node has a next node, I add that next node back into the heap.
Finishing Up:
When the heap is empty, all elements have been merged in ascending order.

Example Run

Suppose I have the following 3 sorted lists:


List 1: 1 -> 4 -> 5
List 2: 1 -> 3 -> 4
List 3: 2 -> 6

List 1: 1 -> 4 -> 5

List 2: 1 -> 3 -> 4

List 3: 2 -> 6

Step-by-step merging would be:

Heap starts with [1,1,2].
Poll 1 (from List 1). Add 4 from List 1.
Heap now [1,2,4].
Poll 1 (from List 2). Add 3 from List 2.
Heap now [2,3,4].
Poll 2 (from List 3). Add 6 from List 3.
Continue until all nodes are processed.

Final result:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6

Time and Space Complexity

Time Complexity:
O(N log K), where N is the total number of nodes and K is the number of linked lists.

Why?
Each insertion and removal operation on the heap takes O(log K) time, and we do this N times (for every node).

Space Complexity:
O(K) for the heap, since at any time, the heap holds at most K nodes.

Conclusion

Merging K sorted lists in Java can seem tricky at first, but using a priority queue makes it clean and efficient. I personally found that understanding the flow step-by-step helped me master not only this problem but also improved my overall data structure skills.

If you’re preparing for interviews, knowing this pattern is absolutely essential. And trust me, the more you practice it, the more intuitive it becomes!