LeetCode 23. Merge k Sorted Lists


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;
        }
    };
    

    Comments are closed.