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: ListNode[]: Array of head nodes of linked lists. Examples display each linked list as an array of values within the list

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