23. Merge k Sorted Lists

题目描述：将k个已排序的链表合并为一条排好序的链表。分析复杂度。
分析：k个链表的归并可以利用归并排序的思想，每次取其中两个归并直到最后合为一个。k个链表每次归并为O(n)，共O(nk)的复杂度TLE。
方法一：用分治的思想，第一次划分将所有链表分k/2组，每次归并都是O(n)，二分之后只需处理lgk次，故时间复杂度O(nlgk)，空间复杂度O(1)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
//解决主函数要放在前面
        ListNode* mergeKLists(vector<ListNode*>& lists) {
        int k = lists.size();
        if (k == 0) return NULL;
        //二分法，每次合并到前一个链表中
        while(k > 1)
        {
            int j = (k + 1) / 2;
            for(int i = 0; i < k/2 ; i ++)
                lists[i] = merge2Lists(lists[i], lists[i + j]);
            k = j;
        }
        return lists[0];
    }
    //合并2个有序链表
    ListNode *merge2Lists(ListNode *l1, ListNode *l2){
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        ListNode *l = new ListNode(-1);
        ListNode *h = l;
        while(l1 != NULL && l2 != NULL)
        {
            if (l1->val < l2->val)
            {
                h->next = l1;
                l1 = l1->next;
            }
            else
            {
                h->next = l2;
                l2 = l2->next;
            }
            
            h = h->next;
        }
        if (l1 == NULL)
            h->next = l2;
        else if (l2 == NULL)
            h->next = l1;
        
        return l->next;
    }
};

方法二：利用最小堆构成的优先队列，首先将每个链表的第一个元素加入队列，每次取出队首元素后，将相应链表的下一个元素加入队列，循环此操作直到队列为空。由于k个链表是有序的，所以每个链表的元素也是按从小到大进入队列，故队列中始终存放当前k个最小元素。每个元素入队一次O(kn)，每次插入新元素后需调整O(lgk)。故时间复杂度O(kn * lgk)，空间复杂度O(k)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    //STL自带的优先队列默认大数优先
    struct cmp{
        bool operator() (ListNode *a, ListNode *b){
            return a->val > b->val;
        }
    };
    
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> queue;
        for (int i = 0; i < lists.size(); i ++)
        {
            if(lists[i] != NULL)
                queue.push(lists[i]);
        }
        ListNode *l = NULL, *pre = NULL, *t;
        while(!queue.empty())
        {
            t = queue.top();
            queue.pop();
            if (pre == NULL)
                l = t;
            else
                pre->next = t;
            
            pre = t;
            if(t->next != NULL)
                queue.push(t->next);
        }
        return l;
    }
};