# Merge k Sorted Lists in TypeScript

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
// If the list of lists is empty, return null
if (lists.length === 0) {
return null;
}
// If the list of lists has only one list, return that list
if (lists.length === 1) {
return lists[0];
}
// Find the middle index of the list of lists
const mid = Math.floor(lists.length / 2);
// Recursively merge the left half of the list of lists
const left = mergeKLists(lists.slice(0, mid));
// Recursively merge the right half of the list of lists
const right = mergeKLists(lists.slice(mid));
// Merge the two halves and return the result
return mergeTwoLists(left, right);
}

// Helper function to merge two sorted lists
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
// Create a dummy head node for the merged list
const dummy = new ListNode();
// Initialize the current node to the dummy node
let curr = dummy;
// While both lists are not null
while (l1 && l2) {
// If the value of l1 is smaller than or equal to the value of l2
if (l1.val <= l2.val) {
// Append l1 to the merged list
curr.next = l1;
// Move l1 to the next node
l1 = l1.next;
}
// Otherwise
else {
// Append l2 to the merged list
curr.next = l2;
// Move l2 to the next node
l2 = l2.next;
}
// Move the current node to the next node
curr = curr.next;
}
// If l1 is not null, append the remaining nodes of l1 to the merged list
if (l1) {
curr.next = l1;
}
// If l2 is not null, append the remaining nodes of l2 to the merged list
if (l2) {
curr.next = l2;
}
// Return the head of the merged list
return dummy.next;
}