[LeetCode 23] Merge k Sorted Lists

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

Input: lists = []
Output: []
Example 3:

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

- k == lists.length
- 0 <= k <= 10^4
- 0 <= lists[i].length <= 500
- -10^4 <= lists[i][j] <= 10^4
- lists[i] is sorted in ascending order.
- The sum of lists[i].length won't exceed 10^4.

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
    // special case handle
    if(lists.length === 0) return null;
    
    const values = []
    
    // save all node values and sort them
    for(let list of lists){
        while(list !== null) {
            values.push(list.val)
            list = list.next
        }
    }
    values.sort((a, b) => a - b)

    // create current & dummy node for iteration
    let cur = new ListNode(0)
    let dummy = cur;
    for(let i = 0; i < values.length; i++){
        cur.next = new ListNode(values[i])
        cur = cur.next
    }

    // return dummy next
    return dummy.next;
};