Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
以前做的ac,结果前几天提交发现超时了,原来系统最近又加了一个test case。。。用的选择排序,时间复杂度是O(n^2)
采用最小堆,首先将 k 个首节点放入堆中,弹出最小的节点并插入到新的链表中;
弹出的节点如果next 非空,就将它的 下一个节点进 堆。
继续,直到堆为空。
堆 Push 和 pop 的复杂度是 log(k), 所以复杂度是 nlg(k), n为总的节点数
/**
*......
阅读全文