Merge K Sorted Lists

Problem

You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.

Merge all the linked-lists into one sorted linked-list and return it.

Example 1:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Example 2:

Input: lists = []
Output: []

Example 3:

Input: lists = [[]]
Output: []

Constraints:

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 10^4.

Solution

Approach 1: Min Heap

The key insight is to use a min heap to efficiently find the smallest element among the heads of all k lists. We repeatedly extract the minimum and add the next node from that list.

Implementation

import heapq

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        # Min heap: (node.val, index, node)
        heap = []

        # Initialize heap with head of each list
        for i, head in enumerate(lists):
            if head:
                heapq.heappush(heap, (head.val, i, head))

        dummy = ListNode()
        current = dummy

        while heap:
            val, i, node = heapq.heappop(heap)
            current.next = node
            current = current.next

            # Add next node from the same list
            if node.next:
                heapq.heappush(heap, (node.next.val, i, node.next))

        return dummy.next

Approach 2: Divide and Conquer

Merge lists pairwise recursively, similar to merge sort.

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if not lists:
            return None

        def mergeTwoLists(l1, l2):
            dummy = ListNode()
            current = dummy

            while l1 and l2:
                if l1.val <= l2.val:
                    current.next = l1
                    l1 = l1.next
                else:
                    current.next = l2
                    l2 = l2.next
                current = current.next

            current.next = l1 if l1 else l2
            return dummy.next

        # Divide and conquer
        while len(lists) > 1:
            merged_lists = []
            for i in range(0, len(lists), 2):
                l1 = lists[i]
                l2 = lists[i + 1] if i + 1 < len(lists) else None
                merged_lists.append(mergeTwoLists(l1, l2))
            lists = merged_lists

        return lists[0] if lists else None

Complexity Analysis

Min Heap Approach:

Time Complexity: O(N log k), where N is the total number of nodes and k is the number of lists. Each insertion/extraction from the heap takes O(log k), and we do this for all N nodes.
Space Complexity: O(k) for the heap storing at most k nodes.

Divide and Conquer:

Time Complexity: O(N log k). We do log k levels of merging, and each level processes all N nodes.
Space Complexity: O(1) for iterative version, O(log k) for recursive version due to call stack.

Key Insights

Min Heap Efficiency: The heap allows us to find the minimum among k elements in O(log k) time, which is much better than scanning all k list heads in O(k) time.
Index in Heap: We include an index in the heap tuple to handle the case where nodes have equal values (Python’s heapq needs a tiebreaker).
Divide and Conquer Strategy: Merging k lists is similar to merge sort. We can merge pairs of lists, then merge the results, reducing the problem size by half each time.
Pairing Pattern: In divide and conquer, we pair lists: merge 0 with 1, 2 with 3, etc. If there’s an odd number, the last list carries forward unchanged.
Trade-offs: Min heap is easier to understand and implement. Divide and conquer has better cache locality and can be parallelized.