noodleProblems/
Merge k Sorted Lists
#19

Merge k Sorted Lists

AlgorithmhardLinked ListDivide And ConquerHeap Priority QueueMerge Sort

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

Each list is shown in array notation for readability — [[1, 4, 5], [1, 3, 4], [2, 6]] is three sorted lists, and the answer is the single merged list [1, 1, 2, 3, 4, 4, 5, 6]. The outer array may be empty, and individual lists may be empty.

Example cases

  • three lists
    in lists = [[1,4,5],[1,3,4],[2,6]]
    out [1,1,2,3,4,4,5,6]11234456null
    Merging the three sorted lists interleaves their values into one sorted run.
  • no lists
    in lists = []
    out []null
  • one empty list
    in lists =
    out []null

Constraints

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length, and the total number of nodes across all lists is in the range [0, 10^4].
  • -10^4 <= lists[i][j] <= 10^4
  • Each lists[i] is sorted in non-decreasing order.
Saved
lists =
[[1,4,5],[1,3,4],[2,6]]