You receive an array holding the heads of k linked lists, with every individual list already in ascending order.
Produce the head of one ascending linked list that includes every node from all supplied lists.
Interview versions may ask either for arbitrary k or specifically for k = 3. For exactly three lists, a direct three-list merge is preferred to using a heap; the general k version favors a heap-based approach.
Notes
Boundary cases: if the array of lists is empty, return null; if every supplied head is null, also return null; lists with differing lengths require no special handling beyond the usual merge behavior.
Preparation
Practice both implementations: a heap-driven solution for general k and a pointer-based three-way merge for k = 3. Put extra emphasis on the three-list version, since it tests careful pointer handling in associate-level interviews.
Problem 23, "Merge k Sorted Lists," is the standard equivalent exercise and appears on the relevant tagged practice list.