Merge k Sorted Lists

    这种方法非常简单直接，但是时间复杂度较高，容易出现 TLE.

    源码分析

    1. 由于头节点不定，我们使用dummy节点。
    2. 使用last表示每次归并后的新链表末尾节点。
    3. count用于累计链表表头节点为NULL的个数，若与 vector 大小相同则代表所有节点均已遍历完。
    4. tempVal用于保存每次比较 vector 中各链表表头节点中的最小值，index保存本轮选择归并过程中最小值对应的链表索引，用于循环结束前递推该链表表头节点。

    复杂度分析

    由于每次for循环只能选择出一个最小值，总的时间复杂度最坏情况下为 O(k \cdot \sum ^{k}_{i=1}l_i). 空间复杂度近似为 O(1).

    源码分析

    实现合并两个链表的子方法后就没啥难度了，mergeKLists中左半部分链表初始化为lists[0], for循环后迭代归并head和lists[i].

    复杂度分析

    合并两个链表时最差时间复杂度为 O(l1+l_2), 那么在以上的实现中总的时间复杂度可近似认为是 l_1 + l_1+l_2 +…+l_1+l_2+…+l_k = O(\sum {i=1} ^{k} (k-i) \cdot l_i). 比起题解1复杂度是要小一点，但量级上仍然差不太多。实际运行时间也证明了这一点，题解2的运行时间差不多时题解1的一半。那么还有没有进一步降低时间复杂度的可能呢？当然是有的，且看下题分解…

    源码分析

    由于需要建立二分递归模型，另建一私有方法helper引入起止位置较为方便。下面着重分析helper。

    1. 分两种边界条件处理，分别是和start + 1 == end. 虽然第二种边界条件可以略去，但是加上会节省递归调用的栈空间。
    2. 使用分治思想理解helper, left和right的边界处理建议先分析几个简单例子，做到不重不漏。
    3. 注意merge2Lists中传入的参数，为lists[start]而不是start…

    在mergeKLists中调用helper时传入的end参数为lists.size() - 1，而不是lists.size().

    复杂度分析

    优化后的运行时间显著减少！由题解2中的500+ms 减至40ms 以内。