Hard

Merge k Sorted Lists

LAB

Given k sorted linked lists encoded as rows of values, merge all lists into one sorted linked list and return its values.

EXAMPLES

Example 1

Input
{
  "lists": [
    [
      1,
      4,
      5
    ],
    [
      1,
      3,
      4
    ],
    [
      2,
      6
    ]
  ]
}

Output
[
  1,
  1,
  2,
  3,
  4,
  4,
  5,
  6
]

FUNCTION SHAPE

lists: intMatrix→intArray

SOLUTION NOTE

Approach 1 is intuitive but not optimal, as we repeatedly scan through the growing result list.

Approach 2 T(k) = 2*T(k//2) + O(n) => O(nlogk). This approach is much more efficient as it pairs up lists and merges them, reducing the number of comparisons. You should read the divide and conquer section first before trying to understand this solution. Once you read that section, this logic is straightforward. If we merge all lists on the left half into one list, and all lists on the right half into one list, we can merge them together using the mergeTwoLists function from the last question. Nice.

Approach 3 efficiently merges all lists by always taking the smallest node available across all lists. The priority queue gives us the smallest element in log(k) time. Note that we don't use i, but we need it in the tuple as the second argument, otherwise heapify will complain since it can't compare list nodes using '<'. (try removing it from the tuple)

The key insight in this problem is the efficiency gain from using either divide and conquer or a priority queue, which reduces the time complexity from O(Nk) to O(Nlog(k)). For large values of k, this makes a significant difference.

Reveal reference solution +

pythonREFERENCE

# Approach 1: Sequential Merging
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists:
        return None

    result = lists[0]
    # Sequentially merge each list with the result
    for i in range(1, len(lists)):
        result = self.mergeTwoLists(result, lists[i])

    return result
# Time: O(N*k), Space: O(1)

# Approach 2: Divide and Conquer (More Efficient)
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists:
        return None

    # Merge lists using divide and conquer
    def merge(lists, start, end):
        if start == end:
            return lists[start]
        if start > end:
            return None

        mid = start + (end - start) // 2
        left = merge(lists, start, mid)
        right = merge(lists, mid + 1, end)
        return mergeTwoLists(left, right)

    return merge(lists, 0, len(lists) - 1)
# Time: O(N*log(k)), Space: O(log(k))

# Approach 3: Using a Priority Queue (Heap)
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    pq = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapify(pq)
    dummy = ListNode(-1)
    curr = dummy

    while pq:
        _, i, top_node = heappop(pq)

        curr.next = top_node
        curr = top_node

        if top_node.next:
            heappush(pq, (top_node.next.val, i, top_node.next))

    return dummy.next
# Time: O(N*log(k)), Space: O(k)

TimeO(N*log(k))

SpaceO(k) for heap approach

Open on LeetCode ↗