Merge K sorted Lists

今天在看Twitter Design,刚好做一下这个练习一下Merging Timeline。

2月份时候做的笔记【虽然我完全不记得了】 看起来用Priority Queue来做是一个solution。怪不得之前做Twitter OO design那题大家都是用Priority Queue。

这题有一个比较tricky的地方。我们一开始把每个List的head放进Queue里,但是queue并不知道每个List后面接着的是多少。然后我们把node们一个一个从queue里pop出来,先pop出来的是比较小的,每次pop出一个,我们取它的nextNode 扔进Queue。所以Queue里实际还是只有K个东西。

所以什么时候应该停止? 当Queue是empty的时候,也就是上一轮到头了没有再offer新Node了。

Merge Sort看起来也是一个很好的办法【怪不得叫merge sort】。

MergeTwoLists 那个方法他省略没写

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容