一种结合链表和优先队列的优雅解法,巧妙之处在于使用优先队列出队元素,可以直接得到下一个入队元素,算法复杂度是O(nlgn)。联想到如果不是优先队列结构,那么我们可以使用同样的解法,只是我们需要在队列中记录每个元素属于哪一行,而使用链表结构就避免了这种麻烦。

题目

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

分析

如摘要中所说,最小元素一定是每一个链表最前面的元素之一,在其中选取最小的。那么,自然就是使用优先队列了。

另外,一个小技巧,代码中使用了哑节点,方便书写循环。

代码

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注