All problems

Merge k Sorted Lists

Hard · heap

You are given an array lists of k linked lists. Each list is already sorted in non-decreasing order. Merge all of them into one sorted list and return its head.

Some of the lists can be empty, and lists itself can be empty. If there are no nodes at all, return None. Reusing the existing nodes is fine, you do not have to create new ones. The nodes you receive are ListNode objects with a val and a next.

Examples

Example 1

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]

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

Taking the smallest front value among the three lists at every step gives 1, 1, 2, 3, 4, 4, 5, 6.

Example 2

Input: lists = []

Output: []

There are no lists, so there are no nodes to return.

Example 3

Input: lists = [[]]

Output: []

There is one list and it is empty, so the result is empty too.

Constraints

• 0 <= len(lists) <= 1000
• 0 <= number of nodes in each list
• The total number of nodes across all lists is at most 5000
• -10^4 <= Node.val <= 10^4
• Every list is sorted in non-decreasing order.