k路已排序链表的合并O(nlgk)

题目：请给出一个时间为O(nlgk)、用来将k个已排序链表合并为一个排序链表的算法。此处n为所有输入链表中元素的总数。

(机械工业出版社 《算法导论》P82  6.5-8)

 

这是网上找到一个解答：

1.把每个已排序链表的第一个值取下，构建一个k个元素的最小堆。

2.找到最小元素原来的链表，从中取下第二个元素，插入最小堆。

3.接着找到当前最小元素原来的链表，从中取下下一个元素，插入最小堆。

4.循环直到所有链表为空。

 

这里我有个疑问:

第三步是不是可以替换成随便从k个链表中取出一个元素，插到最小堆里，这样时间复杂度也是O(nlgk)。可是这样的话就完全没有到每个链表是有序的这个特性了。

 

明白了，第2步中还需要把堆顶即最大的元素摘掉，插到最后结果的大链表里