Merge K Sorted Lists

Problem Description

You are given an array of k linked lists, each sorted in ascending order. Merge all of them into one sorted linked list and return its head.

Examples

Constraints

• k == lists.length
• 0 ≤ k ≤ 10⁴
• 0 ≤ lists[i].length ≤ 500
• -10⁴ ≤ lists[i][j] ≤ 10⁴
• lists[i] is sorted in ascending order.
• The sum of all lists[i].length will not exceed 10⁴.

Merging One List at a Time Is O(kN); Divide and Conquer Gets You to O(N log k)

The naive approach: merge list 0 into list 1, then merge the result into list 2, and so on. Each merge is O(current_size + next_list_size). The first merge is O(n), the second is O(2n), …, the k-1th is O((k-1)n). Total: O(kN). That’s fine for small k but bad for k = 10⁴.

Divide and conquer cuts the merges differently. Pair up lists and merge each pair. In round 1, k lists become k/2. In round 2, k/2 become k/4. After log k rounds, everything is merged. Each round processes N total nodes. Total: O(N log k).

The min-heap approach also achieves O(N log k) but maintains a heap of the current heads of all k lists, popping the minimum and pushing the next node of that list. It’s useful when you need to merge streams lazily (one node at a time) rather than all at once.

Solution 1: Merge One at a Time (Baseline)

Fold the list array left to right.

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length == 0) return null;
        ListNode merged = lists[0];
        for (int i = 1; i < lists.length; i++) {
            merged = mergeTwoLists(merged, lists[i]);
        }
        return merged;
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
            else { curr.next = l2; l2 = l2.next; }
            curr = curr.next;
        }
        curr.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}

class Solution:
    def mergeKLists(self, lists: list) -> ListNode:
        if not lists:
            return None
        merged = lists[0]
        for i in range(1, len(lists)):
            merged = self.mergeTwoLists(merged, lists[i])
        return merged

    def mergeTwoLists(self, l1, l2):
        dummy = ListNode(0)
        curr = dummy
        while l1 and l2:
            if l1.val <= l2.val: curr.next, l1 = l1, l1.next
            else: curr.next, l2 = l2, l2.next
            curr = curr.next
        curr.next = l1 or l2
        return dummy.next

class Solution {
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* curr = &dummy;
        while (l1 && l2) {
            if (l1->val <= l2->val) { curr->next = l1; l1 = l1->next; }
            else { curr->next = l2; l2 = l2->next; }
            curr = curr->next;
        }
        curr->next = l1 ? l1 : l2;
        return dummy.next;
    }
public:
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        ListNode* merged = lists[0];
        for (int i = 1; i < lists.size(); i++) merged = mergeTwoLists(merged, lists[i]);
        return merged;
    }
};

Complexity Analysis:

• Time Complexity: O(kN). Each merge pass touches an increasingly large merged list.
• Space Complexity: O(1) extra. Reuses existing nodes.

Where it breaks: at k = 10⁴ with N = 10⁴ total nodes, this is 10⁸ operations in the worst case. The divide and conquer approach reduces this by a factor of log k.

Solution 2: Divide and Conquer

Repeatedly pair up lists and merge each pair until one list remains.

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

    private ListNode mergeRange(ListNode[] lists, int lo, int hi) {
        if (lo == hi) return lists[lo];
        int mid = lo + (hi - lo) / 2;
        ListNode left = mergeRange(lists, lo, mid);
        ListNode right = mergeRange(lists, mid + 1, hi);
        return mergeTwoLists(left, right);
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
            else { curr.next = l2; l2 = l2.next; }
            curr = curr.next;
        }
        curr.next = l1 != null ? l1 : l2;
        return dummy.next;
    }
}

class Solution:
    def mergeKLists(self, lists: list) -> ListNode:
        if not lists:
            return None

        def merge_two(l1, l2):
            dummy = ListNode(0)
            curr = dummy
            while l1 and l2:
                if l1.val <= l2.val: curr.next, l1 = l1, l1.next
                else: curr.next, l2 = l2, l2.next
                curr = curr.next
            curr.next = l1 or l2
            return dummy.next

        def merge_range(lo, hi):
            if lo == hi: return lists[lo]
            mid = (lo + hi) // 2
            return merge_two(merge_range(lo, mid), merge_range(mid + 1, hi))

        return merge_range(0, len(lists) - 1)

class Solution {
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy(0);
        ListNode* curr = &dummy;
        while (l1 && l2) {
            if (l1->val <= l2->val) { curr->next = l1; l1 = l1->next; }
            else { curr->next = l2; l2 = l2->next; }
            curr = curr->next;
        }
        curr->next = l1 ? l1 : l2;
        return dummy.next;
    }

    ListNode* mergeRange(std::vector<ListNode*>& lists, int lo, int hi) {
        if (lo == hi) return lists[lo];
        int mid = lo + (hi - lo) / 2;
        return mergeTwoLists(mergeRange(lists, lo, mid), mergeRange(lists, mid + 1, hi));
    }
public:
    ListNode* mergeKLists(std::vector<ListNode*>& lists) {
        if (lists.empty()) return nullptr;
        return mergeRange(lists, 0, lists.size() - 1);
    }
};

Complexity Analysis:

• Time Complexity: O(N log k). log k merge rounds, each processing all N nodes.
• Space Complexity: O(log k). Recursion stack depth.

Where it breaks: the recursive implementation uses O(log k) stack space. For k = 10⁴, that’s about 14 frames deep. No concern. An iterative bottom-up version eliminates even this, but it’s rarely necessary.

Why Not Use a Min-Heap?

A min-heap approach puts the heads of all k lists into a heap. On each step, pop the minimum node, add it to the result, and push that node’s next if it exists. This is O(N log k) time and O(k) space. The trade-off: the heap maintains k pointers at all times, so it uses more space than divide and conquer’s O(log k) stack. Divide and conquer wins on space. The heap approach wins when you need to merge lazily (produce the next minimum without merging everything upfront).

Common Mistakes

• Not handling lists being empty or containing only null entries. If lists = [[]], the single list is null. The merge should return null, not crash on l1.val.
• Off-by-one in the divide and conquer range. The base case is lo == hi, not lo >= hi. Getting this wrong causes infinite recursion.
• Using lists.length instead of lists.length - 1 as the initial hi. The range is 0 to k - 1, inclusive.

Frequently Asked Questions

When should you use the min-heap approach over divide and conquer? Use a min-heap when the lists are streams (you don’t have all nodes upfront) or when you want to produce the merged sequence incrementally. For static lists where you want the full result, divide and conquer is simpler and uses less space.

What if some lists are null? mergeTwoLists(null, l2) returns l2 immediately in both implementations. Null lists are handled without special casing.

How does this relate to the external sort algorithm? This is essentially a k-way merge, the final phase of external sort. Divide and conquer and min-heap are the standard implementations in database systems for this exact step.

← All Problems