[LeetCode]Merge k Sorted Lists

为了方便计算时间复杂度，先假设有n个list，每个list的长度为m。首先我们可以想到的一个方法是，每个list不断地和第一个list merge，直到我们只剩第一个list为止。这样的话，要进行n - 1次merge，第一个list里每个元素会被扫n - 1次，第二个list里每个元素会被扫n - 2次，以此类推。所以总的时间复杂度是O(n * n * m)。然后我们应该能很快想到一个提高的方法就是两两merge，这样merge的过程就像一个二叉树，在每层每个元素会被扫一次，有log n层，所以时间复杂度是O(n * m * log n)。代码如下：

另外一个方法就是，维护一个heap，每次从heap中删掉最小的值，然后把删掉元素的next元素加入，每个元素要进一次出一次heap，时间复杂度也是O(n * m * log n)，代码如下：