Merge K Sorted Lists

If you’ve ever wondered “how the heck do we merge multiple sorted linked lists efficiently?” — this post is for you.

We’ll break down the Merge K Sorted Lists problem step-by-step, explain the intuition behind the logic, and walk through an example so clear that you’ll never forget it again.

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!