Merge K Sorted Lists

Before we dive in, note that in our previous article we walked through how to merge two sorted linked lists, step by step. That idea is the core building block for what we will do here.

If you would like a quick refresher first, check out the guide: 🔗 Merge Two Sorted Linked Lists

Once you’re comfortable with that, come back here — we’ll take it one level higher and learn how to merge K sorted lists efficiently.

---

In this post we will break the problem down, explain the intuition, and walk through a clear example so the idea sticks

Problem Statement

You are given K linked lists — each sorted in ascending order.
Your task is to merge them all into one single sorted linked list.

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

The Intuition — Think of It Like Paper Sheets
Imagine you have 4 already sorted papers of numbers.

If you merge all 4 one by one, like this:
Merge 1 + 2 → result1
Then result1 + 3 → result2
Then result2 + 4 → result3

That works… but it’s slow because you keep merging bigger and bigger lists repeatedly.

A smarter way?

Merge them in pairs!

Round 1: Merge (List0 + List1), (List2 + List3)

Round 2: Merge the two merged results

Done !!!

This is exactly what our code does — merge lists in pairs, doubling the group size each time.

The Code

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

        int interval = 1;
        int n = lists.length;

        while (interval < n) {
            for (int i = 0; i + interval < n; i = i + interval * 2) {
                lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
            }
            interval *= 2;
        }

        return lists[0];
    }
}

Step-by-Step Explanation

Step 1 — Base check

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

If no lists exist, just return null.

Step 2 — Start with interval = 1

We’ll first merge lists that are next to each other:

interval = 1 → merge (0,1), (2,3), (4,5)...

Step 3 — Merge pairs inside a loop

for (int i = 0; i + interval < n; i = i + interval * 2)

That scary line simply means:

Go through the lists array, merge list[i] with list[i + interval],
then skip ahead by interval * 2 to jump to the next pair.

So for:

interval = 1: merge (0,1), (2,3)

interval = 2: merge (0,2), (4,6)

Step 4 — Replace the merged list

lists[i] = mergeTwoLists(lists[i], lists[i + interval]);

After merging two sorted lists, store the result in lists[i].

Step 5 — Double the interval
interval *= 2;

After each round, we’ve merged lists into bigger groups, so next time we double the interval.

Why interval doubles and i = i + interval * 2

Why interval doubles and i = i + interval * 2

Round	Interval	Pairs Merged	What Happens
1	1	(0,1), (2,3)	Merge small lists
2	2	(0,2)	Merge bigger merged lists
3	4	—	Done (only one list left)

Each merge round combines 2×bigger lists,
so we double the interval and jump ahead by interval * 2.

Time Complexity

Let’s break it down:

Each merge operation takes O(N) (where N is total elements).

Each round halves the number of lists.

So total complexity = O(N log K).

✅ Much faster than merging one by one (which is O(NK)).

Final Thoughts

The key to understanding Merge K Sorted Lists is realizing that:

You don’t merge them one-by-one — you merge them in pairs, in rounds.

This divide-and-conquer pattern is clean, efficient, and elegant — it’s the same concept that powers merge sort!