LeetCode题目：Merge k Sorted Lists

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

分析
设总长度为n。
最简单的办法就是扫一遍k个链表的开头，哪个最小就把它移除，加入到结果链表中。这样时间复杂度是kn
第二个办法就是进行二分，将k个链表分为两个一组，组内进行merge。形成一个新的链表集合，大小为(k + 1)/2。继续两个一组merge，这样下去一共会进行logk次merge，最后merge成为一个链表。总的时间复杂度是nlogk

其中两个list合并的代码同LeetCode题目：Merge Two Sorted Lists

代码：72ms过大集合

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *proot = NULL;
        ListNode **pplast = &proot;
        while(l1 || l2){
            if(l1) {
                ListNode *minNode;
                if(!l2 || l1->val <= l2->val){
                    //l1 is min
                    minNode = l1;
                    l1 = l1->next;
                } else if(l2) {
                    //l2 is min
                    minNode = l2;
                    l2 = l2->next;
                }
                //proceed root
                *pplast = minNode;
                pplast = &(minNode->next);
            } else {
                //l1 is empty
                *pplast = l2;
                break;
            }
        }
        return proot;
    }
    ListNode *mergeKLists(vector &lists) {
        if(lists.size() == 0)
            return NULL;
        int curSize = lists.size();
        while(curSize > 1) {
            int halfSize = (1 + curSize) / 2;
            //merge i,i + halfSize
            for(int i = 0 ; i < halfSize && i + halfSize < curSize; ++i) {
                ListNode *first = lists[i];
                ListNode *second = lists[i + halfSize];
                ListNode *result = mergeTwoLists(first,second);
                lists[i] = result;
            }
            //set curSize to halfsize
            curSize = halfSize;
        }
        return lists[0];
    }
};