# 某岛

… : "…アッカリ～ン . .. . " .. .
June 27, 2015

## LeetCode 23. Merge k Sorted Lists

• 做法一：分治
• 类似归并排序，每次分两半递归，然后用 前一题 的代码合并起来。复杂度 T(n) = 2T(n/2) + O(kn)。

```/**
* function ListNode(val) {
*     this.val = val;
*     this.next = null;
* }
*/
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/

var mergeTwoLists = function(l1, l2) {

while (l1 !== null || l2 !== null){
if (l1 !== null && (l2 === null || l1.val < l2.val)){
ptr.next = new ListNode(l1.val);
l1 = l1.next;
}
else{
ptr.next = new ListNode(l2.val);
l2 = l2.next;
}
ptr = ptr.next;
}

};

var mergeKLists = function(lists) {
var k = lists.length;
if (k == 0) return null;
if (k == 1) return lists[0];

var m = k / 2;
var l = mergeKLists(lists.slice(0, m));
var r = mergeKLists(lists.slice(m));
return mergeTwoLists(l, r);
};
```
• 做法二：优先队列
• 复杂度一样。

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

#define REP(i, n) for (int i=0;i<n;++i)
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> Q;

class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {

int k = lists.size(); REP(i, k) if (lists[i] != nullptr) Q.push(make_pair(lists[i]->val, i));

while (!Q.empty()){
ptr->next = new ListNode(Q.top().first); ptr = ptr->next;
int i = Q.top().second; lists[i] = lists[i]->next;
if (lists[i] != nullptr) Q.push(make_pair(lists[i]->val, i));
Q.pop();
}