Given an array of k linked lists, each already sorted in non-decreasing order, merge all of them into one sorted linked list and return its head. This is a direct extension of merging two sorted lists (see "Merge Two Sorted Linked Lists Into One") — the question is how to combine k of them without doing needlessly repeated work. A divide and conquerDivide and Conquer MergeSplit the k lists in half, recursively reduce each half down to a single sorted list, then merge those two results with an ordinary two-list merge. Halving at every level means each node only participates in about log k merges total, instead of up to k merges if lists were combined one at a time into a growing result. approach splits the array of lists in half, recursively merges each half down to one list, and combines the two halves with the same two-pointer splice used for two lists — turning k lists into one in O(N log k) instead of the O(N·k) that merging them one at a time would cost.