多路归并问题

题目描述：

有K张已经排序好的链表，将其归并为一张排序列表。
链表节点定义如下：

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

分析与题解：

多路归并问题是一类经典~~（其实我也是最近才看到的这个题QAQ）~~的算法问题，如何设计算法与合理利用数据结构至关重要。
对于以下数据，我们做出约定：$ N=Max{\ Len(list)\ } $（大括号不知为什么页面上显示不出来QAQ）
首先来看一般的做法:

方法一（暴力法）:

想法：将所有链表遍历，数据存放到一个数组中，对数组排序，然后再组合成链表。
时间复杂度分析：遍历一遍再重新构建，复杂度为$ O(KN) $，排序复杂度为$ O(KNlog(KN)) $，所以总和为 $ O(KNlog(KN)) $
空间复杂度分析：开了一张大小为$ KN $的数组，占用$ O(KN) $的大小

方法二（暴力法）：

想法：将链表两两归并，最后成为一个链表。
时间复杂度分析：第一张表参与了$ K-1 $次归并，第二张表参与了$ K-2 $次归并，同理第 $ i $ 张表参与了$ K - i $ 次归并，因此总体时间复杂度为$ O((1+2+3+\cdots+K-1)\times N)=O(K^2N) $
空间复杂度分析：组成一张总的链表，占用$ O(KN) $的大小

方法三（分治）：

想法：同类似归并排序的方法（不会的自己去康）解决，每次归并两张表。
代码（出口为mergeKLists):

ListNode* mergeTwoList(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    ListNode* p = dummy;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val <= l2->val) {
            p->next = l1;
            p = p->next;
            l1 = l1->next;
        } else {
            p->next = l2;
            p = p->next;
            l2 = l2->next;
        }
    }
    while (l1 != NULL) {
        p->next = l1;
        p = p->next;
        l1 = l1->next;
    }
    while(l2 != NULL) {
        p->next = l2;
        p = p->next;
        l2 = l2->next;
    }
    p = dummy->next;
    delete dummy;
    return p;
}
ListNode* merge(vector<ListNode*>& lists, int left, int right) {
    if (left == right) return lists[left];
    if (left + 1 == right) return mergeTwoList(lists[left], lists[right]);
    else {
        int center = (left + right) / 2;
        ListNode* l1 = merge(lists, left, center);
        ListNode* l2 = merge(lists, center + 1, right);
        return mergeTwoList(l1, l2);
    }
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    int n = lists.size();
    if (n == 0) return NULL;
    else return merge(lists, 0, n - 1);
}

时间复杂度分析：类似归并排序，时间复杂度为$ O(KNlogK) $
空间复杂度分析：递归层数最深可达$ logK $层，占用空间大小为$ O(log_2^2 K) $

方法四（最小堆/优先队列）：

想法：注意到最小堆的特性，队首的一定是数据中最小的元素（其他不一定是顺序排列），对于加入和提取元素，其时间复杂度均为$ O(logN) $（这里$ N $和上面无关），利用这个性质，我们每次只取一个元素，同时只加入一个元素，即可达到优化的效果。在C++中，我们可以直接使用priority_queue模拟优先队列，注意自定义比较函数。
代码：

struct cmp {
    bool operator() (ListNode* l1, ListNode* l2) {
        return l1.val > l2.val;
    }
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    int n = lists.size();
    if (n == 0) return NULL;
    priority_queue<ListNode*, vector<ListNode*>, cmp> q;
    for (int i = 0; i < n; i++) {
        if (lists[i] != NULL)
            q.push(lists[i]);
    }
    ListNode* dummy = new ListNode(0);
    ListNode* p = dummy;
    while(!q.empty()) {
        p->next = q.top();
        q.pop();
        p = p->next;
        if (p->next != NULL)
            q.push(q->next);
    }
    p->next = NULL;
    p = dummy->next;
    delete dummy;
    return p;
}