Given an array of linked lists, lists, where each linked list's node values are in ascending order, combine all these linked lists into a single sorted linked list and return the head node of the combined linked list.

The linked list is represented by a sequence of ListNodes, where each node points to the next node in the sequence, or null if it is the last node.

A ListNode has the following interface:

interface ListNode {
  val: number;
  next: ListNode | null;
}

Input

• lists: Array<ListNode | null>: Array of head nodes of linked lists. An empty linked list is represented by null. Examples display each linked list as an array of values within the list

If every linked list is empty, return null.

Input: lists = [[10,20,30],[5,15,25],[2,12,22]]
Output: [2,5,10,12,15,20,22,25,30]
Explanation: The lists are combined into a single sorted list with elements in increasing order.

Input: lists = [[1],[3],[2]]
Output: [1,2,3]
Explanation: Each list contains a single element, so they are combined into a sorted list.

Input: lists = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,2,3,4,5,6,7,8,9]
Explanation: All lists are already in ascending order and combined directly.

Constraints

• 1 <= lists.length <= 100
• 0 <= Number of nodes per list <= 100
• -10,000 <= ListNode.val <= 10,000