Combine Sorted Linked Lists

You are given an array lists of k linked lists, each already sorted in ascending order. Merge all k lists into a single sorted linked list and return its head.

Each list node has a val (integer) and a next pointer (or None at the end of a list). Any of the input lists may be empty (None).

Example 1

Input: lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
Output: [1, 1, 2, 3, 4, 4, 5, 6]
Explanation: Merging the three sorted lists produces one fully
sorted list.

Example 2

Input: lists = [[], [], []]
Output: []

Constraints

• 0 <= k <= 10^4
• 0 <= length of each list <= 500
• -10^4 <= node.val <= 10^4
• Each individual list is sorted in non-decreasing order.