How do you merge n sorted lists with average length K in O(nklogn) time?

How do you merge n sorted lists with average length K in O(nklogn) time?

Use heap to find the min or max value, the complexity is O(nklogn)
Take root and insert a new node in the root, shift down the new root to proper position, we need O(2logn) complexity. (compare two child nodes and compare parent node with one max or min child node)