Problem

At Meta, imagine multiple pre-sorted event streams need to be combined into one ordered feed. Given k sorted singly linked lists, merge them into one sorted linked list and return its head.

Formal Specification

Implement a function that takes lists, where lists[i] is the head of a sorted singly linked list or null. Each node contains an integer value and a next pointer. Return the head of a new merged sorted linked list formed by reusing the existing nodes.

Examples

Example 1 Input: lists = [[1,4,5],[1,3,4],[2,6]] Output: [1,1,2,3,4,4,5,6] Explanation: Repeatedly taking the smallest current node across the three lists produces the fully sorted merged list.

Example 2 Input: lists = [] Output: [] Explanation: There are no lists to merge, so the result is empty.

Example 3 Input: lists = [[]] Output: [] Explanation: The only list is empty.

Constraints

• 0 <= k <= 10^4
• 0 <= total number of nodes <= 10^5
• -10^4 <= Node.val <= 10^4
• Each individual linked list is sorted in non-decreasing order.

Aim for a solution better than collecting all values and sorting them again.