k聊已排序链表的合并O(nlgk)
k路已排序链表的合并O(nlgk)
题目：请给出一个时间为O(nlgk)、用来将k个已排序链表合并为一个排序链表的算法。此处n为所有输入链表中元素的总数。
(机械工业出版社 《算法导论》P82 6.5-8)
这是网上找到一个解答：
1.把每个已排序链表的第一个值取下，构建一个k个元素的最小堆。
2.找到最小元素原来的链表，从中取下第二个元素，插入最小堆。
3.接着找到当前最小元素原来的链表，从中取下下一个元素，插入最小堆。
4.循环直到所有链表为空。
这里我有个疑问:
第三步是不是可以替换成随便从k个链表中取出一个元素，插到最小堆里，这样时间复杂度也是O(nlgk)。可是这样的话就完全没有到每个链表是有序的这个特性了。
明白了，第2步中还需要把堆顶即最大的元素摘掉，插到最后结果的大链表里