今天在看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 那个方法他省略没写