LeetCode 23. Merge k Sorted Lists


经典题
解法一:优先队列
class CMP{
public:
    bool operator () (const ListNode* a, const ListNode * b) const {
        return a->val > b->val;
    }    
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *head = nullptr;
        if (lists.size() == 0){
            return head;
        }
        
        ListNode *tail = nullptr;
        priority_queue<ListNode*, vector<ListNode*>, CMP> que;
        
        for (int i = 0; i < lists.size(); ++i){
            if (lists[i] != nullptr){
                que.push(lists[i]);
            }
        }
        
        if (que.empty()){
            return head;
        }
        
        head = que.top();
        tail = head;
        que.pop();
        if (tail->next != nullptr){
            que.push(tail->next);
        }
        
        while (!que.empty()){
            ListNode *curNode = que.top();
            que.pop();
            tail->next = curNode;
            tail = tail->next;
            if (tail->next != nullptr){
                que.push(tail->next);
            }
        }
        return head;
    }
};


解法二:基于分治的思想,每次找两个链表合并成一个,一直到只剩最后一个,这里用一个queue提高效率,vector里erase是很耗时的
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *head = nullptr;
        if (lists.size() == 0){
            return head;
        }
        
        queue<ListNode *> que;
        for (int i = 0; i < lists.size(); ++i){
            que.push(lists[i]);
        }
        
        while (que.size() > 1){
            ListNode *a = que.front();
            que.pop();
            ListNode *b = que.front();
            que.pop();
            ListNode *c = mergeList(a, b);
            que.push(c);
        }
        
        return que.front();
    }
    
    ListNode *mergeList(ListNode *a, ListNode *b){
        if (a == nullptr){
            return b;
        }
        if (b == nullptr){
            return a;
        }
        
        ListNode *head = nullptr, *tail = nullptr;
        if (a->val < b->val){
            head = a;
            a = a->next;
        }else{
            head = b;
            b = b->next;
        }
        
        tail = head;
        while (a != nullptr && b != nullptr){
            if (a->val < b->val){
                tail->next = a;
                a = a->next;
            }else{
                tail->next = b;
                b = b->next;
            }
            tail = tail->next;
        }
        
        if (a != nullptr){
            tail->next = a;
        }
        if (b != nullptr){
            tail->next = b;
        }
        
        return head;
    }
};
已邀请:

要回复问题请先登录注册

返回顶部