Use a min-heap to always know the smallest element across all lists.
Add the head of each list to the heap. Pop the smallest, add it to the result, then push its next node (if any) back to the heap.
The heap always contains at most k elements (one from each list), so each push/pop costs .
Alternatively, use divide and conquer: pair up lists and merge them, reducing k lists to k/2 lists each round. Repeat until one list remains.