DEV Community

Rakesh Reddy Peddamallu
Rakesh Reddy Peddamallu

Posted on

Leetcode - 23. Merge k Sorted Lists

#leetcode

When working with linked lists, a classic problem you’ll encounter is:

“Given k sorted linked lists, merge them into one sorted linked list and return it.”

This problem is a favorite in interviews (especially LeetCode #23) because it combines understanding of linked lists, divide-and-conquer, and complexity trade-offs. Let’s dive in step by step.

🧩 Problem Breakdown

We’re given k linked lists, each individually sorted. Our task is to merge them into one sorted linked list.

For example:

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

Output:
1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6
Enter fullscreen mode Exit fullscreen mode

💡 Approach

There are multiple ways to solve this problem:

  1. Brute Force: Put all nodes into an array, sort, then rebuild a linked list.
  • Simple, but sorting all nodes takes O(N log N) time, where N is the total number of nodes.
  • Not very elegant.
  1. Min-Heap / Priority Queue: Keep all heads of the lists in a heap, repeatedly pop the smallest.
  • Efficient (O(N log k)) but requires a heap implementation.
  1. Divide and Conquer (our approach):
  • Repeatedly merge pairs of lists (like merge sort).
  • Each merge is linear, and we keep halving the number of lists until one remains.
  • Clean and efficient without extra data structures.

We’ll use divide and conquer here.

🛠 Step 1: Merging Two Sorted Lists

We first need a helper to merge two sorted linked lists. This is like the merge step of merge sort.

const merge_two_lists = (list1, list2) => {
    let dummy = new ListNode();
    let head = dummy;

    while (list1 && list2) {
        if (list1.val < list2.val) {
            head.next = list1;
            list1 = list1.next;
        } else {
            head.next = list2;
            list2 = list2.next;
        }
        head = head.next;
    }

    if (list1) head.next = list1;
    if (list2) head.next = list2;

    return dummy.next;
}
Enter fullscreen mode Exit fullscreen mode

This runs in O(n + m) where n and m are the lengths of the two lists.

🛠 Step 2: Merging K Lists Using Divide and Conquer

We now merge lists pair by pair until only one list remains.

var mergeKLists = function (lists) {
    if (!lists || lists.length === 0) {
        return null;
    }

    while (lists.length > 1) {
        let mergedLists = [];

        for (let i = 0; i < lists.length; i += 2) {
            let l1 = lists[i];
            let l2 = (i + 1) < lists.length ? lists[i + 1] : null;
            mergedLists.push(merge_two_lists(l1, l2));
        }

        lists = mergedLists;
    }

    return lists[0];
};
Enter fullscreen mode Exit fullscreen mode

📊 Complexity Analysis

  • Merging Two Lists: O(n + m)

  • Merging K Lists (Divide & Conquer):

    • Each round halves the number of lists.
    • We perform log k rounds.
    • Each node is processed in every merge step, so total work is O(N log k).

Where:

  • N = total number of nodes across all lists
  • k = number of lists

Space Complexity

  • We only use a few pointers and a dummy node.
  • O(1) extra space (not counting recursion stack if you write a recursive merge).

✅ Key Takeaways

  • The divide and conquer approach is elegant, efficient, and doesn’t require additional data structures.
  • Time complexity: O(N log k)
  • Space complexity: O(1)

If you need even faster performance in practice, a priority queue (min-heap) is often used, especially when k is very large. But for clean code and interviews, this divide-and-conquer approach is a winner.

Top comments (0)