Merge k Sorted Lists

Merge k sorted linked lists into one sorted list.

List format. A linked list is given as two lines: its length n, then its n values from head to tail (the second line is empty when n = 0). When you print a list, print its values on one line separated by spaces, or the word empty if it has no nodes.

Input:

• line 1: k
• then k lists, each in list format (2 lines)

Output: the merged list.

Constraints: 0 ≤ k ≤ 10⁴, total number of nodes ≤ 10⁵, −10⁴ ≤ value ≤ 10⁴.

Think about it: merging lists one by one costs O(k·N). Use a min-heap holding the current head of every list (O(N log k)), or merge them in pairs like merge sort.