Merge k Sorted Lists_weixin_33785108的博客-程序员宝宝

题目描述：

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

　　因为之前做过Merge Two Sorted Lists，所以这道题也就显得不那么难了。

solution：

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

ListNode *mergeKLists(vector<ListNode *> &lists) {
    int n = lists.size();
    if(n == 0)
        return NULL;
    if(n == 1)
        return lists[0];
    if(n == 2)
        return mergeTwoLists(lists[0], lists[1]);
    vector<ListNode *>::iterator mid = lists.begin() + n / 2;
    vector<ListNode *> front(lists.begin(), mid);
    vector<ListNode *> back(mid, lists.end());
    return mergeTwoLists(mergeKLists(front), mergeKLists(back));
}

ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
    ListNode *head = new ListNode(0);
    ListNode *p = head;
    while (l1 != NULL && l2 != NULL)
    {
        if (l1->val < l2->val)
        {
            p->next = l1;
            l1 = l1->next;
        }
        else
        {
            p->next = l2;
            l2 = l2->next;
        }
        p = p->next;
    }
    p->next = l1 ? l1 : l2;
    return head->next;
}

参考链接：https://leetcode.com/discuss/9279/a-java-solution-based-on-priority-queue