Facebook PixelMerge k Sorted Lists — Coding Practice
Merge k Sorted ListsHard

Merge k Sorted Lists

Hard 19.5k51% acceptance
Linked ListDivide and ConquerHeap (Priority Queue)Merge Sort

You are given an array lists of k linked lists, each already sorted in non-decreasing order.

Merge all of them into one sorted linked list and return its head.

Each element of lists is a ListNode ({ val, next }); an empty list is null. The array itself may be empty ([]), and individual lists may be empty ([[]]). Return the merged list, or the empty list ([]) if there are no nodes.

Example 1
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Merging all three sorted lists yields one sorted sequence.
Example 2
Input: lists = []
Output: []
No lists at all means an empty result.
Example 3
Input: lists = [[]]
Output: []
A single empty list also yields an empty result.
Constraints
  • k == lists.length
  • 0 ≤ k ≤ 10⁴
  • The total number of nodes across all lists is in the range [0, 10⁴].
  • -10⁴ ≤ Node.val ≤ 10⁴ and each list is sorted in non-decreasing order.
Asked atAmazonGoogleMetaMicrosoftUber
JavaScript
Loading editor…
Case 1
[[1,4,5],[1,3,4],[2,6]]
expected: [1,1,2,3,4,4,5,6]
Case 2
[]
expected: []
Case 3
[[]]
expected: []
Case 4
[[],[1]]
expected: [1]
Case 5
[[-2,-1,-1],[-3,0,1]]
expected: [-3,-2,-1,-1,0,1]
Case 6
[[2]]
expected: [2]