https://leetcode.com/problems/merge-k-sorted-lists/

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

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
 

var mergeTwoLists = function(l1, l2) {
    var head = new ListNode(0), ptr = head;
    
    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;
    }
    
    return head.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);
};

复杂度一样。

/**
 * Definition for singly-linked list.
 * 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));
        
        ListNode* head = new ListNode(0), *ptr = head;
        
        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();
        }
        
        return head->next;
    }
};

Posted by xiaodao
Category: LeetCode