Merge K Sorted Lists

Difficulty: Hard

Problem

There are k linked lists, each in ascending order, supplied as an array. Combine them into a single linked list that is also in ascending order, and return its head.

Example

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: Interleaving the three lists by value produces 1→1→2→3→4→4→5→6.

Brute-force approach, Collect All Values, Sort, Rebuild

Collect all node values into an array, sort the array, then create a new linked list from the sorted values.

Steps

  1. Traverse all k lists, collect all values into one array
  2. Sort the array
  3. Build a new linked list from the sorted array
  4. Return the new list

Time complexity: O(N log N) · Space complexity: O(N)

Trade-offs

  • O(N log N) time is worse than O(N log k) when k << N
  • O(N) extra space for the values array

Optimal approach, Merge Pairs: Divide and Conquer

Key insight: Merge lists in pairs each round, halving the count. After log(k) rounds, one sorted list remains.

Pair up k lists and merge each pair using merge-two-sorted-lists. After each round, k lists become k/2. Repeat until one list remains. This is O(N log k) time.

Steps

  1. While more than one list remains:
  2. Pair up adjacent lists
  3. Merge each pair into one sorted list
  4. Replace lists with merged results
  5. Return the single remaining list

Time complexity: O(N log k) · Space complexity: O(1)

Pseudocode

function mergeKLists(lists):
    if lists is empty: return null
    while lists.length > 1:
        merged = []
        for i = 0 to lists.length step 2:
            l1 = lists[i]
            l2 = (i+1 < lists.length) ? lists[i+1] : null
            merged.push(mergeTwoLists(l1, l2))
        lists = merged
    return lists[0]

Hints

  • Think of divide and conquer: merge pairs of lists
  • Reuse the merge two sorted lists solution
  • Keep merging until only one list remains

Complexity questions

What is the time complexity of collect-and-sort?

O(N log N). Collecting all N values is O(N), sorting them is O(N log N). Total: O(N log N).

What is the space complexity of collect-and-sort?

O(N). We store all N values in an array, requiring O(N) space.

What is the time complexity of divide and conquer merge?

O(N log k). There are log(k) rounds, and each round processes all N nodes once. Total: O(N log k).

What is the space complexity of divide and conquer merge?

O(1). We merge in-place by re-linking nodes. Only a constant number of pointers are used (ignoring the input/output list).

Check your understanding of Merge K Sorted Lists

For lists [[1,4,5],[1,3,4],[2,6]], what should the merged result be?

[1,1,2,3,4,4,5,6] (all elements in sorted order). The merged result contains all elements from all k lists arranged in sorted (non-decreasing) order: [1,1,2,3,4,4,5,6].

How is merging k sorted lists different from merging 2 sorted lists?

We need to consider elements from k lists instead of just 2, picking the smallest among all current heads. With k lists, at each step we must compare the front elements of all k lists and pick the smallest. This generalizes the 2-list merge to k lists.

What if the input contains empty lists like [[], [1], []]?

Empty lists are naturally handled, merging with null returns the other list. When merging a non-empty list with an empty (null) list, the merge function simply returns the non-empty list.

Related problems

Keep practising